An AVL (Adel´son-Vel´sky and Landis) tree is a type of binary search tree (BST). Unlike a BST, which can easily become unbalanced when adding and deleting nodes, the AVL tree maintains a balanced state by maintaining a height-balance property. This property ensures that the tree remains approximately balanced at all times. You can refer to the following link for an overview of BST's: Binary Search Trees
In an AVL tree, the height-balance property states that for any node in the tree, the heights of the left and right subtrees can differ by at most one. This means that for every node n, the following condition holds:
|h(left_child(n)) - h(right_child(n))| ≤ 1
where h(node) represents the height of the subtree rooted at node. If this condition is violated after an insertion or deletion, the tree must be rebalanced.
An example of a balanced AVL tree with the height of each node indicated above it. Note that the difference in height between all left/right child nodes is at most 1, which satisfies the height-balance property.
When nodes are added or removed from an AVL tree, the height-balance property may be violated. To restore balance, the tree performs a series of rotations. You can refer to the above BST link given at the start of this page for more information on rotations.
When a new node is inserted into an AVL tree, the height of the inserted node's ancestors may increase, potentially violating the height-balance property, as shown in the following diagrams:
Inserting "A" does not violate the height-balance property.
Inserting "D" causes a height-balance property violation for B, the left child of E, and E, the left child of H.
After the insertion, a search is made traversing up the tree from the inserted node to find the first ancestor node that violates the height-balance property. If found, the tree performs one of four types of rotations to restore balance. To assist with visualization of the necessary rotations, we use variables x, y, and z to represent the nodes involved in the rotations. z is the first node whose children violate the height-balance property. y is the child of z with the greater height, and x is the child of y with the greater height. As the image below shows, after the restoration rotations are applied to the first ancestor that violates the height-balance property, the tree regains its balanced state.
An image showing the rebalancing of an AVL tree after the insertion of a node into a balanced AVL tree. a) The original balanced tree. b) The tree after the insertion of a node in the right subtree of x. Note that the height of z has increased and y is now two levels taller than its sibling, violating the height-balance property. c) The tree after performing a left rotation on y and x to prepare for a height-balancing right rotation on z and x which leads to d). d) The final balanced AVL tree after the right rotation on z and x. Note that the height of the subtree (with root of x now) is the same as before the insertion. This indicates that all ancestor nodes are still in balance and we can stop the rebalancing process.
When a node is deleted from an AVL tree, the height of the deleted node's ancestors may decrease, potentially violating the height-balance property. Similar to insertion, a search is made traversing up the tree from the deleted node to find the first ancestor node that violates the height-balance property. If found, the tree performs one of four types of rotations to restore balance. Note that after a deletion, multiple rotations may be necessary to fully restore balance to the tree, as shown in the following diagrams. Even though the restoration process may involve multiple rotations, the performance of deletion is still O(log n). The search for the node to delete is O(log n). The rotation for each correction is O(1), and the search up the tree for rebalancing is also O(log n). This results in a total time complexity of O(log n) + (O(1) * O(log n)) = O(log n) for the deletion operation.
An image showing the rebalancing of an AVL tree after the deletion of a node from a balanced AVL tree. a) The original balanced tree before deletion of the indicated node. b) The tree after the deletion of the indicated node. Note that resulting height disparity between the child nodes of z. c) The tree after performing a right rotation of z and y to restore balance to that subtree. Note that the height of the right subtree (with root of y now) has decreased, causing a new height-balance violation between y and its sibling. A new rebalancing is then necessary. This rebalancing may continue up the tree until the root is reached.
AVL trees provide efficient performance for search, insertion, and deletion operations. The time complexity for these operations is O(log n), where n is the number of nodes in the tree. This logarithmic time complexity is due to the balanced nature of AVL trees, which ensures that the height of the tree remains logarithmic with respect to the number of nodes. The following table summarizes the time complexity for various operations on AVL trees: