Skip to content

Treap ​

Treap<T> is an ordered set backed by a randomized treap: a binary search tree where each node also carries a random priority and the tree is heap-ordered by that priority. The randomness makes the tree balanced on expectation for any insertion sequence. The native handle is released automatically when the binding goes out of scope.

Construction ​

SyntaxDescription
Treap<T>()Create a new empty treap

T can be any integer type, any float type, boolean, or string.

Methods ​

MethodSignatureReturnsDescription
insert(T) => voidvoidAdd an element; duplicates are ignored
contains(T) => booleanbooleanWhether the element is in the tree
len() => usizeusizeNumber of elements
isEmpty() => booleanbooleanWhether the tree is empty

Complexity ​

OperationTime Complexity
insertO(log n) expected
containsO(log n) expected
len / isEmptyO(1)

The random priorities make the tree balanced on expectation, so every operation is logarithmic for any input, including pre-sorted data.

Examples ​

Complete example ​

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