How to insert a node in an AVL tree

AVL trees

AVL trees are self-balancing binary search trees. This means that whenever an imbalanceAn imbalance in a binary search tree happens due to one subtree of a node being heavier than the other subtree. is created via the insertion or deletion of a node(s), these trees can restore the balance.

Note: To learn more about AVL trees and the different types of imbalances that can arise in them due to the insertion/deletion of a node(s), refer to this link.

This maintenance of balance in an AVL tree allows operations such as insertion, deletion, and searching to run in $O(log(N))$ time. Thus, it makes them much more efficient than simple binary search trees, which take $O(N)$ time in the worst case.

Insertions

Efficiently inserting a new node in an AVL tree requires a recursive approach that involves 2 main steps:

1. Inserting the node itself: We insert a node into the tree the same way it would be inserted into a binary search tree—recursively. This new node will become a leaf node.

2. Rebalancing the tree once the node is inserted: This happens once the backtracking starts. Starting from the newly inserted node (currently a leaf node), we travel up the tree until the first unbalanced node (with a balance factorThe balance factor of a node is the difference in the height of the left and right sub-tree. The balance factor of every node in the AVL tree should be either +1, 0 or -1. that lies outside the range [-1, 1]) is found. Next, we perform the required rotationsRotations involve switching around positions of nodes in the unbalanced node's sub-tree(s) each time the balance factor is disrupted. on the subtree of this unbalanced node to rebalance it. This is repeated until we reach the root node of the tree and the recursion backtracking ends.

Insert the node itself

To insert a node in a BST, we first compare the value of $x$ (the node being inserted) with the value of the root node. If this value is less than the root node's value, we go to the left child, making it the root node for the next recursive call. Similarly, if this value is greater than the root node's value. We go to the right child and make it the root node for the next recursive call. We keep making these recursive calls until we reach a leaf node. If the value of $x$ is less than this leaf node's value, we make it the left child of this leaf node. Similarly, if the value of $x$ is greater than this leaf node's value, we make it the right child of this leaf node.

The example below demonstrates this (the current root node during the recursive calls is colored orange):

Once the node is inserted into the tree, the backtracking can begin since the base case is reached for the first time.

Rebalance the tree once the node is inserted

During backtracking, we check the balance factor of each node. If the balance factor is in the range [-1, 1], we do nothing and allow backtracking to proceed as it is. However, if the node is unbalanced, we need to perform rotation(s) on it to rebalance it.

Note: To learn more about how the rebalancing of an AVL tree is done using rotations, refer to this link.

If the balance factor is 2, then this means that the unbalanced node's left subtree is heavier than the right one. Thus, there is either a left-left imbalance or a left-right imbalance. Now, if the balance factor of the unbalanced node's left child is greater than or equal to 1 (or, alternatively, if the value of $x$ is less than the value of the unbalanced node's left child), this narrows it down to a left-left imbalance and a right rotation needs to be applied on the unbalanced node, otherwise, the imbalance is a left-right one and a left-right rotation needs to be applied.

Similarly, if the balance factor is -2, then this means that the unbalanced node's right subtree is heavier than the left one. Thus, there is either a right-right imbalance or a right-left imbalance. Now, if the balance factor of the unbalanced node's right child is less than or equal to 0 (or, alternatively, if the value of $x$ is greater than the value of the unbalanced node's right child), this narrows it down to a right-right imbalance and a left rotation needs to be applied on the unbalanced node. Otherwise, the imbalance is a right-left one and a right-left rotation needs to be applied.

This backtracking process is depicted below, continuing the same example from above (the current root node during each step of the backtracking is colored red):

Once the backtracking ends, we have successfully inserted new_node . Another example is demonstrated below:

Code example

The insertNode() function, highlighted in the lines below, implements the steps discussed above for inserting a node in an AVL tree:

Explanation

In the output of the code above, the nodes of the tree have been printed in a 2-D manner to help with visualization. To keep the implementation of the prettyPrintTree() function straightforward, the tree is rotated 90^o to the left in the output.