Binary search tree

A Binary Search Tree (BST) is a specialized type of binary tree that ensures its nodes are arranged in a specific order. Each node has at most two children: a left child and a right child. The left subtree of a node contains nodes with values less than the node’s value, while the right subtree contains nodes with values greater than the node’s value. This property allows efficient searching, insertion, and deletion operations.

Key Characteristics of BST

• Nodes: Each node contains a value and pointers to its left and right children.
• Ordering Property: All values in the left subtree of a node are less than the node’s value, and all values in the right subtree are greater.
• Dynamic Structure: BSTs adjust dynamically to the data inserted.

Why Use a BST?

BSTs are widely used due to their efficiency in search, insertion, and deletion operations:

• Searching: Average-case time complexity of O(log n).
• Insertion: Average-case time complexity of O(log n).
• Deletion: Average-case time complexity of O(log n).
• Range Queries: Efficient for retrieving all elements in a given range.

Implementing a BST in C++

Here’s a basic implementation of a BST in C++:

Node Structure

Each node in a BST contains a value, a pointer to the left child, and a pointer to the right child.

struct Node {
    int value;
    Node* left;
    Node* right;

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

Basic BST Operations

To insert a new node, the tree is traversed starting from the root, comparing values to maintain the BST properties.cpp

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

Searching is done by traversing the tree from the root and comparing values to find the desired node.

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

In-order traversal visits nodes in ascending order.

void inorder(Node* root) {
    if (root == nullptr) return;
    inorder(root->left);
    std::cout << root->value << " ";
    inorder(root->right);
}

Deletion involves three cases: the node has no children, one child, or two children.

Node* findMin(Node* root) {
    while (root->left != nullptr) root = root->left;
    return root;
}

Node* remove(Node* root, int val) {
    if (root == nullptr) return root;
    if (val < root->value) {
        root->left = remove(root->left, val);
    } else if (val > root->value) {
        root->right = remove(root->right, val);
    } else {
        // Node to be deleted found
        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 = findMin(root->right);
        root->value = temp->value;
        root->right = remove(root->right, temp->value);
    }
    return root;
}

Advanced Concepts in BST

1. Self-Balancing BSTs To avoid degeneracy, BSTs like AVL trees and Red-Black trees maintain balance through rotations.
   • AVL Trees: Balances the tree using height differences.
   • Red-Black Trees: Uses a color scheme to maintain approximate balance.
2. Threaded BSTs Threaded BSTs replace null pointers with links to in-order successor nodes to optimize traversal.
3. Augmented BSTs These BSTs store extra data in each node for advanced operations like finding the kth smallest element.

Practical Applications of BSTs

1. Databases: Used in indexing for fast data retrieval.
2. File Systems: For managing file directories.
3. Priority Queues: When implemented using self-balancing BSTs.
4. Autocomplete Systems: For searching through dictionaries.

Performance Analysis

BST performance depends on the balance of the tree:

• Balanced BST: Average O(log n) for search, insertion, and deletion.
• Unbalanced BST: Degenerates to a linked list with O(n) complexity.

Limitations of BSTs

• Unbalanced Trees: Can degrade performance.
• Complex Rotations: Required for balancing self-balancing trees.
• Space Usage: Each node requires extra space for child pointers.