Read Time:13 Minute, 16 Second

AVL TREE

An AVL tree is a self-balancing binary search tree that maintains a balanced height between its left and right subtrees. The name “AVL” comes from the initials of the inventors Adelson-Velsky and Landis.

Table of Contents

In an AVL tree, the height difference between the left and right subtree of any node is at most one. This ensures that the tree remains balanced even after insertions and deletions, and guarantees a worst-case time complexity of O(log n) for both searching and insertion.

The balancing of the AVL tree is achieved by performing rotations on the tree after an insertion or deletion operation that may cause the tree to become unbalanced. There are four types of rotations – left rotation, right rotation, left-right rotation, and right-left rotation – which are used to balance the tree.

AVL trees are commonly used in database indexing, where efficient search and insertion operations are required. However, the self-balancing property of AVL trees comes at the cost of increased overhead in terms of memory usage and insertion/deletion time compared to non-balanced binary search trees.

Overall, AVL trees are a powerful data structure for maintaining a sorted collection of items with efficient search and insertion operations, especially when the number of operations performed on the tree is high and the need for a balanced tree is critical.

The balancing of the AVL tree

The balancing of an AVL tree is maintained by performing rotations on the tree after an insertion or deletion operation that may cause the tree to become unbalanced. There are four types of rotations – left rotation, right rotation, left-right rotation, and right-left rotation – which are used to balance the tree.

A left rotation is performed when a node has a balance factor of +2, meaning that its right subtree is two levels deeper than its left subtree. The rotation involves moving the node’s right child up to become its parent, with the node becoming the left child of its former right child’s left child.

A right rotation is performed when a node has a balance factor of -2, meaning that its left subtree is two levels deeper than its right subtree. The rotation involves moving the node’s left child up to become its parent, with the node becoming the right child of its former left child’s right child.

A left-right rotation is performed when a node has a balance factor of +2 and its right child has a balance factor of -1, indicating that the right child’s left subtree is deeper than its right subtree. The rotation involves first performing a right rotation on the node’s right child, followed by a left rotation on the node itself.

A right-left rotation is performed when a node has a balance factor of -2 and its left child has a balance factor of +1, indicating that the left child’s right subtree is deeper than its left subtree. The rotation involves first performing a left rotation on the node’s left child, followed by a right rotation on the node itself.

After performing a rotation, the balance factors of the affected nodes are recalculated, and the process is repeated until the entire tree is balanced.

Left rotation

A left rotation is a type of rotation performed on an AVL tree to balance it after an insertion or deletion operation has made it unbalanced.

When a node has a balance factor of +2, meaning that its right subtree is two levels deeper than its left subtree, a left rotation is performed on the node. The rotation involves moving the node’s right child up to become its parent, with the node becoming the left child of its former right child’s left child.

Here are the steps to perform a left rotation on a node X:

Set Y as X’s right child

Set B as Y’s left child
Set X as B’s parent
Set Y as the new root

Set X as Y’s left child
Set B as X’s right child

Before Rotation:

        X                  <--+2 balance factor
       / \
      A   Y                <--balance factor of Y is -1 or 0
         / \
        B   C

After Rotation:

        Y                  <--balanced
       / \
      X   C
     / \
    A   B

In the above example, the node X had a balance factor of +2, so a left rotation was performed on node X. The right child of X (node Y) became the new root, with X becoming the left child of Y, and the former left child of Y (node B) becoming the right child of X.

After the left rotation, the height of the left and right subtrees of node Y differs by at most one, ensuring that the AVL tree is balanced.

Right rotation

A right rotation is a type of rotation performed on an AVL tree to balance it after an insertion or deletion operation has made it unbalanced.

When a node has a balance factor of -2, meaning that its left subtree is two levels deeper than its right subtree, a right rotation is performed on the node. The rotation involves moving the node’s left child up to become its parent, with the node becoming the right child of its former left child’s right child.

Here are the steps to perform a right rotation on a node X:

