An AVL Tree is a type of binary search tree that auto balances according to the height. To recap, binary trees consist of nodes that can have up to two children nodes and a data field, and are ordered so that the left child is always less than the parent, and the right child is greater than the parent.
Insertion and deletion are the same as in a binary search tree. To insert a node, you compare the data to each node in the tree, traversing down subtrees depending on how they compare. To delete, you replace the node with the in order successor or simply sever the leaf.
An important part of an AVL Tree is the balancing factor, which describes the difference in the height of the left and the right subtree. Recall that the height is the amount of edges from the node to the deepest node.
We define the balancing factor to be:
If the balancing factor is greater than 1 or less that -1, then our tree is heavy on one side. To fix this, AVL trees use rotations to shift the nodes from a height of two to a height of one.
1. Left Left Rotation:
2. Left Right Rotation:
3. Right Right Rotation
4. Right Left Rotation
Right left and left right rotations are a combination of the LL and RR rotations
Check out rotations in this visualizer: https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
(Try inserting 1,2,3!)
