Script – Self Balancing AVL Trees

Well, a few days back, I learnt about the amazing self-balancing trees. There are many different kinds of self balancing trees, the 2-3-4 Tree, the Red-Black Tree, many kinds. Read more

But out of all of them, the AVL Tree seems to be the only one that I can quite fully understand. I might try out other implementations, but this will do for now. I have yet to add in the function to delete a node, but I might add that in later.

On hindsight, I should have went allow with the implementation that make use of the height to balance the tree, instead of the method of maintaining a balance counter.

For those seeking to understand how the tree works, here is an explanation on how this method works. There is a bit of math involved, especially in the part where the tree is rotate. The algorithm for updating the balancing when deleting nodes are not provided.

After trying to implement the delete function for the balance method as described above, and failing terribly, I implemented another version which recalculates the height everything the balance is used. It is a much simpler method, though not as effective. But for those who are trying to understand how all of these works, it is a very good way to start.