Red Black Tree

Preserve black height and avoid red-red links

A red-black tree is a BST where the root is black, null leaves are black, red nodes have black children, and every root-to-leaf path has equal black count. Insert like a normal BST and color the new node red. If parent and child are both red, inspect the uncle: recolor when it is red; otherwise rotate and recolor around the grandparent, handling inner and outer shapes. These local repairs preserve ordering and restore the invariants. The height stays O(log n), so search, insert, and delete are O(log n); nodes require O(n) storage. Explain deletion needs an extra-black fix-up and is more involved. Test root insertion, red uncle recoloring, both rotation directions, duplicate-key policy, and null sentinels.