[Verse 1] When your binary search tree gets unbalanced and slow Heights differ by more than one, that's when you know Left-heavy or right-heavy, the structure's gone wrong Time to rotate and fix it, let's sing this song Check the balance factor, negative two or plus two That's your signal to rotate, here's what you do Single rotation first, then we'll learn the double Keep your tree balanced, avoid search trouble [Chorus] Left-left case, rotate right Right-right case, rotate left tonight Left-right case, double spin around Right-left case, balance can be found AVL rotations keep the height in check Log n performance, no more tree wreck Remember the patterns, sing it loud and clear Balanced search trees, efficiency's here [Verse 2] Single right rotation when the left side's too tall Take the left child, make it parent of all Original root becomes the right child now Left subtree stays, right subtrees somehow Switch positions cleanly, maintain BST order Height gets balanced, crossing the border From unbalanced chaos to structured delight One simple rotation makes everything right [Chorus] Left-left case, rotate right Right-right case, rotate left tonight Left-right case, double spin around Right-left case, balance can be found AVL rotations keep the height in check Log n performance, no more tree wreck Remember the patterns, sing it loud and clear Balanced search trees, efficiency's here [Verse 3] But sometimes single rotation just won't do the trick Left-right pattern means you need a double fix First rotate left on the left child node Then rotate right on root, follow the code Right-left pattern works the mirror way Right rotate first, then left saves the day Two rotations working as a team Keeping AVL trees living the dream [Bridge] Balance factor is the key to know Left height minus right, watch how it goes Minus one, zero, plus one, you're fine Outside that range, it's rotation time Insert and delete, check every node up Propagate changes, fill balance cup AVL invariant, height difference bound Logarithmic search time, performance sound [Chorus] Left-left case, rotate right Right-right case, rotate left tonight Left-right case, double spin around Right-left case, balance can be found AVL rotations keep the height in check Log n performance, no more tree wreck Remember the patterns, sing it loud and clear Balanced search trees, efficiency's here [Outro] Four cases total, learn them by heart Single and double, playing their part AVL trees keep your data in line Rotations working, performance divine
← Binary search tree operations | Red-black tree balancing →