Exploring another self-balancing BST that uses node coloring to ensure balance.
Red-Black Trees are another type of self-balancing binary search tree that uses a clever coloring scheme to ensure the tree remains balanced during insertions and deletions. Each node in the tree is colored either 'red' or 'black' and must adhere to a specific set of rules: 1. Every node is either red or black. 2. The root is always black. 3. Every leaf (NIL node) is black. 4. If a node is red, then both its children are black. 5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes. These rules collectively ensure that the longest path from the root to any leaf is no more than twice as long as the shortest path. This property guarantees a height of O(log n), ensuring logarithmic time complexity for search, insert, and delete operations. Compared to AVL trees, Red-Black Trees are less strictly balanced but require fewer rotations on average during modifications. This makes them slightly faster for insertions and deletions, while searches might be marginally slower. Because of this trade-off, Red-Black Trees are widely used in practice, for example, in C++'s `std::map` and `std::set` and Java's `TreeMap` and `TreeSet`.