本文简单介绍二叉搜索树，为下一篇文章讲红黑树作铺垫。

二叉搜索树

二叉搜索树(Binary Search Tree, BST)是一棵二叉树，每个结点都记录着左子left、右子right、父结点p、关键字key。BST里的关键字总是满足二叉搜索树性质：对于每个结点，其关键字都大于或等于它的任意左子，小于或等于它的任意右子。简单来说，就是“左小右大”。下面比较结点大小时，指的就是比较结点关键字的大小。

搜索

BST很便于搜索。例如要搜索k，那么从根结点开始，如果k比当前结点大，就往右下走；如果更小，就往左下走；如果相等，就搜索成功；如果搜到叶子结点都没找到，就搜索失败。

TREE-SEARCH(x,k)
    if x == NIL or k == x.key
        return x
    if k < x.key
        return TREE-SEARCH(x.left, k)
    else
        return TREE-SEARCH(x.right, k)

最大值与最小值

很显然，一直往左下走就是最小值，一直往右下走就是最大值。

前驱与后继

某结点的前驱(predecessor)是小于它却最接近它的结点，后继(successor)是大于它却最接近它的结点。

后继在哪里找呢？在一棵二叉树中，对于任一结点M，另一个结点与它的关系可能是：

  1. 是M的祖先
  2. 是M的后代
  3. 与M有另一个最低的共同祖先P

所以，M的后继N一定在这三类位置当中。

  1. 如果N是M的祖先，那么M必然是N的左子树的最大值，即M = min(T, N.left)。这样的N最多只存在一个，可记为N1。

  2. 如果N是M的后代，那么N必然是M的右子树的最小值，即N = max(T, M.right)。这样的N最多只存在一个，可记为N2。

  3. 如果M与N有另一个最低的共同祖先P，那么P的值一定在M与N之间，N不可能是M的后继。

当N1和N2都存在的情况下，因为M在N1的左子树上，又是N2的祖先，故N2 < N1。

综上，M的后继是它右子树的最小值（若存在），否则是使M成为它左子树上最大值的那个结点（若存在），否则没有后继（是整棵树的最大值）。

前驱的情况与后继对应。

TREE-SUCCESSOR(x)
    if x.right != NIL
        return TREE-MINIMUM(x.right)
    y = x.p
    while y != NIL and x == y.right
        x = y
        y = y.p
    return y

插入和删除

插入实际上类似于搜索，只不过搜索的是一个不存在的key值，然后当我们到达一个空结点时，把它变成具有新key值的结点就行了。

TREE-INSERT(T,z)
    y = NIL
    x = T.root
    while x != NIL
        y = x
        if(z.key < x.key) x = x.left
        else x = x.right
    z.p = x
    if y == NIL // tree T was empty
        T.root = z
    else if z.key < y.key
        y.left = z
    else
        y.right = z

删除稍微要麻烦一些。

首先我们要认识到，删除一个仅有0或1个儿子的结点（下称“计生”结点）很容易，只要直接删除，或者把它的儿子“接上来”就可以了。下面是用子树v替换子树u的代码，它只做了简单的拆装，维持u以外的原树的结构：

TRANSPLANT(T,u,v)
    if u.p == NIL
        T.root = v
    elseif u == u.p.left
        u.p.left = v
    else u.p.right = v
    if v != NIL
        v.p = u.p

当我们要删除有2个儿子的结点Z时，可以找另一个结点代替它。代替者必须满足：1. 大于左子树的最大值（即Z的前驱）；2. 小于右子树的最小值（即Z的后继）。这样看来，似乎我们只能用Z的前驱或后继代替Z了，而恰好它们俩都是“计生”结点（前驱无右子，后继无左子）。下面说用Z的后继Y代替Z的方法。

  • 若Y恰好是Z的右子，则可以直接用Y代替Z的位置，Y的左子取代Z的左子，右子保持不变。
  • 若Y不是Z的右子，则可先用Y代替Z的位置，Y的左右子取代Z的左右子；与此同时，Y原来的右子需挂靠在Y的父结点上，相当于将“删除有2个儿子的Z”转化为“删除仅有0或1个儿子的Y”。
TREE-DELETE(T,z)
    if z.left == NIL
        TRANSPLANT(T,z,z.right)
    elseif z.right == NIL
        TRANSPLANT(T,z,z.left)
    else y = TREE-MINIMUM(z.right)
         if y.p != z
             TRANSPLANT(T,y,y.right)
             y.right = z.right
             y.right.p = y
         TRANSPLANT(T,z,y)
         y.left = z.left
         y.left.p = y

模板

可以用C++写个简单的模板。

struct BSTNode {
    int key;
    BSTNode* left;
    BSTNode* right;
    BSTNode* p;
};

struct BST {
    BSTNode *root;
    
    BSTNode* query(int val);
    BSTNode* mininum(BSTNode* node);
    BSTNode* maximum(BSTNode* node);
    BSTNode* insert(int val); // return the inserted node
    BSTNode* del(BSTNode *node); // return NULL if deletion fails, or return a pointer pointing to the original place in the tree where node was deleted
}