[Verse 1]
Started with a binary search tree, nodes scattered wild
Data getting lopsided, performance exiled
Rudolf Bayer had a vision back in seventy-two
Color-coded balancing, red and black debut
Every node gets painted, no exceptions here
Red or black decisions keep the structure clear
Root stays black forever, that's rule number one
Leaves are black and empty when insertion's done
[Chorus]
Red-black rules, remember these four
Black root foundation, red kids no more
Red nodes spawn black children, that's the law
Black height uniform, balance restored
Rotate and recolor when violations appear
Red-black tree magic keeps the data near
[Verse 2]
Insertion starts simple, paint the new node red
Check your parent's color, might need surgery instead
Double red disaster breaks our sacred code
Uncle node's the witness, determines fix mode
Red uncle means recoloring up the chain
Black uncle needs rotation to ease the strain
Left-left case means right rotate around
Grandparent becomes child, balance found
[Chorus]
Red-black rules, remember these four
Black root foundation, red kids no more
Red nodes spawn black children, that's the law
Black height uniform, balance restored
Rotate and recolor when violations appear
Red-black tree magic keeps the data near
[Bridge]
Deletion's trickier, replacement node's key
Copy the value, then delete carefully
Red nodes vanish easy, no black height change
Black nodes disappear, siblings rearrange
Double black phantom needs attention fast
Recolor or rotate until rules hold fast
[Verse 3]
AVL trees count height with precision tight
Red-black approximates, still gets it right
Logarithmic searching guaranteed to stay
Even with a million nodes in your array
Self-balancing sorcery, automation prime
Insert and delete in optimal time
[Outro]
From crimson violations to obsidian peace
Red-black tree balancing will never cease
Four simple rules maintain the equilibrium
Data structure mastery, your algorithm