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
| Syntax | Description |
|---|---|
Treap<T>() | Create a new empty treap |
T can be any integer type, any float type, boolean, or string.
Methods
| Method | Signature | Returns | Description |
|---|---|---|---|
insert | (T) => void | void | Add an element; duplicates are ignored |
contains | (T) => boolean | boolean | Whether the element is in the tree |
len | () => usize | usize | Number of elements |
isEmpty | () => boolean | boolean | Whether the tree is empty |
Complexity
| Operation | Time Complexity |
|---|---|
insert | O(log n) expected |
contains | O(log n) expected |
len / isEmpty | O(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
};