Binary Search Trees: Search, Insertion, Successor & Hibbard Deletion Asymmetry

The Global BST Invariant, Successor Geometry & Hibbard's Three Deletion Cases

Notice a critical distinction between the BST property and the Heap property: the BST property is a global subtree invariant, not merely a local parent-child condition. A node $y$ inside $x$'s left-right grandchild slot must satisfy $x.\text{left}.\text{key} < y.\text{key} < x.\text{key}$; merely checking parent vs. child locally fails to validate a BST.

Finding the In-Order Successor of a node $x$ splits into two structural cases in $O(h)$ time:

1. $x.\text{right} \ne \text{null}$: The successor is $\text{minimum}(x.\text{right})$, found by walking left pointers from $x.\text{right}$ until left == null.Crucially, this successor node $y$ is guaranteed to have $y.\text{left} == \text{null}$.
2. $x.\text{right} == \text{null}$: The successor is the lowest ancestor of $x$ whose left subtree contains $x$ (found by walking up parent pointers while coming from a right child, or tracking the last left-turn ancestor from the root).

Hibbard Deletion (treeDelete(T, z)): To delete node $z$, CLRS uses a helper transplant(T, u, v) that replaces subtree $u$ with subtree $v$ in $O(1)$ pointer updates:

• Case 1 ($z.\text{left} == \text{null}$): Replace $z$ directly with $z.\text{right}$ (covers both 0-child leaf and right-only child).
• Case 2 ($z.\text{right} == \text{null}$): Replace $z$ directly with $z.\text{left}$.
• Case 3 ($z$ has two children): Find $z$'s successor $y = \text{minimum}(z.\text{right})$. Because $y$ is the minimum of $z.\text{right}$, $y$ has no left child ($y.\text{left} == \text{null}$). If $y$ is not $z$'s immediate right child ($y.\text{parent} \ne z$), first transplant $y$ with $y.\text{right}$ and attach $z.\text{right}$ to $y.\text{right}$. Finally, transplant $z$ with $y$ and attach $z.\text{left}$ to $y.\text{left}$.

Visualizing Case 3 Hibbard Transplant ($y.\text{parent} \ne z$)

Implementation: Pointer-Stable CLRS Transplant & Symmetric Hibbard Delete

// C++20: Pointer-Stable CLRS BST Transplant & Deletion (Zero Iterator Invalidation)
struct BSTNode {
    int key;
    BSTNode *left = nullptr, *right = nullptr, *parent = nullptr;
};

void transplant(BSTNode*& root, BSTNode* u, BSTNode* v) {
    if (u->parent == nullptr) {
        root = v;
    } else if (u == u->parent->left) {
        u->parent->left = v;
    } else {
        u->parent->right = v;
    }
    if (v != nullptr) {
        v->parent = u->parent;
    }
}

BSTNode* treeMinimum(BSTNode* x) {
    while (x != nullptr && x->left != nullptr) x = x->left;
    return x;
}

void treeDelete(BSTNode*& root, BSTNode* z) {
    if (z->left == nullptr) {
        transplant(root, z, z->right);
    } else if (z->right == nullptr) {
        transplant(root, z, z->left);
    } else {
        BSTNode* y = treeMinimum(z->right); // Guaranteed: y->left == nullptr
        if (y->parent != z) {
            transplant(root, y, y->right);
            y->right = z->right;
            y->right->parent = y;
        }
        transplant(root, z, y);
        y->left = z->left;
        y->left->parent = y;
    }
    delete z;
}