RedBlackTree
RedBlackTree<T> is an ordered set backed by a self-balancing red-black tree. Nodes are colored red or black under invariants that keep every root-to-leaf path at most twice as long as any other, which guarantees logarithmic operations in the worst case. The native handle is released automatically when the binding goes out of scope.
Construction
| Syntax | Description |
|---|---|
RedBlackTree<T>() | Create a new empty red-black tree |
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) worst case |
contains | O(log n) worst case |
len / isEmpty | O(1) |
The coloring invariants keep the tree balanced, so every operation is logarithmic regardless of insertion order.
Examples
Complete example
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
};