BST (Binary Search Tree) and AVL Tree, Data Structures: (Trees, Part II)

Binary Search Tree (BST)

A Binary Search Tree (BST) is a binary tree data structure where each node has at most two children, referred to as the left child and the right child. The key property of a BST is that for every node, all elements in its left subtree are less than or equal to the node's value, and all elements in its right subtree are greater than the node's value. This property allows for efficient search, insertion, and deletion operations.

Key Properties of BST:

1. Ordering Property: For any node N, all elements in the left subtree of N are less than or equal to the value of N, and all elements in the right subtree of N are greater than the value of N.

2. No Duplicates: BSTs typically do not allow duplicate elements. If a duplicate element is encountered during insertion, it can either be ignored or handled in a specific manner based on the implementation.

3. Efficient Operations: BSTs support efficient search, insertion, and deletion operations. Searching for an element in a BST has a time complexity of O(log n) on average, where n is the number of nodes in the tree. This efficiency is due to the binary search property, which allows us to eliminate half of the nodes at each step of the search.

4. In-order Traversal: Performing an in-order traversal of a BST results in a sorted sequence of elements. This property is useful for tasks such as finding the k-th smallest/largest element in the tree.

Advantages of BST:

• Efficient Searching: BSTs provide efficient searching, making them suitable for applications where fast retrieval of data is required, such as databases and search algorithms.

• Ordered Structure: The ordering property of BSTs allows for easy traversal of elements in sorted order, facilitating tasks like range queries and finding minimum and maximum elements.

• Dynamic Structure: BSTs can dynamically grow and shrink based on the number of elements inserted or deleted, making them adaptable to changing data sets.

Limitations of BST:

• Imbalanced Trees: In certain scenarios, such as when elements are inserted in sorted order, BSTs can become highly imbalanced, leading to degraded performance. This issue can be mitigated through techniques like AVL trees and Red-Black trees, which ensure balanced tree structures.

• Performance Degradation: Although BSTs offer efficient operations on average, their performance can degrade to O(n) in the worst case, particularly for skewed trees. This can occur if elements are inserted in a sorted order, resulting in a linear chain-like structure.

Binary Search Trees are fundamental data structures with a wide range of applications due to their efficiency and versatility in storing and retrieving data. Understanding their properties and operations is essential for designing and implementing efficient algorithms and applications.

Implementation of Binary Search Tree in C++

Binary Search Trees (BSTs) are a fundamental data structure used for efficient storage and retrieval of data. They maintain a sorted order of elements, allowing for fast search, insertion, and deletion operations. Below is a class-based implementation of a Binary Search Tree in C++, including attributes, constructor, destructor, and a method for inserting elements into the tree.

#include <iostream>
using namespace std;

class BST {
private:
    struct Node {
        int data;
        Node* left;
        Node* right;

        Node(int val) : data(val), left(nullptr), right(nullptr) {}
    };

    Node* root;

public:
    BST() : root(nullptr) {}

    ~BST() {
        clear(root);
    }

    void insert(int value) {
        root = insertNode(root, value);
    }

private:
    Node* insertNode(Node* node, int value) {
        if (node == nullptr) {
            return new Node(value);
        }
        if (value < node->data) {
            node->left = insertNode(node->left, value);
        } else {
            node->right = insertNode(node->right, value);
        }
        return node;
    }

    void clear(Node* node) {
        if (node != nullptr) {
            clear(node->left);
            clear(node->right);
            delete node;
        }
    }
};

This implementation provides the basic framework for a Binary Search Tree. The BST class contains a private nested Node struct to represent individual nodes of the tree. It includes a constructor to initialize the root node to nullptr and a destructor to deallocate memory by recursively deleting all nodes.

The insert() method allows for the insertion of elements into the BST while maintaining its binary search property. It recursively traverses the tree to find the appropriate position for the new element and creates a new node with the given value.

This code serves as a foundation for building more advanced BST functionalities, such as search, deletion, traversal, and other operations. Further enhancements and optimizations can be made based on specific requirements and use cases.

Operations on Binary Search Tree (BST)

Binary Search Trees (BSTs) are versatile data structures that facilitate efficient manipulation and retrieval of data. By maintaining the binary search property, BSTs enable essential operations such as searching, insertion, and deletion.

Search Operation

Searching in a BST involves traversing the tree from the root node to find the target element. The algorithm compares the target value with the value of each node, guiding the search path towards the desired element.

