How to Insert Strings into an AVL Tree

Q: What is the maximum height of an AVL tree having n nodes?

The maximum height of an AVL tree having n nodes is log(n).

Q: State two properties of AVL trees.

The important properties of an AVL tree are: 1. It is a binary search tree, 2. For any node A, the height of the left subtree of A and the height of the right subtree of A differ by at most 1.

Q: What is the balancing condition of an AVL tree?

The balancing condition of an AVL tree is: balance(n) = abs(height(n.left)−height(n.right))

Q: What is the insertion cost in an AVL tree in terms of time complexity?

O(log(n)) where n is the number of nodes.

Introduction

Trees can be regarded as one of the most important topics of Data Structures and Algorithms and are included in almost every interview or placement test. They are of different types, including Binary trees, Binary Search Trees, Red-Black trees, N-ary trees, etc.

AVL tree is one such important topic that is a must for interview preparation.

This blog will discuss the problem, of how to insert strings into an AVL tree.

AVL tree is a self-balancing binary tree named after its inventors, Adelson Velshi and Landis. It was one of the first trees that could balance itself dynamically.
Balance Factor → The difference between the height of the left subtree and the right subtree at every node is defined as the balance factor.

In the case of an AVL tree, the balance factor can have only 3 values, -1, 0, and 1.

Example

For example, let's take a look at the following AVL trees:

This tree is an AVL tree because the balance factor has only 3 values, -1, 0, and 1.

This tree is not an AVL tree because the balance factor has values 2, and -2 which are not allowed in an AVL tree.

Approach

At every step, the nodes should be inserted so that the property of the AVL tree is not violated. To make sure that the tree remains AVL even after the insertion of nodes, the balance factor needs to be checked, and if it is not equal to -1, 0, and 1 the rotation needs to be performed accordingly.

Algorithm

Create a node with the first value available, in case it is initially empty.
Place it to the left if the new node is less than the preceding node.
Otherwise, if the new node is larger than the preceding node, it should be placed to the right.
The next task is to check whether the tree is balanced or not.
Balance factor > 1: 2 cases are possible in this case:
- Single Rotation - Left - Left case
- Double Rotation - Left - Right case
Balance factor < -1: 2 cases are possible in this case:
- Single Rotation - Right - Right case
- Double Rotation - Right - Left case
Repeat this process until all the remaining nodes are inserted into the tree.

Let us look at the following example to understand the implementation of the above-given algorithm.

Implementation

Let us consider a set of 7 countries that need to be inserted into an AVL tree.

{Turkey, Mexico, Thailand, Spain, Syria, France, Yemen}

According to the algorithm, we will first insert ‘Turkey’ as the first node and its balance factor will be 0.

Next, we will insert ‘Mexico’ to the left of ‘Turkey’, as M is smaller than T.

Balance Factor for ‘Mexico’ = 0

Balance Factor for ‘Turkey’ = 1 - 0 = 1

Next, we will insert ‘Thailand’ to the left of ‘Mexico’, as T is greater than M.

Balance Factor for ‘Thailand’ = 0

Balance Factor for ‘Mexico’ = 0 - 1 = -1

Balance Factor for ‘Turkey’ = 2 - 0 = 2

Since the balance factor becomes 2, which is greater than 1, it needs to be rotated in order to be balanced.

Next, we will insert ‘Spain’ to the left of ‘Thailand’ and to the right of ‘Mexico’ as S is greater than M, but smaller than T.

Balance Factor for ‘Spain’ = 0

Balance Factor for ‘Mexico’ = 0 - 1 = -1

Balance Factor for ‘Turkey’ = 0

Balance Factor for ‘Thailand’ = 2 - 1 = 1

Now, we have to insert ‘Syria’, which will be inserted to the right of ‘Spain’ as SY is greater than SP.

Balance Factor for ‘Syria’ = 0

Balance Factor for ‘Spain’ = 1 - 0 = 1

Balance Factor for ‘Mexico’ = 0 - 2 = -2

Balance Factor for ‘Turkey’ = 0

Balance Factor for ‘Thailand’ = 3 - 1 = 2

Since the balance factor becomes 2, which is greater than 1, it needs to be rotated to be balanced.

Now, we have to insert ‘France’, which will be inserted to the left of ‘Mexico’’ as F is smaller than M.

Balance Factor for ‘France’ = 0

Balance Factor for ‘Mexico’ = 1 - 0 = 1

Balance Factor for ‘Syria = 0

Balance Factor for ‘Spain’ = 2 - 1 = 1

Balance Factor for ‘Turkey’ = 0

Balance Factor for ‘Thailand’ = 3 - 1 = 2

Since the balance factor becomes 2, which is greater than 1, it needs to be rotated once again to be balanced.

Now, we have to insert ‘Yemen’, which will be the last node to be inserted, and it will be inserted to the right of ‘Syria’ as Y is greater than S.

Balance Factor for ‘France’ = 0

Balance Factor for ‘Mexico’ = 1 - 0 = 1

Balance Factor for ‘Yemen’’ = 0

Balance Factor for ‘Turkey’ = 0 - 1

Balance Factor for ‘Syria = 0

Balance Factor for ‘Thailand’ = 1 - 2 = -1

Balance Factor for ‘Spain’’ = 2 - 3 = -1

At last, we have obtained the required height-balanced AVL tree, where the balance factor is -1, 0, and 1.

Check out this problem - Find Duplicate In Array

Frequently Asked Questions

What is the maximum height of an AVL tree having n nodes?

The maximum height of an AVL tree having n nodes is log(n).

State two properties of AVL trees.

The important properties of an AVL tree are:
→ It is a binary search tree,
→ For any node A, the height of the left subtree of A and the height of the right subtree of A differ by at most 1.

What is the balancing condition of an AVL tree?

The balancing condition of an AVL tree is:
balance(n) = abs(height(n.left)−height(n.right))

What is the insertion cost in an AVL tree in terms of time complexity?

O(log(n)) where n is the number of nodes.

Conclusion

So, this blog discussed the problem of how to insert strings into an AVL tree. To discover more, go to Coding Ninjas Studio right now to practice problems and ace your interviews like a Ninja!