6.6 AVL balanced trees and  Balancing algorithm

An AVL tree is a self-balancing binary search tree (BST) where the heights of the two child subtrees of any node differ by at most one. It is named after its inventors, Adelson-Velsky and Landis. AVL trees are designed to maintain a balanced structure, ensuring that the height of the tree remains O(log n) where n is the number of nodes in the tree.

Definition:

In an AVL tree:

• Binary Search Tree Property: Every node in the tree satisfies the binary search tree property, meaning that for any given node:
• All nodes in the left subtree have values less than the node's value.
• All nodes in the right subtree have values greater than the node's value.
• Balance Factor: For every node in the tree, the height difference between its left and right subtrees (known as the balance factor) is either -1, 0, or 1.

Why AVL Tree:

The main motivation behind using AVL trees is to ensure that the operations performed on the tree (insertion, deletion, and search) have a guaranteed time complexity of O(log n), where n is the number of nodes in the tree. Without balancing, in a typical binary search tree, the tree could degenerate into a linked list in the worst case scenario, leading to linear time complexity (O(n)) for these operations.

By maintaining the balance property, AVL trees provide faster search times compared to unbalanced binary search trees. This balance ensures that the height of the tree remains relatively small, optimizing the time complexity of operations. Additionally, AVL trees are particularly useful in scenarios where the tree is frequently updated, as their self-balancing property helps in maintaining efficiency even after numerous insertions and deletions.

Overall, AVL trees strike a balance between the efficiency of operations and the overhead of maintaining balance, making them a popular choice for applications where fast search times are crucial and the dataset is subject to frequent modifications.

Balance Factor

The balance factor of a node in an AVL tree is calculated as the difference between the height of its left subtree and the height of its right subtree. Mathematically, the balance factor (BF) of a node can be expressed as:

BF=height of left subtree−height of right subtree

In this formula, "height of left subtree" refers to the height of the left child subtree of the node, and "height of right subtree" refers to the height of the right child subtree of the node.

The balance factor can take on three possible values:

• BF=−1 : The left subtree is one level higher than the right subtree.
• BF=0 : Both the left and right subtrees have the same height, or the node has no children.
• BF=1 : The right subtree is one level higher than the left subtree.

For a balanced AVL tree, the balance factor of every node must be either -1, 0, or 1. If the balance factor of any node violates this condition, the tree needs to be rebalanced to maintain AVL tree properties.

Every AVL Tree is a binary search tree but every Binary Search Tree need not be AVL tree.

Rotation Operation in AVL Tree

AVL tree rotations are operations performed on AVL trees to maintain the balance property after an insertion or deletion that may have caused the tree to become unbalanced. In an AVL tree, balance is maintained by ensuring that the heights of the left and right subtrees of any node differ by at most one. When this balance condition is violated, rotations are performed to restore balance without violating the binary search tree property.

There are four main types of AVL tree rotations:

Left Rotation (LL Rotation):

• Used when the balance factor of a node becomes greater than 1 due to an insertion or deletion in the left subtree of its left child.
• It involves rotating the unbalanced node down to the right while promoting its left child to become the new root.
• This operation helps to restore balance and maintain the properties of the AVL tree.

Right Rotation (RR Rotation):

• Used when the balance factor of a node becomes less than -1 due to an insertion or deletion in the right subtree of its right child.
• It involves rotating the unbalanced node down to the left while promoting its right child to become the new root.
• Similar to left rotation, it helps to restore balance and maintain the AVL tree properties.

Left-Right Rotation (LR Rotation):

• Used when the balance factor of a node becomes greater than 1 due to an insertion or deletion in the right subtree of its left child.
• It involves performing a left rotation on the left child followed by a right rotation on the unbalanced node.
• This operation corrects the imbalance and maintains the AVL tree properties.

Right-Left Rotation (RL Rotation):

• Used when the balance factor of a node becomes less than -1 due to an insertion or deletion in the left subtree of its right child.
• It involves performing a right rotation on the right child followed by a left rotation on the unbalanced node.
• Similar to LR rotation, it helps restore balance in the AVL tree.

SEARCH IN AVL TREE

In a balanced AVL tree, the height of the tree is guaranteed to be O(log n), where n is the number of nodes in the tree. This balanced height ensures that the search operation has a time complexity of O(log n) in the average and worst-case scenarios.

The reason for this time complexity is that at each level of the tree, the search space is effectively halved due to the balanced structure. Therefore, with each comparison, the search effectively eliminates half of the remaining nodes, leading to a logarithmic time complexity with respect to the number of nodes in the tree.

Algorithm:

Algorithm: AVL Tree Search

Step 1: Read the search element from the user.
Step 2: Call AVL_SEARCH(root, search_element).
Step 3: END.

Procedure AVL_SEARCH(node, search_element):
    Step 1: If node is NULL, return "Element is not found".
    Step 2: If search_element is equal to node -> DATA, then display "Given node is found!!!" and terminate.
    Step 3: If search_element is less than node -> DATA, then call AVL_SEARCH(node -> LEFT, search_element).
    Step 4: If search_element is greater than node -> DATA, then call AVL_SEARCH(node -> RIGHT, search_element).

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.

Algorithm:

Algorithm: AVL Tree Insertion

Step 1: Insert the new element into the tree using Binary Search Tree insertion logic.
Step 2: Call AVL_CHECK_BALANCE(root).
Step 3: END.

Procedure AVL_CHECK_BALANCE(node):
    Step 1: If node is NULL, return.
    Step 2: Calculate the balance factor (BF) of the node.
    Step 3: If the balance factor (BF) of the node is -1, 0, or 1, continue to the next node.
    Step 4: If the balance factor (BF) of the node is other than -1, 0, or 1, the tree is imbalanced.
    Step 5: Perform suitable rotation(s) to rebalance the tree.
    Step 6: Call AVL_CHECK_BALANCE(node -> LEFT) recursively.
    Step 7: Call AVL_CHECK_BALANCE(node -> RIGHT) recursively.

Example: Construct an AVL Tree by inserting numbers from 1 to 8.

Deletion Operation in AVL Tree

The deletion operation in AVL Tree is similar to the deletion operation in Binary Search Tree. But after every deletion operation, we need to check with the Balance Factor condition. If the tree is balanced after deletion go for the next operation otherwise perform suitable rotation to make the tree Balanced.