Set Y as X’s left child
Set B as Y’s right child
Set X as B’s parent

Set Y as the new root
Set X as Y’s right child
Set B as X’s left child

Before Rotation:

         X                 <-- -2 balance factor
        / \
       Y   C              <--balance factor of Y is +1 or 0
      / \
     A   B

After Rotation:

         Y                  <-- balanced
        / \
       A   X
          / \
         B   C

In the above example, the node X had a balance factor of -2, so a right rotation was performed on node X. The left child of X (node Y) became the new root, with X becoming the right child of Y, and the former right child of Y (node B) becoming the left child of X.

After the right rotation, the height of the left and right subtrees of node Y differs by at most one, ensuring that the AVL tree is balanced.

Left-right rotation

A left-right rotation is a type of rotation performed on an AVL tree to balance it after an insertion or deletion operation has made it unbalanced. It is a combination of a left rotation followed by a right rotation.

Here are the steps to perform a left-right rotation on a node X:

Perform a right rotation on X’s right child Y.
Perform a left rotation on X.

Before Rotation:

         X                   <-- +2 balance factor
        / \
       A   Y                <-- -1 balance factor
          / \
         B   Z
        / \
       C   D

After Right Rotation on Y:

After Left Rotation on X:

In the above example, the node X had a balance factor of +2 and its right child Y had a balance factor of -1, so a left-right rotation was performed on node X. First, a right rotation was performed on node Y, and then a left rotation was performed on node X.

After the left-right rotation, the height of the left and right subtrees of node B, which is the new root, differs by at most one, ensuring that the AVL tree is balanced.

Right-Left rotation

A right-left rotation is a type of rotation performed on an AVL tree to balance it after an insertion or deletion operation has made it unbalanced. It is a combination of a right rotation followed by a left rotation.

Here are the steps to perform a right-left rotation on a node X:

Perform a left rotation on X’s left child Y.

Perform a right rotation on X.

Before Rotation:

         X                    <-- -2 balance factor
        / \
       Y   A                 <-- +1 balance factor
      / \
     Z   B
        / \
       C   D

After Left Rotation on Y:

After Right Rotation on X:

In the above example, the node X had a balance factor of -2 and its left child Y had a balance factor of +1, so a right-left rotation was performed on node X. First, a left rotation was performed on node Y, and then a right rotation was performed on node X.

After the right-left rotation, the height of the left and right subtrees of node B, which is the new root, differs by at most one, ensuring that the AVL tree is balanced.

Differences from other type of tree

AVL trees are a type of self-balancing binary search tree. The main difference between AVL trees and other types of binary search trees, such as binary search trees (BSTs) and Red-Black trees, is that AVL trees guarantee a balanced tree structure at all times, which means that the height of the tree is always logarithmic in the number of nodes.

Here are some of the differences between AVL trees and other types of binary search trees:

AVL trees have a stricter balance condition compared to BSTs. In a BST, a node can have at most two children, but there is no constraint on the balance of the tree. In contrast, AVL trees require that the difference in height between the left and right subtrees of each node be at most one.

Red-Black trees use color coding to maintain balance, whereas AVL trees use rotations. In Red-Black trees, each node is assigned a color, either red or black, and the tree is balanced by enforcing certain rules about the placement of red and black nodes. In AVL trees, the tree is balanced by performing rotations on nodes that violate the height balance condition.
AVL trees may be less efficient than Red-Black trees for some operations. Because AVL trees maintain strict height balance, they may require more frequent rotations than Red-Black trees, which can make them less efficient for certain operations.
AVL trees are more suitable for applications where efficient searching is a priority, while Red-Black trees are more suitable for applications where efficient insertion and deletion are a priority.

In summary, AVL trees differ from other types of binary search trees in their strict height balance condition and use of rotations to maintain balance, which can make them more efficient for searching but potentially less efficient for other operations.

Usage of AVL tree

