[Verse 1]
Started with a binary search tree, but it wasn't balanced right
Worst case linear time, got me coding through the night
Then I found the red-black tree, revolutionary design
Self-balancing algorithm, keeping search time in line
Every node is colored red or black, that's the foundation
Four rules keep it balanced through every operation
Root is always black, that's rule number one
Red nodes got black children, before we're done
[Chorus]
Red-black balance, keep the height in check
Logarithmic time, that's what we expect
No red-red parent-child, black height stays the same
Four rules to remember, master this game
Red-black balance, rotation is key
Left and right turns, keep the tree free
Insert and delete, colors might change
But the rules stay constant, never rearrange
[Verse 2]
Rule three says red nodes can't have red kids
Black parent required, that's how balance lives
Rule four's the deepest, black height must be equal
Every path to nil nodes, same black count sequel
Insert a new node, color it red first
Check the rules, see if any are cursed
If parent's red too, we got violation
Time for rotations and recoloration
[Chorus]
Red-black balance, keep the height in check
Logarithmic time, that's what we expect
No red-red parent-child, black height stays the same
Four rules to remember, master this game
Red-black balance, rotation is key
Left and right turns, keep the tree free
Insert and delete, colors might change
But the rules stay constant, never rearrange
[Bridge]
Uncle node is black, rotate and recolor
Uncle node is red, color up the collar
Left-left case, single right rotation
Right-right case, mirror that creation
Left-right combo, double rotation flow
Right-left pattern, that's how we go
[Verse 3]
Deletion's trickier, cases multiply
Replace with successor, don't ask me why
If we delete black, black height decreases
Fixup procedure, problems it releases
Double black phantom, traveling up the tree
Rotations and colors set the structure free
Time complexity guaranteed log n height
Red-black trees keep performance tight
[Outro]
From insertion to deletion, rules never break
Self-balancing beauty, for performance sake
Red-black mastery, algorithm complete
Data structure champion, can't be beat