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).
- 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.
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
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.
- 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.
- 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
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.
This is a full implementation of our AVL tree including the code shown in the previous sections: