Skip to content

Treap ​

Treap<T> é um conjunto ordenado implementado sobre um treap aleatório: uma árvore binária de busca em que cada nó também carrega uma prioridade aleatória e a árvore é ordenada por heap conforme essa prioridade. A aleatoriedade mantém a árvore balanceada em expectativa para qualquer sequência de inserções. O handle nativo é liberado automaticamente quando a variável sai de escopo.

Construção ​

SintaxeDescrição
Treap<T>()Cria um novo treap vazio

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) esperado
containsO(log n) esperado
len / isEmptyO(1)

As prioridades aleatórias mantêm a árvore balanceada em expectativa, então toda operação é logarítmica para qualquer entrada, inclusive dados pré-ordenados.

Exemplos ​

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