Skip to content

SplayTree ​

SplayTree<T> é um conjunto ordenado implementado sobre uma árvore de splay autoadjustável. Cada acesso move o elemento para a raiz por uma sequência de rotações, então elementos acessados recentemente ficam mais baratos de alcançar de novo. As operações são logarítmicas amortizadas. O handle nativo é liberado automaticamente quando a variável sai de escopo.

Construção ​

SintaxeDescrição
SplayTree<T>()Cria uma nova árvore de splay 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) amortizado
containsO(log n) amortizado
len / isEmptyO(1)

Uma única operação pode tocar todos os nós, mas uma sequência de m operações sobre uma árvore de n elementos sempre roda em O(m log n): o custo amortizado de cada operação é O(log n), e padrões de acesso com localidade temporal são ainda mais rápidos na prática.

Exemplos ​

Exemplo completo ​

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

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