Red-black trees are a type of self-balancing [[binary search tree]]. Red-black trees encode one extra bit of information for each node, whether it is "red" or "black". The rules for coloring nodes in a red-black tree are 1. Root and leaves (NIL values) are black 2. If a node is red, both its children are black 3. The black-height is well defined for every node, which is to say the number of black nodes along every path starting from the node has the same number of black nodes These rules ensure that the heigh of a red-black tree $h$ is $\log_2 n \le h \le 2(\log_2 n)$. Find is the same in red-black trees as binary search trees. The challenge is maintaining the red-black tree properties on insert and delete. To insert an element, use the same algorithm as for binary search trees and assign it the color red. If the parent is also red, which violates the red-black tree property (a "red-red violation"), recolor the tree. If the "uncle" of the inserted element is also red, then swap the colors of the inserted element's grandparent, parent and uncle recursively until the red-red violation is addressed or in the worst case "ejected" through the root of the tree. If the "uncle" of the inserted element is black, complete tree rotation(s) to rebalance the trees. The implementations of insert and delete are complex, look up their implementations if needed in a book on algorithms. # tree rotations Tree rotations are used to rebalance red-black trees while maintaining their important properties. Rotations are either clockwise (right) or counterclockwise (left). Consider the tree with two nodes $x$ and $y$ and subtrees $a$, $b$, and $c$ where $x < y$. ```mermaid flowchart TB y --> x & c[/c\] x --> a[/a\] & b[/b\] ``` In a clockwise rotation, the nodes $x$ and $y$ are swapped and the subtree $b$ is reassigned as the left child of $y$. ```mermaid flowchart TB x --> a[/a\] & y y --> b[/b\] & c[/c\] ``` In a counterclockwise rotation, the operation is the exact reverse to restore the original tree.