Balanced Binary Search Tree C++

MUAZHAN

8 min read

·

Jun 28, 2024

31

Share

Balanced Binary Search Tree in C++

A balanced binary search tree is a binary search tree that maintains a balanced structure, ensuring that the height of the tree remains relatively small. This prevents worst-case scenarios where the tree degenerates into a linear linked list, leading to inefficient search, insertion, and deletion operations.

Why Balanced Binary Search Trees?

• Efficient Search: Balanced trees guarantee a logarithmic time complexity for search operations, making them significantly faster than unbalanced trees.
• Efficient Insertion and Deletion: Maintaining balance ensures that insertions and deletions also take logarithmic time, avoiding the potential for linear time complexity in unbalanced trees.
• Improved Space Complexity: While balanced trees might require slightly more memory for maintaining balance information, they generally offer better space utilization than unbalanced trees.

Popular Balanced Tree Algorithms

Several algorithms are used to maintain balance in binary search trees, each with its own strengths and weaknesses. Some of the most popular include:

• AVL Trees: AVL trees maintain balance by ensuring that the height difference between the left and right subtrees of every node is at most one. They are known for their strict balance constraints, resulting in more complex rotations during insertion and deletion.
• Red-Black Trees: Red-black trees utilize a color property for nodes (red or black) and use color flips and rotations to maintain balance. They offer a more relaxed balance compared to AVL trees, leading to simpler rotations and slightly lower performance in some scenarios.
• B-Trees: B-trees are primarily used in databases and file systems. They are designed for efficient disk access, especially for large datasets. They maintain balance by distributing data across multiple levels.

Implementing a Balanced Binary Search Tree in C++

Implementing a balanced binary search tree in C++ involves defining a tree node structure and implementing the core functions:

• Insertion: Inserting a new node while maintaining balance requires using the specific balancing algorithm.
• Deletion: Removing a node also requires maintaining balance using the chosen algorithm.
• Search: Searching for a specific node utilizes the binary search tree property.
• Minimum/Maximum: Finding the minimum or maximum element in the tree is straightforward due to the ordered structure.

Here's a simplified example of a balanced binary search tree implementation using the AVL algorithm:

#include 

// Node structure for AVL tree
struct Node {
    int data;
    int height;
    Node *left;
    Node *right;
};

// Function to calculate the height of a node
int height(Node *node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

// Function to calculate the balance factor of a node
int balanceFactor(Node *node) {
    if (node == NULL) {
        return 0;
    }
    return height(node->left) - height(node->right);
}

// Function to perform right rotation
Node* rightRotate(Node *y) {
    Node *x = y->left;
    Node *T2 = x->right;

    // Perform rotation
    x->right = y;
    y->left = T2;

    // Update heights
    y->height = 1 + std::max(height(y->left), height(y->right));
    x->height = 1 + std::max(height(x->left), height(x->right));

    // Return new root
    return x;
}

// Function to perform left rotation
Node* leftRotate(Node *x) {
    Node *y = x->right;
    Node *T2 = y->left;

    // Perform rotation
    y->left = x;
    x->right = T2;

    // Update heights
    x->height = 1 + std::max(height(x->left), height(x->right));
    y->height = 1 + std::max(height(y->left), height(y->right));

    // Return new root
    return y;
}

// Function to insert a new node into the AVL tree
Node* insert(Node *node, int data) {
    // Perform standard BST insertion
    if (node == NULL) {
        Node *newNode = new Node;
        newNode->data = data;
        newNode->height = 1;
        newNode->left = newNode->right = NULL;
        return newNode;
    }

    if (data < node->data) {
        node->left = insert(node->left, data);
    } else if (data > node->data) {
        node->right = insert(node->right, data);
    } else {
        return node; // Duplicate key, do nothing
    }

    // Update height of this ancestor node
    node->height = 1 + std::max(height(node->left), height(node->right));

    // Calculate balance factor of this ancestor node
    int balance = balanceFactor(node);

    // If this node becomes unbalanced
    // Left Left Case
    if (balance > 1 && data < node->left->data) {
        return rightRotate(node);
    }

    // Left Right Case
    if (balance > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // Right Right Case
    if (balance < -1 && data > node->right->data) {
        return leftRotate(node);
    }

    // Right Left Case
    if (balance < -1 && data < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    // Return the (unchanged) node pointer
    return node;
}

int main() {
    Node *root = NULL;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    // ... further operations on the AVL tree
}

This example demonstrates the insertion operation in an AVL tree. The other operations (deletion, search, min/max) would need to be implemented similarly, maintaining balance using appropriate rotations and height updates.

Remember that this is a simplified example. A complete implementation of a balanced binary search tree in C++ would require careful attention to memory management, error handling, and thorough testing.