AVL Tree Insertion Algorithm and Code with Balancing Steps

AVL Trees introduction

An AVL tree A binary search tree (BST) in which, at every node, the height of the left and the right subtree differ by at most one. The feature aids in avoiding the tree being skewed thus compromising the worst-case performance of BST operations to O(n). The term AVL is named after the two inventors: Georgy Adelson-Velsky and Evgenii Landis, who suggested these dynamically balanced trees in 1962.

Every node of an AVL tree stores an additional structural data named a balance factor. The balance factor of a node is: the height of a left subtree minus the height of the right subtree. A balance factor of a balanced node is -1, 0 or +1. When the balancing factor is outside this range (i.e. is negative less than -1 or positive greater than +1), then it is out of balance and the rotations must be made such that an AVL property is regained.

AVL Tree operations

AVL trees also conduct different operations such as insertion, deletion, and search. These are basically binary search trees but with the add-ons of rebalancing operations to preserve the AVL property.

Insertion algorithm in AVL Tree

The algorithm to insert a new node into an AVL tree consists of two major steps, the first one is to identify the destination where to place the node similar to the algorithm of insertion in any simple BST and the second one is when needed to rebalance the tree by some operations so that the tree remains a balanced one. One will always insert a new node as leaf node, with the initial balance factor of 0.

The insertion algorithm of AVL tree can be simplified into the following steps:

1. Do Standard BST Insertion: Become recursive and go to the relevant leaf in the tree where the new key has to be inserted.* In the case that the new key is smaller than the key of the current node, follow the left subtree.* In a situation where the new key is larger than the current node key, move towards the right subtree.* In case the current node is null, then it is better to create a new node whose key is the same given and then it must be inserted here.

2. Updating heights: Once insertion is successfully done, the heights of the nodes, starting with the ancestor node, are updated as the recursive calls unwind, as the maximum of one additional to the maximum height of the left child and right child gets computed.

3. Calculation of Balance Factor: Balance factor is determined by calculating, Balance Factor = Height of Left Subtree - Height of Right Subtree, against each ancestor node.

4. Rebalance the Tree (Rotations): In case the balance factor of a node is more than 1 (left-heavy) or less than -1 (right-heavy) then the overall tree is unbalanced and rotations are carried out to make it balanced. The rebalancing mechanism goes upwards starting with the parent node of the new node that was inserted then corrects any imbalances it comes across till the root node is reached.

Rotations The types of rotations include basic, pseudo, stepwise, and mixed rotations. Basic Rotations Basic rotations are also known as plain rotations. A basic rotation occurs when the variables are not identically distributed and are defined as a rotation that maps each quasi-interface to a one-dimensional subspace of the plane (that is, the rotation of the variables).

Four key rotations, used to rebalance an AVL tree include:

Left-Left (LL) Rotation / Right Rotation

It happens when a node is added at the left subtree of the left child of any unbalanced node and arrangement of nodes will create an excess of balance factor over 1. This is rectified by doing one right rotation. A right rotation changes an order of the nodes to the left to an order of the nodes to the right.

Right-Right (RR) Rotation/ Left Rotation

This occurs when a node is added to the right subtree of the right child of an unbalanced node and causes the balance factor of less than -1. To rebalance the tree a single left rotation is done. A left rotation takes the layout of nodes on the right hand side and rotates them into a layout on the left hand side.

Left-Right (LR) rotation

It is a two-way rotation that is done when a node is left-heavy and its left child happens to be right-heavy.

It follows two steps, namely, a left rotation is done on the left child followed by a right rotation on the node.

Right-Left (RL) rotation

It is the other type of double rotation, which takes place when a node becomes right-heavy, and we are at the right child node,and there exists a left-heavy node. It entails right rotation on the right child, followed by the left rotation of the initiating node.

Complexity of time and space

An AVL tree has a time complexity of O(log n) with insertion. It is due to the fact that the insertion point search is the operation with O(log n) time complexity and so is the process of rebalancing (rotations and updating the height of the node) in the form of going up the tree to the tree root, which in turn also requires O(log n) time since the rotation is O(1).

The space complexity of an AVL tree is O(n), n being the number of nodes. Here there is an account of the storage of each node which has data, child pointers and also this balance factor. The recursive nature of the insertion algorithm also takes O(log n) auxiliary space in the form of the call stack of recursion.

The Usage of AVL Trees

AVL trees make an ideal solution when a big set of data is supposed to be found quickly, softened, and renewed. They are especially suitable to:

• Applications which required real time update.
• Cases where trees need to be kept as efficient as possible by regularly updating the data.
• Applications that demand sorting of the data regularly.

Smaller and discrete datasets, or in the case that memory space is very constrained, simpler data structures may be more suitable, because AVL trees have overhead and complexity.

Find More with Uncodemy

Uncodemy has detailed training programs of data structures and algorithms and AVL trees as well in case a person is interested in a more detailed exploration of the subject. Uncodemy offers a training course in Noida; it includes practical training on the advanced tools and technologies in Data structure and algorithms. Besides, Uncodemy provides other courses based on data structure such as"C with Data Structure Certification Training in Delhi" and so on which consists of different issues such as AVL tree insertion that includes LL Rotation, LR Rotation, RL Rotation, and RR Rotation. The courses are designed to suit beginners to the experienced professionals.