Every node is RED or BLACK. Five color rules together force the longest root-to-leaf path to be at most twice the shortest, so height stays O(log n). Insert starts the new node RED, then recolors or rotates to fix any violations.
Insert
Search
Presets
Normal
0
Nodes
0
Height
-
Black-Height
-
Min Possible
Try it: Insert 10, 20, 30, 40, 50 one at a time. Watch how reds flip to black and how rotations straighten zig-zags. Notice the root is always black.