I need some guidance regarding AVL Trees. So far, I have created a binary tree library. For the next step, I want to use this btree source code to make it into an AVL tree. I have studied Prelude's AVL Tutorial on her webpage and I understand the rotations part. However, I need some assistance on how to know when to do a rotation. I know I need to add a "balance" variable to each node. Also that I need to modify my insert function to automatically perform rotations. I plan to insert normally, then do a tree traversal that will update balance factors. When out of balance is detected I run a rotation but how do I know which one is needed (single, double, left, right) ?
This whole thing is confusing as heck.