C++ Code For Balanced Binary Search Tree

8 min read Jul 01, 2024

C++ Code for Balanced Binary Search Tree

A balanced binary search tree is a binary search tree that maintains a certain balance, ensuring that the height of the tree remains relatively small. This prevents worst-case scenarios where the tree becomes a linear list, leading to inefficient search operations. There are several self-balancing algorithms, but the most common ones are AVL trees and red-black trees.

This article will focus on implementing a balanced binary search tree using the AVL algorithm in C++.

AVL Tree Properties

AVL trees ensure balance by adhering to these key properties:

Binary Search Tree Property: Every node in the left subtree has a value smaller than the root, and every node in the right subtree has a value larger than the root. This property enables efficient searching.
Height Balance Property: For every node in the tree, the heights of its left and right subtrees differ by at most 1. This property maintains the tree's balance.

C++ Implementation

Here's a C++ implementation of an AVL tree:

#include 

using namespace std;

// Node structure
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 get the maximum of two integers
int max(int a, int b) {
    return (a > b) ? a : b;
}

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

// Function to create a new node
Node *newNode(int data) {
    Node *node = new Node();
    node->data = data;
    node->height = 1;
    node->left = node->right = NULL;
    return node;
}

// Function to perform a 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 = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    // Return new root
    return x;
}

// Function to perform a 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 = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    // 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) {
        return newNode(data);
    }

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

    // Update height of the current node
    node->height = 1 + max(height(node->left), height(node->right));

    // Get the balance factor
    int balanceFactor = getBalanceFactor(node);

    // Left Left Case
    if (balanceFactor > 1 && data < node->left->data) {
        return rightRotate(node);
    }

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

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

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

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

// Function to print the AVL tree in inorder traversal
void inorder(Node *root) {
    if (root != NULL) {
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
}

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);

    cout << "Inorder traversal of the AVL tree: ";
    inorder(root);
    cout << endl;

    return 0;
}

Explanation

Node Structure: A Node structure stores the data, height, and pointers to the left and right children.
Height Calculation: The height function recursively calculates the height of a node based on the heights of its children.
Balance Factor: The getBalanceFactor function calculates the difference between the heights of the left and right subtrees to determine the balance of a node.
Rotations: The leftRotate and rightRotate functions perform the necessary rotations to maintain balance.
Insertion: The insert function first performs standard BST insertion and then checks for imbalance. It applies appropriate rotations based on the balance factor and the position of the newly inserted node.
Inorder Traversal: The inorder function traverses the AVL tree in inorder to print the nodes in sorted order.

Conclusion

This C++ code provides a basic implementation of an AVL tree, demonstrating how to maintain balance during insertion. By understanding these concepts, you can effectively implement and utilize balanced binary search trees in your C++ programs to achieve efficient search and insertion operations.

C++ Code For Balanced Binary Search Tree