Binary Search Trees

A binary search tree (BST) is a binary tree data structure that maintains the property that the value of each node is greater than or equal to the values of all nodes in its left subtree and less than or equal to the values of all nodes in its right subtree. This property ensures that an inorder traversal of the tree will result in the sorted order of the elements.

Operations

The main operations on a binary search tree are insertion, deletion, and search.

Insertion

To insert a new value into a BST, we start at the root and compare the new value to the value of the current node. If the new value is less than the current node's value, we move to the left subtree; otherwise, we move to the right subtree. We repeat this process until we reach a null pointer, where we create a new node with the new value and insert it.

Example:

Node* insert(Node* root, int value) {
    if (root == nullptr) {
        return new Node(value);
    }

    if (value < root->data) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }

    return root;
}

Deletion

To delete a value from a BST, we first search for the node containing the value. If the node has no children, we simply remove it. If the node has one child, we replace the node with its child. If the node has two children, we find the inorder successor (or predecessor) of the node, replace the node with the successor, and then delete the successor.

Example:

Node* minValueNode(Node* node) {
    Node* current = node;

    while (current && current->left) {
        current = current->left;
    }

    return current;
}

Node* deleteNode(Node* root, int value) {
    if (root == nullptr) {
        return root;
    }

    if (value < root->data) {
        root->left = deleteNode(root->left, value);
    } else if (value > root->data) {
        root->right = deleteNode(root->right, value);
    } 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;
}

Search

To search for a value in a BST, we start at the root and compare the target value to the value of the current node. If the target value is less than the current node's value, we move to the left subtree; otherwise, we move to the right subtree. We repeat this process until we find the target value or reach a null pointer.

Example:

bool search(Node* root, int value) {
    if (root == nullptr) {
        return false;
    }

    if (root->data == value) {
        return true;
    }

    if (value < root->data) {
        return search(root->left, value);
    } else {
        return search(root->right, value);
    }
}

Time Complexity

The time complexity of BST operations is O(h), where h is the height of the tree. In the worst case, a BST can be completely unbalanced, resulting in a height of O(n) for n nodes, causing the operations to have a time complexity of O(n). However, in the best case and average case, a BST is balanced or nearly balanced, resulting in a height of O(log n), which leads to a time complexity of O(log n) for the operations.

Balanced Binary Search Trees

To avoid the worst-case scenario of an unbalanced BST, various types of balanced binary search trees have been developed. These trees ensure that the height of the tree remains logarithmic with respect to the number of nodes, thus providing better performance guarantees. Some examples of balanced binary search trees include:

• AVL trees
• Red-Black trees
• B-trees

Applications

Binary search trees are widely used in various applications, such as:

• Databases and file systems for efficient search, insertion, and deletion operations.
• Symbol tables in compilers and interpreters for storing and retrieving variable information.
• Implementing associative arrays, sets, and maps in programming languages.

See Also

• Heaps
• Hash Tables
• Trees
• Binary Trees