[Verse 1]
Started with a binary tree but it got unbalanced
Height was growing wild, performance got damaged
Left side heavy, right side light
Searches taking way too long into the night
Then I learned about a better way to code
Red and black nodes following a special mode
Self-balancing structure keeps things in line
Every operation running in logarithmic time
[Chorus]
Red node parent must be black, that's the rule
Uncle red means recolor, that's the tool
Uncle black means rotation time
Left or right to keep the tree in prime
Black height equal on every path
Red-black balancing, do the math
No red-red connections allowed
Keep it balanced, make it proud
[Verse 2]
Insertion starts just like BST
Find the spot and place the node carefully
Color it red, that's the starting way
But now the properties might break today
Check the parent, is it red as well?
If so we got violations to dispel
Look up to grandpa, check the uncle too
Their colors determine what we're gonna do
[Chorus]
Red node parent must be black, that's the rule
Uncle red means recolor, that's the tool
Uncle black means rotation time
Left or right to keep the tree in prime
Black height equal on every path
Red-black balancing, do the math
No red-red connections allowed
Keep it balanced, make it proud
[Bridge]
Left-left case, rotate right
Right-right case, rotate left tonight
Left-right case, double rotation flow
Right-left case, let the spinning go
Root stays black, that never changes
Nil nodes black through all the ranges
[Verse 3]
Deletion's trickier than insert for sure
Find the node and check what to endure
If it's red just remove with ease
Black node gone puts balance in freeze
Double black bubble needs fixing fast
Sibling cases make the solution last
Push the blackness up the tree
Till the root absorbs it finally
[Chorus]
Red node parent must be black, that's the rule
Uncle red means recolor, that's the tool
Uncle black means rotation time
Left or right to keep the tree in prime
Black height equal on every path
Red-black balancing, do the math
No red-red connections allowed
Keep it balanced, make it proud
[Outro]
Five properties keep the structure tight
Logarithmic height is our delight
From root to leaf the black count's same
Red-black trees mastered in this game