AVL trees are primarily used in situations where efficient searching and retrieval of data is important, and where data is frequently added or deleted. Some specific examples of applications where AVL trees can be useful include:

Databases: AVL trees can be used to index data in databases, making it faster and easier to search and retrieve information.

Compiler design: AVL trees are often used in compiler design to store symbol tables, which are used to keep track of identifiers (such as variables, functions, and types) in a program.
Text editors: AVL trees can be used in text editors to implement fast search and replace operations.
Networking: AVL trees can be used in network routing algorithms to efficiently store and search routing tables.

Computer graphics: AVL trees can be used in computer graphics algorithms to efficiently store and search data structures used in 3D rendering.

In general, AVL trees are useful in any application where efficient searching and retrieval of data is important, and where the data is frequently updated or modified.

Summary

AVL trees are a type of self-balancing binary search tree that guarantee a balanced tree structure at all times. They use rotations to maintain balance and ensure that the height of the tree is always logarithmic in the number of nodes. AVL trees are useful in applications where efficient searching and retrieval of data is important, and where data is frequently added or deleted. Some specific examples of applications where AVL trees are used include databases, compiler design, text editors, networking, and computer graphics.

Question:

Write a “c” program to create an AVL TREE A and perform the operations insertion, deletion, search and traversal. Assume that the AVL Tree A
does not contain duplicate values.

The program should contain the following functions:
InSERT(A,k)- Inserts a new node with key ‘k’ into the tree A.
SEARCh (A, k) – Searches for a node with key ‘k’ in A, and returns a pointer to the node with key k if one exists; otherwise, it returns NIL. Deletenode(A, k) – Deletes a node with the key ‘k’ from the tree A. Getbalance(A,k) – Prints the balance factor of the node with ‘k’ as key in the tree A.

Note:- Balance factor is an integer which is calculated for each node as:
B_factor = height(left_subtree)−height(right_subtree)

LeftRotate(A, k) – Perform left rotation in the tree A, with respect to the node with key ‘k’.
RightRotate(A, k) – Perform right rotation in the tree A, with respect to node with key ‘k’.
PrintTree(A) – Prints the tree given by A in the parenthesis format as: (t
( left-subtree )( right-subtree ) ),t represents root node of tree A. Empty parenthesis ( ) represents a null tree.

Note: After each insertion on an AVL TREE, it may result in increasing the height of the tree. Similarly, after each deletion on an AVL TREE, it may result in decreasing the height of the tree. To maintain height balanced property of AVL tree, we may need to call rotation functions.

Tree A should be an AVL Tree after INSERT AND DELETE NODE operations.

Input Format: – Each line contains a character from ‘i’, ‘d’, ‘s’, ‘b’, ‘p’and ‘e’ followed by at most one integer.
The integers, if given, are in the range[−10^6,10^6].
Character ‘i’ is followed by an integer separated by space; a node with this integer as key is created and inserted into A.
Character ‘d’ is followed by an integer separated by space; the node with this integer as key is deleted from A and the deleted node’s key is printed.
Character ‘s’ is followed by an integer separated by space; find the node with this integer as key in A.
Character ‘b’ is followed by an integer separated by space; find the balance factor of the node with this integer as key in A and the print the balance-factor.
Character ‘p’ is to print the Parenthesis Representation of the tree A.
Character ‘e’ is to ‘exit’ from the program.

Output Format:
The output (if any) of each command should be printed on a separate line. For option ‘d’, print the deleted node’s key. If a node with the input key is not present in A, then print FALSE.
For option ‘s’, if the key is present in A, then print TRUE. If key is not present in A, then print FALSE.
For option ‘b’, if the key k is present in A, then print the balance factor of the node with k as key. If key is not present in A, then print FALSE.
For option ‘p’, print the Parenthesis Representation of the tree A.

Sample Input:
i4
i6
i3
i2
i1
s2
p
b4
d3
p
e
Sample Output: TRUE
(4(2(1()())(3()()))(6()()))
1
3
(4(2(1()())())(6()()))