Skip to content

Treap ​

Treap<T> es un conjunto ordenado implementado sobre un treap aleatorio: un árbol binario de búsqueda en el que cada nodo también lleva una prioridad aleatoria y el árbol está ordenado por montículo según esa prioridad. La aleatoriedad mantiene el árbol equilibrado en expectativa para cualquier secuencia de inserciones. El handle nativo se libera automáticamente cuando la variable sale del ámbito.

Construcción ​

SintaxisDescripción
Treap<T>()Crea un nuevo treap 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) esperado
containsO(log n) esperado
len / isEmptyO(1)

Las prioridades aleatorias mantienen el árbol equilibrado en expectativa, por lo que toda operación es logarítmica para cualquier entrada, incluidos los datos preordenados.

Ejemplos ​

Ejemplo completo ​

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

const main = (): void => {
    const t = Treap<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
};