Skip to content

AvlTree ​

AvlTree<T> is an ordered set backed by a self-balancing AVL tree. Every insertion rebalances the tree so that the two subtrees of any node differ by at most one level in height, which guarantees logarithmic operations in the worst case. The native handle is released automatically when the binding goes out of scope.

Construction ​

SyntaxDescription
AvlTree<T>()Create a new empty AVL 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 strict height invariant makes the worst case as fast as the average case: every operation is logarithmic regardless of insertion order.

Examples ​

Complete example ​

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

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