search tree. That means, an AVL tree is also a binary search tree but it is a

balanced tree. A binary tree is said to be balanced if, the difference between

the heights of left and right subtrees of every node in the tree is either -1, 0 or +1. In other words, a binary tree is

said to be balanced if the height of left and right children of every node

differ by either -1, 0 or +1. In an AVL

tree, every node maintains an extra information known as balance factor. The

AVL tree was introduced in the year 1962 by G.M. Adelson-Velsky and E.M.

Landis.

An AVL tree is defined as follows:

**An AVL tree is a balanced binary search tree. In an AVLtree, balance factor of every node is either -1, 0 or +1.**

Balance factor of a node is the

difference between the heights of the left and right subtrees of that node. The

balance factor of a node is calculated either height of left subtree - height

of right subtree (OR) height of right subtree - height of left subtree. In the

following explanation, we calculate as follows:

**Balance factor = heightOfLeftSubtree - heightOfRightSubtree.**

**Example:-**

**AVL Tree Rotations**

In AVL tree, after performing

operations like insertion and deletion we need to check the balance factor of

every node in the tree. If every node satisfies the balance factor condition

then we conclude the operation otherwise we must make it balanced. Whenever the

tree becomes imbalanced due to any operation we use rotation operations to make

the tree balanced.

Rotation operations are used to make

the tree balanced.

**Rotation is the process of moving nodes either to left or toright to make the tree balanced.**

**Operations on an AVL Tree**

The following operations are performed

on AVL tree...

1. Search

2. Insertion

3. Deletion

**Search Operation in AVL Tree**

In an AVL tree, the search operation is

performed with O(log n) time complexity. The search operation in the AVL tree

is similar to the search operation in a Binary search tree. We use the

following steps to search an element in AVL tree...

Step

1 - Read the search element from the user.

Step

2 - Compare the search element with the value of root node in the tree.

Step

3 - If both are matched, then display "Given node is found!!!" and terminate

the function

Step 4 - If both are not matched, then check

whether search element is smaller or larger than that node value.

Step

5 - If search element is smaller, then continue the search process in left

subtree.

Step

6 - If search element is larger, then continue the search process in right

subtree.

Step 7 - Repeat the same until we find

the exact element or until the search element is compared with the leaf node.

Step 8 - If we reach to the node having

the value equal to the search value, then display "Element is found"

and terminate the function.

Step 9 - If we reach to the leaf node

and if it is also not matched with the search element, then display

"Element is not found" and terminate the function.

**Insertion Operation in AVL Tree**

In an AVL tree, the insertion operation

is performed with O(log n) time complexity. In AVL Tree, a new node is always

inserted as a leaf node. The insertion operation is performed as follows...

Step

1 - Insert the new element into the tree using Binary Search Tree insertion

logic.

Step 2 - After insertion, check the

Balance Factor of every node.

Step 3 - If the Balance Factor of every node

is 0 or 1 or -1 then go for next operation.

Step 4 - If the Balance Factor of any

node is other than 0 or 1 or -1 then that tree is said to be imbalanced. In

this case, perform suitable Rotation to make it balanced and go for next

operation.

**Deletion Operation in AVL Tree**

The deletion operation in AVL Tree is

similar to deletion operation in BST. But after every deletion operation, we

need to check with the Balance Factor condition. If the tree is balanced after

deletion go for next operation otherwise perform suitable rotation to make the

tree Balanced.

** **

Name | Views | Likes |
---|---|---|

AVL TREE | 240 | 19 |

## Comments