This is a fork of https://github.com/brianshannan/nim-trees with some modernization. I merged in https://github.com/dcurrie/nim-bbtree, also.

All mutable trees (AVL, RedBlack, Splay, WAVL) share a consistent API:

All trees support order statistics via rank and select:

• select(i) returns the ith smallest item (0-indexed). Negative indices count from the end: select(-1) returns the largest item.
• rank(key) returns the 0-indexed position of key in sorted order.

var tree: AVLTree[int, string]
tree.insert(10, "ten")
tree.insert(5, "five")
tree.insert(15, "fifteen")

echo tree.select(0)   # (5, "five")   - smallest
echo tree.select(1)   # (10, "ten")   - middle
echo tree.select(-1)  # (15, "fifteen") - largest
echo tree.rank(10)    # 1

AVL trees are strictly balanced binary search trees.

Virtues:

• Fastest lookups due to strict balancing (height ≤ 1.44 log₂(n))
• Predictable O(log n) worst-case for all operations
• Best choice for read-heavy workloads

Drawbacks:

• More rotations on insert/delete than Red-Black or WAVL
• Slightly slower writes than Red-Black trees

Complexity: O(log n) insert, remove, find; O(n) space and iteration.

Algorithm adapted from Wikipedia.

Red-Black trees are balanced binary search trees with relaxed balancing.

Virtues:

• Fewer rotations than AVL on insert/delete
• Good all-around performance for mixed workloads
• Widely used in standard libraries (C++ std::map, Java TreeMap)

Drawbacks:

• Slightly slower lookups than AVL (height ≤ 2 log₂(n))
• More complex implementation

Complexity: O(log n) insert, remove, find; O(n) space and iteration.

Algorithm adapted from CLRS.

WAVL (Weak AVL) trees use rank differences instead of balance factors.

Virtues:

• At most 2 rotations per insert or delete (vs O(log n) for AVL delete)
• Without deletions, equivalent to AVL trees
• All WAVL trees are valid Red-Black trees
• Good balance between AVL strictness and Red-Black flexibility

Drawbacks:

• Slightly more complex than AVL or Red-Black
• Less widely known/documented

Complexity: O(log n) insert, remove, find; O(n) space and iteration.

Algorithm adapted from Wikipedia.

Splay trees are self-adjusting binary search trees that move accessed nodes to the root.

Virtues:

• Excellent cache locality for repeated access patterns
• Amortized O(log n) without storing balance information
• Recently accessed items are O(1) to access again
• Simpler implementation than balanced trees

Drawbacks:

• O(n) worst-case for individual operations
• Mutates tree structure on reads (not thread-safe for concurrent reads)
• Poor performance with uniform random access patterns

Complexity: Amortized O(log n) insert, remove, find; O(n) space and iteration.

Additional API:

• peek(key): (V, bool) - Query without splaying (const operation)

Algorithm adapted from Wikipedia.

BBTrees (Bounded Balance Trees), also known as Weight Balanced Trees or Adams Trees, are a persistent (immutable) data structure.

Virtues:

• Persistent/immutable: operations return new trees, old versions preserved
• Thread-safe without locks (immutable)
• Rich set operations (union, intersection, difference)
• O(log n) order statistics (getNth, rank)
• Functional programming friendly

Drawbacks:

• Higher memory allocation (creates new nodes on modification)
• Different API than mutable trees (functions take and return trees)
• No in-place mutation

Complexity: O(log n) insert, remove, find, getNth, rank; O(n) space and iteration; O(m + n) for set operations.

BBTree uses a functional style where operations return new trees:

# Successor/predecessor
getNext(tree, key, default)  # smallest key > key
getPrev(tree, key, default)  # largest key < key

# Set operations
union(tree1, tree2)
intersection(tree1, tree2)
difference(tree1, tree2)
symmetricDifference(tree1, tree2)

# Set predicates
isSubset(tree1, tree2)
isProperSubset(tree1, tree2)
disjoint(tree1, tree2)
setEqual(tree1, tree2)

# Operators
tree1 + tree2   # union
tree1 * tree2   # intersection
tree1 - tree2   # difference
tree1 -+- tree2 # symmetric difference
tree1 < tree2   # proper subset
tree1 <= tree2  # subset
tree1 =?= tree2 # set equality

# Functional operations
map(tree, proc(k, v): T)
fold(tree, proc(k, v, acc): T, init)
toSet(keys)  # create set from array

# Additional iterators
inorder(tree)   # alias for pairs
revorder(tree)  # reverse order

• Adams, Implementing Sets Efficiently in a Functional Language, CSTR 92-10
• Straka, Adams' Trees Revisited, 2011
• Weight-balanced trees on Wikipedia

• AVL, Red-Black, Splay, WAVL: Apache-2.0
• BBTree: MIT