Balanced Binary Trees

---

A Balanced Binary Tree is a binary tree in which the difference in height between the left and right subtrees of any node is minimized, ensuring the tree remains well-balanced. This balance property allows for efficient operations such as searching, insertion, and deletion, which is crucial in many computer science algorithms.

---

What is a Balanced Binary Tree?

A Balanced Binary Tree is defined as a binary tree where the difference in height between the left and right subtrees of every node is no more than a specified value (usually 1). This ensures that the tree does not become skewed, maintaining optimal efficiency for operations such as insertion, deletion, and search.

Key Properties of a Balanced Binary Tree:

1. Balance Factor: The balance factor of a node is the difference between the height of the left subtree and the height of the right subtree. For the tree to be balanced, the balance factor of each node must lie between -1 and 1: $$-1\le \text{balance factor}\le 1$$
2. Efficient Search Operations: Since the height is kept in check, the search, insertion, and deletion operations in a balanced binary tree run in $O(\log n)$ time, where $n$ is the number of nodes in the tree.
3. Height of the Tree: The height of a balanced binary tree is kept minimal, ensuring that the tree does not degenerate into a linked list, as can happen with unbalanced trees.

Example of a Balanced Binary Tree:

Here is an example of a balanced binary tree:

        4
       / \
      2   6
     / \ / \
    1  3 5  7

In this tree:

• The balance factor of every node is between -1 and 1.
• The tree is "balanced," meaning it has a minimal height relative to the number of nodes.

---

Types of Balanced Binary Trees

1. AVL Tree

An AVL Tree (named after its inventors Adelson-Velsky and Landis) is a type of self-balancing binary search tree. It maintains its balance by ensuring that the difference between the heights of the left and right subtrees of any node is at most 1.

Operations:

• Insertion: After inserting a node, the tree may become unbalanced, and rotations are performed to restore the balance.
• Deletion: Similar to insertion, after deleting a node, rotations may be necessary to restore the balance of the tree.
• Rotations: AVL Trees use four types of rotations to maintain balance:
  1. Left Rotation (LL Rotation)
  2. Right Rotation (RR Rotation)
  3. Left-Right Rotation (LR Rotation)
  4. Right-Left Rotation (RL Rotation)

2. Red-Black Tree

A Red-Black Tree is another type of self-balancing binary search tree. It is slightly more relaxed than an AVL Tree, which allows for faster insertions and deletions at the cost of slightly slower search operations. The key properties of a Red-Black Tree include:

• Each node is either red or black.
• The root is always black.
• Every leaf (NIL node) is black.
• Red nodes cannot have red children (i.e., no two red nodes can be adjacent).
• From any node, the path to its descendant leaves must have the same number of black nodes.

---

Operations on Balanced Binary Trees

1. Insertion in a Balanced Binary Tree

Insertion in a balanced binary tree, like an AVL tree, involves two steps:

1. Insert the new node in the correct position, just like in a regular binary search tree.
2. Rebalance the tree by performing rotations if necessary to maintain the balance factor.

For Red-Black trees, insertion also involves color changes and rotations to maintain the Red-Black properties.

2. Deletion in a Balanced Binary Tree

Deleting a node in a balanced binary tree involves:

1. Removing the node.
2. Rebalancing the tree through rotations if necessary to maintain balance.

3. Traversal of a Balanced Binary Tree

Traversal is the process of visiting each node in the tree in a specific order:

• Preorder Traversal: Visit the root, traverse the left subtree, then traverse the right subtree.
• Inorder Traversal: Traverse the left subtree, visit the root, then traverse the right subtree.
• Postorder Traversal: Traverse the left subtree, traverse the right subtree, then visit the root.
• Level-order Traversal: Traverse the tree level by level.

---

Code Example: AVL Tree in Python

Below is a Python implementation of an AVL Tree that supports insertion, rotation to maintain balance, and in-order traversal.

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

class AVLTree:
    def insert(self, root, key):
        if not root:
            return Node(key)
        
        if key < root.value:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)
        
        root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
        
        balance = self.getBalance(root)
        
        # Left heavy
        if balance > 1 and key < root.left.value:
            return self.rightRotate(root)
        
        # Right heavy
        if balance < -1 and key > root.right.value:
            return self.leftRotate(root)
        
        # Left-right case
        if balance > 1 and key > root.left.value:
            root.left = self.leftRotate(root.left)
            return self.rightRotate(root)
        
        # Right-left case
        if balance < -1 and key < root.right.value:
            root.right = self.rightRotate(root.right)
            return self.leftRotate(root)
        
        return root
    
    def leftRotate(self, z):
        y = z.right
        T2 = y.left
        
        y.left = z
        z.right = T2
        
        z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
        
        return y
    
    def rightRotate(self, z):
        y = z.left
        T3 = y.right
        
        y.right = z
        z.left = T3
        
        z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
        
        return y
    
    def getHeight(self, root):
        if not root:
            return 0
        return root.height
    
    def getBalance(self, root):
        if not root:
            return 0
        return self.getHeight(root.left) - self.getHeight(root.right)
    
    def inorderTraversal(self, root):
        if not root:
            return
        self.inorderTraversal(root.left)
        print(root.value, end=" ")
        self.inorderTraversal(root.right)

# Example Usage
avl = AVLTree()
root = None

# Inserting nodes
nodes = [10, 20, 30, 40, 50, 25]
for node in nodes:
    root = avl.insert(root, node)

# Inorder Traversal
print("Inorder Traversal of AVL Tree:")
avl.inorderTraversal(root)

Output:

Inorder Traversal of AVL Tree:
10 20 25 30 40 50

---

Applications of Balanced Binary Trees

1. Efficient Searching: Balanced binary trees like AVL and Red-Black trees are used in searching algorithms because they provide fast search times of $O(\log n)$.

2. Priority Queues: Heaps, a specialized form of binary trees, are used in priority queues where balanced trees help maintain the optimal time for inserting and deleting elements.

3. Database Indexing: Balanced binary trees, particularly B-trees, are used for indexing in databases. They ensure efficient searching, insertion, and deletion in large datasets.

4. Memory Management: Balanced binary trees are often used in memory management algorithms for efficient space allocation.

---

---