Skip to content

AvlTree ​

AvlTree<T> é um conjunto ordenado implementado sobre uma árvore AVL autobalanceada. Cada inserção rebalanceia a árvore para que as duas subárvores de qualquer nó difiram em no máximo um nível de altura, o que garante operações logarítmicas no pior caso. O handle nativo é liberado automaticamente quando a variável sai de escopo.

Construção ​

SintaxeDescrição
AvlTree<T>()Cria uma nova árvore AVL vazia

T pode ser qualquer tipo inteiro, qualquer tipo de ponto flutuante, boolean ou string.

Métodos ​

MétodoAssinaturaRetornaDescrição
insert(T) => voidvoidAdiciona um elemento; duplicatas são ignoradas
contains(T) => booleanbooleanSe o elemento está na árvore
len() => usizeusizeNúmero de elementos
isEmpty() => booleanbooleanSe a árvore está vazia

Complexidade ​

OperaçãoComplexidade Temporal
insertO(log n) no pior caso
containsO(log n) no pior caso
len / isEmptyO(1)

O invariante estrito de altura faz o pior caso ser tão rápido quanto o caso médio: toda operação é logarítmica independentemente da ordem de inserção.

Exemplos ​

Exemplo 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
};