C-AVL-tree.asc

Appendix A: AVL Tree

AVL Tree is named after their inventors (Adelson-Velsky and Landis). This self-balancing tree keeps track of subtree sizes to know if a rebalance is needed or not. We can compare the size of the left and right subtrees using a balance factor.

Note	The balanced factor on each node is calculated recursively as follows: Balance Factor = (left subtree height) - (right subtree height)

The implementation will go in the BST node class. We will need two methods to calculate the left and right subtree, and with those, we can get the balance factor.

Balance Factor methods on the BST node

link:../src/data-structures/trees/binary-tree-node.js[role=include]

Implementing AVL Tree

Implementing an AVL Tree is not too hard since it builds upon what we did in the Binary Search Tree.

AVL Tree class

link:../src/data-structures/trees/avl-tree.js[role=include]

As you can see, the AVL tree inherits from the BST class. The insert and remove operations work the same as in the BST, except that at the end we call balanceUpstream. This function checks if the tree is symmetrical after every change to the tree. If the tree went out of balance, it would execute the appropriated rotation to fix it.

Balance Upstream for AVL tree

link:../src/data-structures/trees/avl-tree.js[role=include]

This function recursively goes from the modified node to the root checking if each node in between is balanced. Now, let’s examine how does the balancing works on AVL tree.

Balance method for AVL tree

link:../src/data-structures/trees/avl-tree.js[role=include]

The first thing we do is to see if one subtree is longer than the other. If so, then we check the children balance to determine if need a single or double rotation and in which direction.

You can review [tree-rotations] in case you want a refresher.