Skip to content

RedBlackTree ​

RedBlackTree<T> é um conjunto ordenado implementado sobre uma árvore rubro-negra autobalanceada. Os nós são coloridos de vermelho ou preto sob invariantes que mantêm todo caminho da raiz até uma folha com no máximo o dobro do comprimento de qualquer outro, 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
RedBlackTree<T>()Cria uma nova árvore rubro-negra 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)

Os invariantes de coloração mantêm a árvore balanceada, então toda operação é logarítmica independentemente da ordem de inserção.

Exemplos ​

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