Binary Search Tree (BST) Explained

1. Definition

A Binary Search Tree (BST) is a binary tree in which each node contains a key and satisfies the following properties:

• For every node, all keys in its left subtree are less than the node's key.
• For every node, all keys in its right subtree are greater than the node's key.
• Both the left and right subtrees are binary search trees.

2. Operations

Insertion Operation

Insert a new key into the BST. During insertion, the position is determined by comparing key values. The specific steps are:

1. Start from the root node, compare the new key with the current node's key.
2. If the new key is less than the current node's key, move to the left subtree; otherwise, move to the right subtree.
3. Repeat the above steps until an empty position is found, and insert the new key there.

The code implementation for the insertion operation is as follows:

// Insert node
Node* insert(Node* node, int key) {
    if (node == NULL) return createNode(key);

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

    return node;
}

Search Operation

Search for a key in the BST with the following steps:

1. Start from the root node, compare the target key with the current node's key.
2. If the target key equals the current node's key, the search is successful.
3. If the target key is less than the current node's key, move to the left subtree; otherwise, move to the right subtree.
4. Repeat the above steps until the target key is found or an empty node is encountered (search fails).

The code implementation for the search operation is as follows:

// Search node
Node* search(Node* root, int key) {
    if (root == NULL || root->key == key) {
        return root;
    }

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

Deletion Operation

Deleting a node from a BST involves three cases:

1. Leaf node: Simply delete the node.
2. Node with only one child: Replace the node with its only child.
3. Node with two children: Find the node's successor (the minimum node in the right subtree), replace the node with the successor, then delete the successor.

The code implementation for the deletion operation is as follows:

// Find the minimum value node
Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left != NULL) {
        current = current->left;
    }
    return current;
}

// Delete node
Node* deleteNode(Node* root, int key) {
    if (root == NULL) return root;

    if (key < root->key) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->key) {
        root->right = deleteNode(root->right, key);
    } else {
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }

        Node* temp = minValueNode(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }

    return root;
}

3. Creating a BST

Creating a BST involves sequentially inserting multiple keys into the BST.

4. Performance Analysis

The performance of a BST mainly depends on its height:

• Best case (fully balanced): height is $O(\log n)$.
• Worst case (degenerates to a linked list): height is $O(n)$.

5. Time and Space Complexity Analysis

Insertion Operation

• Time complexity: On average, the time complexity of insertion is $O(\log n)$, because the tree height averages $\log n$. In the worst case (tree degenerates to a linked list), the time complexity is $O(n)$.
• Space complexity: The main space used by insertion is the stack space for recursive calls, which is $O(n)$ in the worst case and $O(\log n)$ on average.

Search Operation

• Time complexity: On average, the time complexity of search is $O(\log n)$. In the worst case (tree degenerates to a linked list), the time complexity is $O(n)$.
• Space complexity: The main space used by search is the stack space for recursive calls, which is $O(n)$ in the worst case and $O(\log n)$ on average.

Deletion Operation

• Time complexity: On average, the time complexity of deletion is $O(\log n)$. In the worst case (tree degenerates to a linked list), the time complexity is $O(n)$.
• Space complexity: The main space used by deletion is the stack space for recursive calls, which is $O(n)$ in the worst case and $O(\log n)$ on average.

6. Example Code (C Language Implementation)

The following is a C language implementation of a BST, including insertion, search, and deletion operations:

#include <stdio.h>
#include <stdlib.h>

// Define node structure
typedef struct Node {
    int key;
    struct Node* left;
    struct Node* right;
} Node;

// Create new node
Node* createNode(int key) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Insert node
Node* insert(Node* node, int key) {
    if (node == NULL) return createNode(key);

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

    return node;
}

// Search node
Node* search(Node* root, int key) {
    if (root == NULL || root->key == key) {
        return root;
    }

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

// Find the minimum value node
Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left != NULL) {
        current = current->left;
    }
    return current;
}

// Delete node
Node* deleteNode(Node* root, int key) {
    if (root == NULL) return root;

    if (key < root->key) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->key) {
        root->right = deleteNode(root->right, key);
    } else {
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }

        Node* temp = minValueNode(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }

    return root;
}

// In-order traversal
void inorderTraversal(Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->key);
        inorderTraversal(root->right);
    }
}

int main() {
    Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    printf("Inorder traversal: ");
    inorderTraversal(root);

    printf("\nDelete 20\n");
    root = deleteNode(root, 20);
    printf("Inorder traversal: ");
    inorderTraversal(root);

    printf("\nDelete 30\n");
    root = deleteNode(root, 30);
    printf("Inorder traversal: ");
    inorderTraversal(root);

    printf("\nDelete 50\n");
    root = deleteNode(root, 50);
    printf("Inorder traversal: ");
    inorderTraversal(root);

    Node* foundNode = search(root, 60);
    if (foundNode != NULL) {
        printf("\nFound key 60\n");
    } else {
        printf("\nKey 60 not found\n");
    }

    return 0;
}

7. References

1. Introduction to Algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
2. Data Structures and Algorithm Analysis in C