The Case Balanced (AVL) Binary Search Tree - Eishaaya/GMRDataStructuresTest GitHub Wiki
The cool thing about binary search trees is that provided they are properly filled, search time goes down from the worst case scenario of O(n) to optimal O(log(n)). However, this is in the theoretical situation, often trees end up looking like linked lists, with one side heavily outweighing the other. This results in a much less efficient search and making the binary search tree useless. We prevent this by balancing each side of the tree with rotations. Named after the inventors (Adelson, Velski & Landis) an AVL tree seeks to make the tree as balanced as possible so that the average search, insert and delete time is O(log(n)).
Here are some examples of balanced trees and unbalanced trees:
Unbalanced Trees
|
|
|
Balanced Trees
|
|
See the difference? The main difference is how long it takes to access any given node in the tree. The balanced trees have a much faster "finding time" then the non-balanced ones. Therefore, in order to minimize the amount of time spent searching, we need to find an easy way of balancing our tree. As noted in the BST example, deleting the set and reentering the information is incredibly slow when we can just sort according to certain rules when we add to the tree. This is accomplished by rotating nodes based on their height and balance.
Unlike the binary search tree, AVL should be implemented using recursion for the add, remove, contains and the traversal functions.
Node class will have much of the same information that was contained inside the binary search tree's node class. We maintain fields for value, left node, right node, child count, height and balance.
Height is a measurement of how far a node is away from a leaf node (a leaf node being a node with no children). The height of a leaf node is 1 and a the height of a non-leaf node is 1 + distance away from the furthest leaf node. This means if a node has a left child with a height of 2 and a right child with a height of 3, its height would be 4 because it's height is 1 greater than the child with the greatest height.
Example:
Balance is a measurement of how many number of nodes are on each side of the root or subtrees. This value operates as a scale, ensuring that each side is structured in such a way that is optimal for finding nodes. The only balances that are acceptable are -1, 0 and 1. This is calculated by subtracting the height of the left child from the height of the right child or more simply (rightNode.Height - leftNode.Height). Lastly, it is important to note that a null left or right child has a height of 0.
Rotations are a term given to how to re-balance a given tree once we know that it is not balanced. HINT: if the tree is leaning towards the right side, it will have a balance of > 1, which means that nodes need to be rotated to the respective left subtree. A left rotate would be rotating the elements around the middle node (the one which is unbalanced) exactly once so the parent of the middle becomes the child of its child. A right rotate would be a similar movement but in the opposite way. A right rotation would occur when there are too many elements on the left side. In this way, an AVL tree can always balance itself with these rotations after insert and will not require reinsertion in order to optimize the search time.
Inserting a value into an AVL tree is similar to inserting into a binary search tree. The only difference being that after the insertion, we have to update the height of the parent node, and we also have to balance the parent node if needed.
Balancing the node only needs to be done if the balance is < -1 or > 1, and within those sub cases, we also need to handle the case of a double rotation such as a left-right or a right-left rotation.
|
|
|
See the visualizer for more examples of what a rotation is and how it would be applied to any situation
Double Rotations
Sometimes a single rotation is not sufficient to balance an unbalanced tree. Take this situation for example. The tree has a balance of +2, but a single rotate left would land us with a balance of -2:
The solution to this is to do a left-right rotation. In order to do this, we perform a right rotation on the right subtree (so perform a right rotate on 'c'), then perform the original left rotate. As such:
What causes this problem? This is due to the right subtree having a negative balance. In other words, because the right subtree was left heavy. This method can be repeated inversely with a right-left rotation. This is done by performing a left rotation on the left subtree, then a right rotation on the original unbalanced node.
Delete
Delete follows the same principles as the BST with the exception of the rotations that AVL has (provided your re-balancing and rotations work correctly). Simply reapply the balancing and rotations that you did in add after you remove a node from the tree.
-
Recursive Functions: Redo some of the following functions using recursion now that the tree is self sorting.
- Depth-First Search (PreOrder, PostOrder, InOrder)
- Bonus: Explain to an instructor why recursion is bad for a binary search tree, but is good with an AVL tree.
-
Remove the Parents
- Parent pointers aren't actually required. See if you can rewrite the AVL tree without having parent pointers.
- Take a look at our implementation if you are stuck.