bool search(Node* root, int target) {
    if (root == nullptr) {
        return false;
    }
    if (root->data == target) {
        return true;
    }
    if (target < root->data) {
        return search(root->left, target);
    } else {
        return search(root->right, target);
    }
}

Time Complexity: O(h) (worst case: O(n))

Insertion Operation

Inserting a new element into a BST involves finding the appropriate position for the new node based on its value. The algorithm recursively traverses the tree, adjusting the structure to maintain the binary search property.

Node* insert(Node* root, int value) {
    if (root == nullptr) {
        return new Node(value);
    }
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    return root;
}

Time Complexity: O(h) (worst case: O(n))

Deletion Operation

Deleting an element from a BST requires locating the node containing the target value and adjusting the tree structure while preserving the binary search property.

Node* deleteNode(Node* root, int key) {
    if (root == nullptr) {
        return root;
    }
    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    } else {
        if (root->left == nullptr) {
            Node* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            Node* temp = root->left;
            delete root;
            return temp;
        }
        Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

Time Complexity: O(h) (worst case: O(n))

These operations are fundamental for maintaining the integrity of a BST and ensuring efficient data management. Understanding their complexities aids in designing optimal algorithms and applications utilizing BSTs.

Full Code Implementation of BST

A Binary Search Tree (BST) is a fundamental data structure that maintains a sorted order of elements, allowing for efficient search, insertion, and deletion operations. This implementation provides a comprehensive class-based approach to constructing and manipulating BSTs in C++.

#include <iostream>
using namespace std;

class BST {
private:
    struct Node {
        int data;
        Node* left;
        Node* right;

        Node(int val) : data(val), left(nullptr), right(nullptr) {}
    };

    Node* root;

public:
    BST() : root(nullptr) {}

    ~BST() {
        clear(root);
    }

    void insert(int value) {
        root = insertNode(root, value);
    }

    bool search(int target) {
        return searchNode(root, target);
    }

    void remove(int key) {
        root = deleteNode(root, key);
    }

private:
    Node* insertNode(Node* node, int value) {
        if (node == nullptr) {
            return new Node(value);
        }
        if (value < node->data) {
            node->left = insertNode(node->left, value);
        } else if (value > node->data) {
            node->right = insertNode(node->right, value);
        }
        return node;
    }

    bool searchNode(Node* node, int target) {
        if (node == nullptr) {
            return false;
        }
        if (node->data == target) {
            return true;
        }
        if (target < node->data) {
            return searchNode(node->left, target);
        } else {
            return searchNode(node->right, target);
        }
    }

    Node* deleteNode(Node* node, int key) {
        if (node == nullptr) {
            return node;
        }
        if (key < node->data) {
            node->left = deleteNode(node->left, key);
        } else if (key > node->data) {
            node->right = deleteNode(node->right, key);
        } else {
            if (node->left == nullptr) {
                Node* temp = node->right;
                delete node;
                return temp;
            } else if (node->right == nullptr) {
                Node* temp = node->left;
                delete node;
                return temp;
            }
            Node* temp = minValueNode(node->right);
            node->data = temp->data;
            node->right = deleteNode(node->right, temp->data);
        }
        return node;
    }

    Node* minValueNode(Node* node) {
        Node* current = node;
        while (current && current->left != nullptr) {
            current = current->left;
        }
        return current;
    }

    void clear(Node* node) {
        if (node != nullptr) {
            clear(node->left);
            clear(node->right);
            delete node;
        }
    }
};

int main() {
    BST bst;

    // Insert some elements
    bst.insert(50);
    bst.insert(30);
    bst.insert(20);
    bst.insert(40);
    bst.insert(70);
    bst.insert(60);
    bst.insert(80);

    // Search for elements
    cout << "Searching for 30: " << (bst.search(30) ? "Found" : "Not Found") << endl;
    cout << "Searching for 45: " << (bst.search(45) ? "Found" : "Not Found") << endl;

    // Remove an element
    bst.remove(30);
    cout << "After removing 30, searching for 30: " << (bst.search(30) ? "Found" : "Not Found") << endl;

    return 0;
}

This code demonstrates the class-based implementation of a Binary Search Tree (BST) in C++. It includes methods for insertion, searching, and deletion of elements, along with a main function showcasing the usage of these methods.

Binary Search Trees are versatile data structures with various applications in computer science. Understanding their implementation and operations is essential for developing efficient algorithms and applications.

AVL Tree (BST)

An AVL tree is a type of self-balancing binary search tree named after its inventors Adelson-Velsky and Landis. It maintains the binary search tree property while ensuring that the tree remains balanced, which guarantees better performance for various operations. Here’s everything important to know about AVL trees:

Key Properties of AVL Tree:

1. Balanced 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 performed to restore this property.

2. Height-Balanced: An AVL tree ensures that the height difference (balance factor) between the left and right subtrees for any node is no more than one. This balance factor is crucial for maintaining the tree’s efficiency.

3. Self-Balancing: The AVL tree automatically balances itself with each insertion and deletion operation. This ensures that the tree remains balanced and the operations remain efficient.

Balancing Factor:

• The balancing factor of a node in an AVL tree is the difference in heights between its left and right subtrees. It is calculated as:

  BalanceFactor = Height(Left Subtree) - Height(Right Subtree)

• The balance factor can be -1, 0, or +1. If it goes outside this range, rebalancing is required.

Rotations:

To maintain balance, AVL trees perform rotations. There are four types of rotations:

1. Left Rotation (LL Rotation): Performed when a node is inserted into the right subtree of a right subtree, causing an imbalance.
2. Right Rotation (RR Rotation): Performed when a node is inserted into the left subtree of a left subtree, causing an imbalance.
3. Left-Right Rotation (LR Rotation): Performed when a node is inserted into the right subtree of a left subtree, causing an imbalance.
4. Right-Left Rotation (RL Rotation): Performed when a node is inserted into the left subtree of a right subtree, causing an imbalance.

Advantages of AVL Tree:

• Balanced Structure: Ensures that the tree remains balanced after every insertion and deletion, guaranteeing O(log n) time complexity for search, insert, and delete operations.
• Efficient Lookups: Due to the balanced nature, lookups are efficient and fast.

Limitations of AVL Tree:

• Complex Implementation: AVL trees are more complex to implement than simple binary search trees due to the need for balancing operations.
• Higher Maintenance Cost: The need to perform rotations can add overhead during insertion and deletion.

Understanding AVL Trees is crucial for applications requiring balanced tree structures, such as databases and search algorithms. AVL Trees provide efficient operations while maintaining balance, ensuring optimal performance.

Rotation

In AVL trees, rotations are fundamental operations used to maintain the balance of the tree after insertions and deletions. Rotations help to rebalance the tree by adjusting the positions of the nodes while preserving the binary search tree property. There are four types of rotations: left rotation, right rotation, left-right rotation, and right-left rotation. Each rotation addresses a specific imbalance scenario in the tree.

Left Rotation (LL Rotation)

A left rotation is performed when a node becomes unbalanced due to an insertion in the right subtree of its right child. This rotation involves moving the right child up to become the new root of the subtree, with the original root becoming the left child of the new root.

Node* leftRotate(Node* root) {
    Node* newRoot = root->right;
    Node* leftSubtreeOfNewRoot = newRoot->left;

    // Perform rotation
    newRoot->left = root;
    root->right = leftSubtreeOfNewRoot;

    // Update heights
    root->height = max(height(root->left), height(root->right)) + 1;
    newRoot->height = max(height(newRoot->left), height(newRoot->right)) + 1;

    // Return new root
    return newRoot;
}

Explanation:

1. Store the right child (newRoot) of the node to be rotated (root) and the left subtree (leftSubtreeOfNewRoot) of newRoot.
2. Perform the rotation by making newRoot the new root of the subtree, with root as its left child and leftSubtreeOfNewRoot as the right child of root.
3. Update the heights of root and newRoot.
4. Return the new root of the subtree (newRoot).

Right Rotation (RR Rotation)

A right rotation is performed when a node becomes unbalanced due to an insertion in the left subtree of its left child. This rotation involves moving the left child up to become the new root of the subtree, with the original root becoming the right child of the new root.

Node* rightRotate(Node* root) {
    Node* newRoot = root->left;
    Node* rightSubtreeOfNewRoot = newRoot->right;

    // Perform rotation
    newRoot->right = root;
    root->left = rightSubtreeOfNewRoot;

    // Update heights
    root->height = max(height(root->left), height(root->right)) + 1;
    newRoot->height = max(height(newRoot->left), height(newRoot->right)) + 1;

    // Return new root
    return newRoot;
}

Explanation:

1. Store the left child (newRoot) of the node to be rotated (root) and the right subtree (rightSubtreeOfNewRoot) of newRoot.
2. Perform the rotation by making newRoot the new root of the subtree, with root as its right child and rightSubtreeOfNewRoot as the left child of root.
3. Update the heights of root and newRoot.
4. Return the new root of the subtree (newRoot).

Left-Right Rotation (LR Rotation)

A left-right rotation is a combination of a left rotation followed by a right rotation. It is performed when a node becomes unbalanced due to an insertion in the right subtree of its left child.

Node* leftRightRotate(Node* root) {
    root->left = leftRotate(root->left);
    return rightRotate(root);
}

Explanation:

1. First, perform a left rotation on the left child of the unbalanced node (root).
2. Then, perform a right rotation on the unbalanced node itself (root).
3. This two-step process balances the tree.

Right-Left Rotation (RL Rotation)

A right-left rotation is a combination of a right rotation followed by a left rotation. It is performed when a node becomes unbalanced due to an insertion in the left subtree of its right child.

Node* rightLeftRotate(Node* root) {
    root->right = rightRotate(root->right);
    return leftRotate(root);
}

Explanation:

1. First, perform a right rotation on the right child of the unbalanced node (root).
2. Then, perform a left rotation on the unbalanced node itself (root).
3. This two-step process balances the tree.

Rotations in AVL trees are essential for maintaining balance after insertions and deletions. Each type of rotation addresses a specific imbalance scenario, ensuring that the tree remains height-balanced and operations such as search, insertion, and deletion remain efficient with a time complexity of O(log n).

Implementation of AVL Tree in C++

AVL trees are self-balancing binary search trees that ensure logarithmic time complexity for essential operations like insertion, deletion, and search. This makes them suitable for scenarios where dynamic data storage with efficient lookup operations is required. Here's a class-based implementation of an AVL tree in C++, including a method for insertion.

#include <iostream>
using namespace std;

class AVLTree {
private:
    struct Node {
        int data;
        Node* left;
        Node* right;
        int height;

        Node(int val) : data(val), left(nullptr), right(nullptr), height(1) {}
    };

    Node* root;

public:
    AVLTree() : root(nullptr) {}

    ~AVLTree() {
        clear(root);
    }

    void insert(int value) {
        root = insertNode(root, value);
    }

private:
    int height(Node* node) {
        if (node == nullptr) {
            return 0;
        }
        return node->height;
    }

    int getBalance(Node* node) {
        if (node == nullptr) {
            return 0;
        }
        return height(node->left) - height(node->right);
    }

    Node* rightRotate(Node* root) {
        Node* newRoot = root->left;
        Node* rightSubtreeOfNewRoot = newRoot->right;

        // Perform rotation
        newRoot->right = root;
        root->left = rightSubtreeOfNewRoot;

        // Update heights
        root->height = max(height(root->left), height(root->right)) + 1;
        newRoot->height = max(height(newRoot->left), height(newRoot->right)) + 1;

        // Return new root
        return newRoot;
    }

    Node* leftRotate(Node* root) {
        Node* newRoot = root->right;
        Node* leftSubtreeOfNewRoot = newRoot->left;

        // Perform rotation
        newRoot->left = root;
        root->right = leftSubtreeOfNewRoot;

        // Update heights
        root->height = max(height(root->left), height(root->right)) + 1;
        newRoot->height = max(height(newRoot->left), height(newRoot->right)) + 1;

        // Return new root
        return newRoot;
    }

    Node* insertNode(Node* node, int value) {
        if (node == nullptr) {
            return new Node(value);
        }

        if (value < node->data) {
            node->left = insertNode(node->left, value);
        } else if (value > node->data) {
            node->right = insertNode(node->right, value);
        } else {
            return node;
        }

        node->height = 1 + max(height(node->left), height(node->right));

        int balance = getBalance(node);

        if (balance > 1 && value < node->left->data) {
            return rightRotate(node);
        }

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

        if (balance > 1 && value > node->left->data) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }

        if (balance < -1 && value < node->right->data) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }

        return node;
    }

    void clear(Node* node) {
        if (node != nullptr) {
            clear(node->left);
            clear(node->right);
            delete node;
        }
    }
};

AVL trees are efficient data structures that provide fast insertion, deletion, and search operations while maintaining balance. This implementation of an AVL tree in C++ offers a foundation for building more advanced functionality, such as deletion, traversal, and other operations. Understanding AVL trees and their properties is essential for designing and implementing efficient algorithms and applications that require dynamic data storage.