An AVL tree is a type of binary search tree which guarantees fast insertions and lookups. In this article, we'll outline the concepts behind AVL trees, then introduce the AVL tree itself, provide some code examples, and lastly, provide a full code implementation in multiple languages.
Binary Search Trees
An AVL Tree is a type of binary search trees. If you are not familiar with binary search trees, or would like to learn more about them please visit our introduction to binary search trees. Otherwise, we will proceed to introduce some new concepts below.
Tree Height and Balance
A tree's height is the length of the longest downward path from the root node to a leaf node. The height of an individual node is the length of the longest downward path from that node (thus, the height of a tree equals the height of its root node).
A node's balance is the difference in heights between its left child node and right child node. If it doesn't have a left and/or right node, the height for the missing node can be considered as 0 for calculation purposes. The list below shows three different types of balances and the meaning behind them. We will consider H(left) to be the height of the left child, or 0 if there is none, and H(right) for the right child.
- Balance is 0:
H(left) = H(right)
- Balance is x:
H(left) = H(right) + x
. The left side has a larger height. - Balance is -x:
H(left) = H(right) - x
. The right side has a larger height.
The node's height can be calculated via: Math.max(H(left), H(right)) + 1
.
Self Balancing Binary Search Tree
A self balancing binary search tree is a type of binary search tree where the balance of each node is -1, 0, or 1. (The range may be larger in certain types of self balancing binary search trees, but we will not cover that in this article). In order to preserve this property, the tree implementation will need to take some type of action when items are inserted or removed. For this article, we will analyze and implement an AVL tree, a common type of self balancing binary search tree.
Without balancing, a binary search tree will have a worst case time complexity of O(n)
, which means that inserting, deleting, or looking for an item could take up to n traversals and comparisons, where n is the number of items in the tree. This is because the worst case complexity is a factor of the tree's height. In a regular binary search tree, the height could be as large as n, which is a case where the tree is actually a linked list. However, in AVL trees, the maximum height will be a factor of log n
, thanks to the tree's self balancing.
AVL Trees
An AVL Tree is a self balancing binary search tree which uses rotation operations to preserve the tree's balance at each insertion and removal. We can consider an AVL tree to be a binary search tree with extra steps to check if a rotation is needed, and if so, apply it. In the sections below, we'll outline the rotation process, discuss which cases we need to apply rotations, and look at a code implementation. The table below shows the time complexity of different operations on an AVL tree.
Operation | Average Case | Worst Case |
---|---|---|
Insertion | O(log n) | O(log n) |
Deletion | O(log n) | O(log n) |
Retrieval | O(log n) | O(log n) |
Since the tree is self balancing, it will also always have a height proportional to log n
, and the maximum path from the root to a leaf node will also be proportional to log n
.
Tree Nodes
For our AVL tree implementation in the sections below, we will need to determine heights and balances of different nodes. We will encapsulate this logic in the method resynchronizeChildren
which will be called when a node's children change and when the tree rebalances itself. This method will update the node's height and balance properties. Other than that method, the tree node has the standard binary tree node fields for the node value, left child, and right child references. We will also have a field occurenceCount which will enable our AVL tree to have more than one instance of a value in the tree at the same time.
Node Rotations
AVL Tree implementations use rotation operations after insertions and deletions to ensure that the tree remains balanced. A single rotation will take two nodes which have a parent-child relationship, and with these nodes:
- Swap their relationship, so the node which was the parent is now the child, and the node which was the child is now the parent.
- Reassign the child node reference, which was just overriden by the previous step, and assign it to the node which has just become the child after the previous step has completed.
In the diagram shown, we can see two types of rotations, a left rotation and a right rotation, both of which appear to be mirror operations of each other. To outline the process of a single rotation using the node names from the diagram:
- Left Rotation:
- Set node P's right child to node Q. Note that node B is now disconnected.
- Set node Q's left child to node B. Note that B is now a left child instead of a right child.
- Right Rotation:
- Set node Q's left child to node P. Note that node B is now disconnected.
- Set node P's right child to node B. Note that B is now a right child instead of a left child.
In the code below, we will refer to the node we want to rotate as the baseNode and the other node in the rotation pair as baseLeft or baseRight, depending upon whether or not it is a left or right rotation. Other than that, the two methods are esentially the same.
Rebalancing an AVL Tree
In our AVL tree implementation, we will build onto a basic search tree implementation by adding an additional method rebalanceFromNode which will check if a given node needs to be rebalanced, and if so, apply one or two rotations to accomplish this. The flowchart below outlines which types of rotations we will need in each scenario depending upon the balance of the node and the value of one of the node's children in comparison to a node value which was recently inserted or deleted.
The implementation below is based on the flowchart and applies each rotation as defined in the previous sections.
Storing Multiple Values
Our AVL tree implementation will be able to store multiple instances of a single value in the tree. This is not required to implement, as some AVL trees can be design to only accept unique items, but we've decided to showcase the scenario where non-unique items can also be added. We've do so by creating an occurenceCount field within the node class itself to keep track of how many occurences of a value exist. The tree class can increment and decrement accordingly.
Full Implementation
This is a full implementation of our AVL tree including the code shown in the previous sections: