Skip to content

RedBlackTree ​

RedBlackTree<T> es un conjunto ordenado implementado sobre un árbol rojo-negro autoequilibrado. Los nodos se colorean de rojo o negro bajo invariantes que mantienen todo camino desde la raíz hasta una hoja con a lo sumo el doble del largo de cualquier otro, lo que garantiza operaciones logarítmicas en el peor caso. El handle nativo se libera automáticamente cuando la variable sale del ámbito.

Construcción ​

SintaxisDescripción
RedBlackTree<T>()Crea un nuevo árbol rojo-negro 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) en el peor caso
containsO(log n) en el peor caso
len / isEmptyO(1)

Los invariantes de coloración mantienen el árbol equilibrado, por lo que toda operación es logarítmica independientemente del orden de inserción.

Ejemplos ​

Ejemplo completo ​

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

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