AVL Binary Tree Operations

There are different types of self-balancing trees, such as red-black trees, AA trees, and scapegoat trees. They balance the tree during each operation that modifies the tree, such as an insertion or deletion operation. There are also external algorithms that balance a tree. The benefits of these are that we do not need to balance the tree on every single operation and can leave balancing so that we do not need it.

Let us start with AVL trees.

AVL trees

An AVL tree is a Binary Search Tree (BST) that has a balanced height in which the difference between the height of the left subtree and right subtree of every node in the tree is not more than 1. This difference is called a balanced factor. The balancing factor for any node (X) can be computed using the following formula:

Balancingfactor(X)=Height(left(X))-Height(Right(X))

Here, Height(left(X)) means the height of the left subtree with respect to node X and Height(right(X)) is the height of the right subtree in respect to node X. An example of a balanced AVL tree is shown below, which each node has a balancing factor in the range of –1 to 1:

The height of the AVL tree is balanced, and the tree is not skewed, since the time taken in different operations has a worst-case scenario of O(n) if the BST is skewed. Let’s look at different operations in an AVL tree.

Operations in an AVL tree

All the operations in an AVL tree, such as traversing, searching, insertion, and deletion operations are very similar to a BST, since an AVL tree is a BST. It is noteworthy that searching and traversing operations do not violate the condition of the AVL tree because, in such operations, we do not change the structure of the tree, so these operations are exactly the same as those of a BST tree. However, in the case of insertion and deletion operations, we need to check if the balancing factor of all the nodes satisfies the conditions of an AVL tree.

The insertion and deletion operations in the AVL tree are performed as follows:

1. We insert or delete any data item, as it is what we do in the BST.
2. After the insertion or deletion operation, we check the balancing factor of all the nodes from the insertion/deletion point to the root of the tree.
3. If the balancing factor of all the nodes is in the range of -1 and 1, then we go for other operations if required.
4. If the balancing factor of any node violates the condition, then we use any of the above rotations to make the tree balanced.

Let’s consider the insertion operation first.

Inserting nodes

After the insertion of a node in the AVL tree, if the tree becomes unbalanced, it will only impact the nodes that are in the path from the newly added node to the root node, as only subtrees of these nodes will be updated. So, it is important to note that when any insertion operation is performed in an AVL tree, the balancing factor of the nodes, which is within the path from the inserted node to the root node, will be changed. So, in order to keep the AVL property intact, such as the balancing factor of each node not being more than 1, we have to check all the nodes from the insertion point to the root node. Once we find a node violating this condition, we use a rotation to balance that node. After fixing the balancing property for this node, there is no need to further check any other node from that node to the root node, as the issue will automatically be fixed.

The AVL tree performs rotations after every operation, such as insertion or deletion, to ensure that the tree remains balanced and that every node adheres to the AVL tree’s properties. Whenever any node (X) violates the balancing condition of an AVL tree, there will be one of the following four cases:

1. An insertion in the left subtree of the left child node of node X.
2. An insertion in the right subtree of the right child node of node X.
3. An insertion in the right subtree of the left child node of node X.
4. An insertion in the left subtree of the right child node of node X.

Left, left variant

If a node violates the AVL property, as mentioned in the first case, in which a new element is added to the left subtree of the left child of a node (say X), then that node X becomes unbalanced. This is shown below:

A single right rotation at node X will balance the tree, as shown in the above figure.

Right, right variant

If a node violates the AVL tree’s property in which a new element is added to the right subtree of the right child of a node (say X), then node X becomes unbalanced. For example, after adding node 9 into the AVL tree in the right subtree of right child 8 of node X, the tree becomes unbalanced (since the height difference for node 6 becomes two). This is shown below:

A single left rotation at node X will make the tree balanced as shown in the above figure.

Left, right variant

If a node violates the AVL property in which a new element is added to the right subtree of the left child node, then that node becomes unbalanced. For example, after adding node 4 in the right subtree of left child node 2, which is the left child of node 9, the balancing factor of node X (node 9 in this example) violates the property of the AVL tree. This is shown in the below figure:

One left rotation and one right rotation (double rotation) will balance the tree, as shown in the figure.

Right, left variant

If a node violates the AVL tree’s property in which a new element is added to the left subtree of the right child node, then that node becomes unbalanced. For example, after adding node 6 into the left subtree of node 8, which is the right child of node 5, the balancing factor of node 5 becomes two, which violates the property of the AVL tree. This is shown in the below figure:

One right rotation and one left rotation (double rotation) will balance the tree is shown above. Here, in the first right rotation, node 7 becomes the parent of node 8. Furthermore, in the second rotation, which is the left rotation, node 7 becomes the parent node of node 5, and then node 6 becomes the right child of node 5 since node 7 already has two children, nodes 5 and 8.

Summary

In summary, we have discussed AVL trees and operations we can perform on them, such as inserting a node in different variants (for example, left, right or right, right). Learn more in the book, Hands-On Data Structures and Algorithms with Python by Basant Agarwal.