The Red-Black Tree Song
[To the Tune of Paint It Black, with my utmost apologies to the rolling stones]
I see a brand new nodei want to pieint it black.
We need a balanced tree, We've Got To Paint It Black.
I want to find my key in log n time - That, Rotating Sub-Trees' Round Sure Can Be A Ball.
I see a brand new nodei want to pieint it black.
Can't Have a Lot of Red Nodes, WE Must Paint Them Black.
Unfortunately, coding them can be a bitch.If we had half a brain to splay trees we would switch.
I see a brand new nodei want to pieint it black.
No Time for AVL TREESWE MUST PAINT It Black.
And if The're Still Confusing, You Should Have No Fear.Because Outside This Class, of Them You'll Never Hear.
I Wanna Paint 'Em Black. Paint Nodes Black. Again and Again.
Copyright 1995 Sean D. Sandys. You May Link to this Page Butbook. Reproduce ITHOR's Written Permission.
