Binary Search Trees (BST) are specialized tree structures that facilitate efficient data retrieval, insertion, and dleetion. They serve as the foundation for complex associative containers like sets and maps.

Core Properties of Binary Search Trees

A BST is defined by a specific ordering of its nodes. For any given node:

1. The values in its left subtree are strictly smaller than the node's value.
2. The values in its right subtree are strictly larger than the node's value.
3. Both left and right subtrees must themselves be binary search trees.
4. An in-order traversal of a BST yields a sorted sequence of elements.

Fundamental Models: K and KV

The K Model (Key Only)

In the K model, the structure stores only the key. This is primarily used to check for the existence of an element. A common example is a spell checker where a dictionary is stored as a BST of keys; if a word is found in the tree, it is spelled correctly.

The KV Model (Key-Value Pair)

In the KV model, each key is associated with a specific value. This is used for dictionary-like lookups. Examples include:

• English-Chinese Dictionary: Key is the English word, Value is the Chinese translation.
• Word Frequency Counter: Key is the word, Value is the integer count of its occurrences.

Implementation of the K Model

Node and Class Structure

template<typename K>
struct BinaryNode {
    K data;
    BinaryNode<K>* left;
    BinaryNode<K>* right;

    BinaryNode(const K& val)
        : data(val), left(nullptr), right(nullptr) {}
};

template<typename K>
class SearchTree {
    using Node = BinaryNode<K>;
public:
    SearchTree() : root(nullptr) {}
private:
    Node* root;
};

Search Operation

The search algorithm compares the target value with the current node. If it is smaller, it moves to the left; if larger, it moves to the right.

bool contains(const K& target) {
    Node* current = root;
    while (current) {
        if (target < current->data)
            current = current->left;
        else if (target > current->data)
            current = current->right;
        else
            return true;
    }
    return false;
}

Insertion Logic

To maintain the BST property, a new node is always inserted as a leaf. The tree is traversed until a null position is found.

bool insert(const K& val) {
    if (root == nullptr) {
        root = new Node(val);
        return true;
    }
    Node* parent = nullptr;
    Node* current = root;
    while (current) {
        if (val < current->data) {
            parent = current;
            current = current->left;
        } else if (val > current->data) {
            parent = current;
            current = current->right;
        } else {
            return false;
        }
    }
    Node* newNode = new Node(val);
    if (val < parent->data)
        parent->left = newNode;
    else
        parent->right = newNode;
    return true;
}

Deletion Strategy

Removing a node is more complex as it requires restructuring to preserve the BST properties. There are three primary scenarios:

1. Leaf Node: Simply remove the node.
2. One Child: Link the node's parent directly to its child.
3. Two Children: Replace the node's value with the minimum value from its right subtree (the in-order successor) or the maximum from its left subtree, then delete that replacement node.

bool remove(const K& val) {
    Node* parent = nullptr;
    Node* current = root;
    while (current) {
        if (val < current->data) {
            parent = current;
            current = current->left;
        } else if (val > current->data) {
            parent = current;
            current = current->right;
        } else {
            if (current->left == nullptr) {
                if (current == root)
                    root = current->right;
                else if (parent->left == current)
                    parent->left = current->right;
                else
                    parent->right = current->right;
                delete current;
            } else if (current->right == nullptr) {
                if (current == root)
                    root = current->left;
                else if (parent->left == current)
                    parent->left = current->left;
                else
                    parent->right = current->left;
                delete current;
            } else {
                Node* successorParent = current;
                Node* successor = current->right;
                while (successor->left) {
                    successorParent = successor;
                    successor = successor->left;
                }
                current->data = successor->data;
                if (successorParent->left == successor)
                    successorParent->left = successor->right;
                else
                    successorParent->right = successor->right;
                delete successor;
            }
            return true;
        }
    }
    return false;
}

Key-Value Model Implementation

The KV model extends the node to include a value field. The logic for navigation remains based on the key.

template<typename K, typename V>
struct KVNode {
    K key;
    V value;
    KVNode<K, V>* left;
    KVNode<K, V>* right;

    KVNode(const K& k, const V& v)
        : key(k), value(v), left(nullptr), right(nullptr) {}
};

template<typename K, typename V>
class KVTree {
    using Node = KVNode<K, V>;
public:
    Node* find(const K& key) {
        Node* curr = root;
        while (curr) {
            if (key < curr->key) curr = curr->left;
            else if (key > curr->key) curr = curr->right;
            else return curr;
        }
        return nullptr;
    }

    bool insert(const K& k, const V& v) {
        if (!root) {
            root = new Node(k, v);
            return true;
        }
        Node* parent = nullptr;
        Node* curr = root;
        while (curr) {
            parent = curr;
            if (k < curr->key) curr = curr->left;
            else if (k > curr->key) curr = curr->right;
            else return false;
        }
        if (k < parent->key) parent->left = new Node(k, v);
        else parent->right = new Node(k, v);
        return true;
    }
private:
    Node* root = nullptr;
};

Complexity and Performance Analysis

The performance of BST operations depends on the height of the tree ($h$).

• Best Case: When the tree is balanced (complete binary tree), $h = \log_2 N$. Operations like search, insert, and delete take $O(\log N)$.
• Worst Case: When keys are inserted in sorted order, the tree degenerates into a linked list. In this scenario, $h = N$, and performance drops to $O(N)$.

To ensure logarithmic performance regardless of insertion order, self-balancing trees such as AVL trees or Red-Black tree are typically utilized.