Skip to content

AvlTree ​

AvlTree<T> es un conjunto ordenado implementado sobre un árbol AVL autoequilibrado. Cada inserción reequilibra el árbol para que los dos subárboles de cualquier nodo difieran en a lo sumo un nivel de altura, 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
AvlTree<T>()Crea un nuevo árbol AVL 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)

El invariante estricto de altura hace que el peor caso sea tan rápido como el caso promedio: toda operación es logarítmica independientemente del orden de inserción.

Ejemplos ​

Ejemplo completo ​

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

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