Red-Black Tree

A Red-Black Tree is a self-balancing binary search tree where each node has an additional color property (red or black). The tree maintains balance through five key properties: the root is always black, all leaves (null nodes) are black, red nodes cannot have red children, and every path from a node to its descendant leaves contains the same number of black nodes. These rules ensure that the tree remains approximately balanced, guaranteeing O(log n) time complexity for search, insert, and delete operations.