Skip to content

SplayTree ​

SplayTree<T> es un conjunto ordenado implementado sobre un árbol de splay autoadaptativo. Cada acceso mueve el elemento a la raíz mediante una secuencia de rotaciones, por lo que los elementos recién accedidos son más baratos de alcanzar de nuevo. Las operaciones son logarítmicas amortizadas. El handle nativo se libera automáticamente cuando la variable sale del ámbito.

Construcción ​

SintaxisDescripción
SplayTree<T>()Crea un nuevo árbol de splay vacío

T puede ser cualquier tipo entero, cualquier tipo de punto flotante, boolean o string.

Métodos ​

MétodoFirmaRetornaDescripción
insert(T) => voidvoidAgrega un elemento; los duplicados se ignoran
contains(T) => booleanbooleanSi el elemento está en el árbol
len() => usizeusizeNúmero de elementos
isEmpty() => booleanbooleanSi el árbol está vacío

Complejidad ​

OperaciónComplejidad Temporal
insertO(log n) amortizado
containsO(log n) amortizado
len / isEmptyO(1)

Una sola operación puede tocar todos los nodos, pero una secuencia de m operaciones sobre un árbol de n elementos siempre se ejecuta en O(m log n): el costo amortizado de cada operación es O(log n), y los patrones de acceso con localidad temporal son incluso más rápidos en la práctica.

Ejemplos ​

Ejemplo completo ​

tyrus
import { SplayTree } from "tyrus:algorithm";

const main = (): void => {
    const t = SplayTree<i32>();
    print(t.isEmpty());  // true

    t.insert(5);
    t.insert(3);
    t.insert(8);
    t.insert(3);  // duplicate, ignored

    print(t.len());        // 3
    print(t.contains(3));  // true
    print(t.contains(4));  // false
};