This has definitely been the hardest one so far; I remembered the traumatic experience since the university time and also remembered why I hid it deep down.
You can check the glorious Wikipedia for the full description of the AVL trees, no need for me to repeat it there. I will however list some of the key points I found while implementing it:
- draw the thing down. It is the best help you can get while your brain tries to make sense of this magic rocket science
- TRACK THE HEIGHT, COMPUTE THE BALANCE. This kept me stuck for eons, maybe it's possible to track the balance only as well and perform some more complex update logic, but I have no intention of going down the rabbit hole again for the moment :)
- after inserting a node, backtrack to the root and perform rotations as needed. Update the heights while backtracking
- not everyone defines right and left rotations the same way. Sometimes they are inverted in the directions they will actually rotate; end result in balancing terms is the same but naming might cause confusion. For me right rotate means: take the node, pull it down right and set his left child as parent. So for me: balance -2 means left heavy therefore a right (or right-left) rotation is needed
Lastly, I also link this super useful tool I found that helps with understanding the logic and checking the correctness of the results form the code: online AVL tree visualization
