LLRB

Left-leaning Red-Black Tree, abbreviated LLRB, is a form of self-balancing binary search tree designed to implement ordered maps and sets. It was introduced as a simplification of the classic red-black tree, encoding a 2-3 tree with binary links and a color bit on each edge. This representation yields a BST interface with balanced height and predictable performance.

The structure relies on color bits and a set of invariants. Each node has a color, red or black. The root is black. Red links are used to form temporary 3-nodes and must lean left, meaning there are no right-leaning red links. A node cannot have two red links incident to it along a path. All paths from the root to the leaves contain the same number of black links, ensuring balanced height across the tree.

Insertion and deletion are implemented to preserve these invariants. Insertion follows a standard BST insert, followed by rotations (left and right) and color flips to fix right-leaning links and split temporary 4-nodes into two 2-nodes. Deletion, including deleteMin and delete, is more intricate but maintains the left-leaning and color-invariant properties. As with other balanced BSTs, operations have worst-case time complexity of O(log n), with space complexity primarily due to recursion or iterative pointer storage.

LLRBs reflect a close relationship to 2-3 trees: red links represent 3-nodes, while black links connect 2-nodes. They are used for implementing ordered symbol tables and other map-like structures, offering simpler code relative to some red-black variants while delivering comparable performance characteristics.