- An AVL tree is a self-balancing binary search tree.
- It maintains a balance factor for each node, which is the difference between the heights of its left and right subtrees.
- The balance factor can be -1, 0, or 1. If the balance factor exceeds this range, the tree is unbalanced.
- After performing insertions or deletions that may violate the balance property, AVL trees automatically perform rotations to restore balance.
- The rotations include left rotation, right rotation, left-right rotation, and right-left rotation, depending on the specific case of imbalance.
- The balance property ensures that the height of an AVL tree remains logarithmic, resulting in efficient search, insertion, and deletion operations with a time complexity of O(log n), where n is the number of elements in the tree.

Here's an example of an AVL tree implementation in a high-level language like Python:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        self.root = self._insert(self.root, value)

    def _insert(self, node, value):
        if not node:
            return Node(value)

        if value < node.value:
            node.left = self._insert(node.left, value)
        else:
            node.right = self._insert(node.right, value)

        node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))
        balance = self._get_balance(node)

        if balance > 1:
            if value < node.left.value:
                return self._right_rotate(node)
            else:
                node.left = self._left_rotate(node.left)
                return self._right_rotate(node)

        if balance < -1:
            if value > node.right.value:
                return self._left_rotate(node)
            else:
                node.right = self._right_rotate(node.right)
                return self._left_rotate(node)

        return node

    def _get_height(self, node):
        if not node:
            return 0
        return node.height

    def _get_balance(self, node):
        if not node:
            return 0
        return self._get_height(node.left) - self._get_height(node.right)

    def _left_rotate(self, z):
        y = z.right
        T2 = y.left

        y.left = z
        z.right = T2

        z.height = 1 + max(self._get_height(z.left), self._get_height(z.right))
        y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))

        return y

    def _right_rotate(self, y):
        x = y.left
        T2 = x.right

        x.right = y
        y.left = T2

        y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))
        x.height = 1 + max(self._get_height(x.left), self._get_height(x.right))

    return x

This implementation includes the `Node` class to represent individual nodes in the AVL tree and the `AVLTree` class to handle the operations on the tree.

Algorithm

One of the commonly used balanced search tree algorithms in DAA (Design and Analysis of Algorithms) is the AVL tree. AVL tree is a self-balancing binary search tree where the heights of the left and right subtrees of any node differ by at most 1.

Here's the algorithm for AVL tree insertion:

AVL_Insert(root, key):
    if root is null:
        create a new node with key and return it

    if key < root.key:
        root.left = AVL_Insert(root.left, key)
    else if key > root.key:
        root.right = AVL_Insert(root.right, key)
    else:
    // Duplicate key, handle as per requirements
    return root

    // Update the height of the current node
    root.height = max(height(root.left), height(root.right)) + 1

    // Perform rotation to maintain balance
    balance = get_balance(root)

    // Left Left Case
    if balance > 1 and key < root.left.key:
        return right_rotate(root)

    // Right Right Case
    if balance < -1 and key > root.right.key:
        return left_rotate(root)

    // Left Right Case
    if balance > 1 and key > root.left.key:
        root.left = left_rotate(root.left)
        return right_rotate(root)

    // Right Left Case
    if balance < -1 and key < root.right.key:
        root.right = right_rotate(root.right)
        return left_rotate(root)

    return root

In this algorithm, `root` represents the root of the AVL tree, and `key` represents the value to be inserted.

The algorithm follows the standard BST insertion process. After inserting the key into the appropriate position, it updates the height of the current node. Then, it checks the balance factor of the current node to determine if any rotations are necessary to maintain the balance of the AVL tree.

The `get_balance` function calculates the balance factor of a node as the difference between the heights of its left and right subtrees.

The rotations (`left_rotate` and `right_rotate`) are performed to rebalance the tree when it becomes unbalanced. These rotations maintain the AVL tree property of having heights of left and right subtrees differ by at most 1.

The algorithm returns the root of the modified AVL tree after insertion.

Note that this algorithm assumes a basic understanding of binary search tree concepts, such as node insertion, height calculation, and rotations. The implementation may also include additional operations such as deletion and searching, but the provided algorithm focuses on the insertion process for an AVL tree.

Program

Certainly! Here's an example of a balanced search tree program using the AVL tree algorithm in DAA. This program includes node insertion, height calculation, and rotation operations.

class AVLNode:
def __init__(self, key):
    self.key = key
    self.left = None
    self.right = None
    self.height = 1

class AVLTree:
    def __init__(self):
        self.root = None

    def insert(self, key):
        self.root = self._insert_recursive(self.root, key)

    def _insert_recursive(self, root, key):
        if root is None:
            return AVLNode(key)

        if key < root.key:
            root.left = self._insert_recursive(root.left, key)
        else:
            root.right = self._insert_recursive(root.right, key)

        root.height = 1 + max(self._get_height(root.left), self._get_height(root.right))

        balance = self._get_balance(root)

        if balance > 1 and key < root.left.key:
            return self._right_rotate(root)

        if balance < -1 and key > root.right.key:
            return self._left_rotate(root)

        if balance > 1 and key > root.left.key:
            root.left = self._left_rotate(root.left)
            return self._right_rotate(root)

        if balance < -1 and key < root.right.key:
            root.right = self._right_rotate(root.right)
            return self._left_rotate(root)

        return root

    def _left_rotate(self, z):
        y = z.right
        T2 = y.left

        y.left = z
        z.right = T2

        z.height = 1 + max(self._get_height(z.left), self._get_height(z.right))
        y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))

        return y

    def _right_rotate(self, z):
        y = z.left
        T3 = y.right

        y.right = z
        z.left = T3

        z.height = 1 + max(self._get_height(z.left), self._get_height(z.right))
        y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))

        return y

    def _get_height(self, node):
        if node is None:
            return 0
        return node.height

    def _get_balance(self, node):
        if node is None:
            return 0
        return self._get_height(node.left) - self._get_height(node.right)

    def inorder_traversal(self):
        self._inorder_recursive(self.root)

    def _inorder_recursive(self, root):
        if root:
            self._inorder_recursive(root.left)
            print(root.key, end=" ")
            self._inorder_recursive(root.right)


# Example usage
avl_tree = AVLTree()
avl_tree.insert(9)
avl_tree.insert(5)
avl_tree.insert(10)
avl_tree.insert(0)
avl_tree.insert(6)
avl_tree.insert(11)
avl_tree.insert(-1)
avl_tree.insert(1)
avl_tree.insert(2)

print("Inorder Traversal:")
avl_tree.inorder_traversal()

In this program, `AVLNode` represents a node in the AVL tree. It includes attributes such as the `key` value, left and right child references, and the height of the node.

The `AVLTree` class represents the AVL tree itself. It includes methods for node insertion (`insert`), height calculation (`_get_height`), balance factor calculation (`_get_balance`), and rotation operations (`_left_rotate’).

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc