Skip to content

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 ​

SyntaxDescription
RedBlackTree<T>()Create a new empty red-black tree

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) worst case
containsO(log n) worst case
len / isEmptyO(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
};