Balanced Binary Tree in Data Structure

Hey, is this you?

You want to learn Data Science but have no idea where to start?

I understand there’s an overwhelming amount of information out there, making it hard to even find a starting point.

Resources like courses and coaching programs that promise well-structured information often cost thousands of dollars.

But it doesn’t have to be this way.

I’ve curated 101+ free resources for you to learn Data Science in 90 days.

It covers:

• Programming
• Mathematics
• Data Analytics
• Machine Learning
• And much more…

Why don’t you give it a try?

Download Free Resources.

What is Balanced Binary Tree

A balanced binary tree is a type of binary tree where the height of the left and right subtrees of any node differ by at most one. Balanced trees are essential in computer science because they ensure that the operations of insertion, deletion, and lookup can be performed in O(log n) time. This efficiency makes balanced trees ideal for implementing dynamic sets and lookup tables, which are fundamental components in many applications.

Why Balance is Important

Balancing a binary tree is crucial for maintaining optimal time complexity. Without balancing, a binary tree can degenerate into a linked list in the worst-case scenario, causing operations to take O(n) time. A balanced tree, however, maintains O(log n) performance, making it significantly more efficient for large datasets.

Types of Balanced Binary Trees

There are several types of balanced binary trees, each with its own balancing criteria and rotation mechanisms. The most common types include:

1. AVL Trees
2. Red-Black Trees
3. Splay Trees
4. B-Trees

Let’s delve into each type to understand their structure, operations, and balancing mechanisms.

AVL Trees

AVL Tree (named after inventors Adelson-Velsky and Landis) is the first self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. If at any time they differ by more than one, rebalancing is done using rotations.

• Rotations in AVL Trees: There are four types of rotations used to balance an AVL tree:
• Left Rotation (LL Rotation)
• Right Rotation (RR Rotation)
• Left-Right Rotation (LR Rotation)
• Right-Left Rotation (RL Rotation)
• Insertion: When a new node is inserted, the tree may become unbalanced. To restore balance, appropriate rotations are performed.
• Deletion: Similar to insertion, deletion can unbalance the tree, requiring rotations to rebalance.

Advantages:

• Guarantees O(log n) time complexity for search, insertion, and deletion.
• Well-suited for read-heavy applications.

Red-Black Trees

Get Amit Yadav’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Red-Black Tree is a type of self-balancing binary search tree. Each node stores an extra bit representing “color” (“red” or “black”), and this color is used to ensure the tree remains balanced during insertions and deletions.

Properties:

• Each node is either red or black.
• The root is always black.
• Red nodes cannot have red children (no two red nodes can be adjacent).
• Every path from a node to its descendant null nodes has the same number of black nodes.
• Rotations and Recoloring: These are used to maintain balance during insertions and deletions.

Advantages:

• Guarantees O(log n) time complexity.
• Easier to implement compared to AVL trees.

Splay Trees

Splay Tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again.

• Splaying: This is the process of moving a node to the root of the tree through a series of tree rotations.
• Operations: Insertion, deletion, and search operations splay the accessed node, bringing it to the root.

Advantages:

• Good for caches and applications where locality of reference is important.

B-Trees

B-Tree is a generalization of a binary search tree in which a node can have more than two children. B-Trees are commonly used in databases and filesystems.

• Properties:
• All leaf nodes are at the same level.
• A node contains a certain number of keys and children pointers.
• Nodes are kept balanced through splitting and merging during insertions and deletions.

Advantages:

• Suitable for storage systems that read and write large blocks of data.

Implementing a Balanced Binary Tree

Implementing a balanced binary tree involves several key steps:

1. Node Structure: Define the structure of a tree node.
2. Insertion: Implement the insertion algorithm, ensuring that the tree remains balanced.
3. Deletion: Implement the deletion algorithm, ensuring that the tree remains balanced.
4. Balancing: Implement the balancing logic, including rotations.

Example: AVL Tree Implementation

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

def insert(root, key):
    if not root:
        return TreeNode(key)
    elif key < root.val:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
        
    root.height = 1 + max(get_height(root.left), get_height(root.right))
    
    balance = get_balance(root)
    
    if balance > 1 and key < root.left.val:
        return right_rotate(root)
    
    if balance < -1 and key > root.right.val:
        return left_rotate(root)
    
    if balance > 1 and key > root.left.val:
        root.left = left_rotate(root.left)
        return right_rotate(root)
    
    if balance < -1 and key < root.right.val:
        root.right = right_rotate(root.right)
        return left_rotate(root)
    
    return root

def left_rotate(z):
    y = z.right
    T2 = y.left
    y.left = z
    z.right = T2
    z.height = 1 + max(get_height(z.left), get_height(z.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    return y

def right_rotate(z):
    y = z.left
    T3 = y.right
    y.right = z
    z.left = T3
    z.height = 1 + max(get_height(z.left), get_height(z.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    return y

def get_height(root):
    if not root:
        return 0
    return root.height

def get_balance(root):
    if not root:
        return 0
    return get_height(root.left) - get_height(root.right)

Conclusion

Balanced binary trees are critical for maintaining efficient data operations in computer science. Understanding the different types of balanced binary trees, such as AVL trees, Red-Black trees, Splay trees, and B-trees, is essential for selecting the right data structure for a given application. Implementing these trees involves mastering their balancing techniques and rotation mechanisms to ensure optimal performance.