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.

EDIT:
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.

Advertisements