Skip to content

SplayTree ​

SplayTree<T> is an ordered set backed by a self-adjusting splay tree. Every access moves the element to the root through a sequence of rotations, so recently accessed elements become cheaper to reach again. Operations are amortized logarithmic. The native handle is released automatically when the binding goes out of scope.

Construction ​

SyntaxDescription
SplayTree<T>()Create a new empty splay 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) amortized
containsO(log n) amortized
len / isEmptyO(1)

A single operation can touch every node, but a sequence of m operations on a tree of n elements always runs in O(m log n): the amortized cost of each operation is O(log n), and access patterns with temporal locality are even faster in practice.

Examples ​

Complete example ​

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

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