详解二叉搜索树

原文地址：

https://lufficc.com/blog/binary-search-tree

在计算机科学中，二叉搜索树（Binary Search Tree）（有时称为有序或排序的二叉树）是一种能存储特定数据类型的容器。二叉搜索树允许快速查找、添加或者删除某一个节点，并且它是动态的集合。
二叉搜索树按照关键字顺序地保存节点，因此查找和其他操作可以使用二叉搜索原理：当在树（或者寻找插入新节点的地方）中查找节点时，它从根节点遍历到叶节点，与每个节点的关键字进行比较，然后基于比较结果，决定继续在左子树或者右子树中进行搜索。平均而言，每次比较将跳过树的大约一半的元素，这使得每次查找，插入或删除一个节点所花费的时间与树的节点个数的对数成（树的高度）正比，比线性表的性能要好很多。

定义

二叉搜索树是以一棵二叉树来组织，每个节点就是一个对象，包括key、卫星数据，除此之外还包括一些为了维持树结构所需要的信息：left、right、parent，分别指向左孩子、右孩子、父节点。其中如果孩子节点或者父节点不存在时，用NIL表示。根节点是树中唯一一个父节点为NIL的节点。

二叉搜索树具有以下性质：

1. 如果节点的左子树不空，则左子树上所有结点的值均小于等于它的根结点的值；
2. 如果节点的右子树不空，则右子树上所有结点的值均大于等于它的根结点的值；
3. 任意节点的左、右子树也分别为二叉查找树；

比如在上图中根节点的关键字为6，左子树有关键字2、4和5，均不大于6；右子树有关键字7和8，均不小于6。这个性质对树中的每个节点都成立，也就是说，二叉搜索树的定义是递归的。

在讨论二叉搜索树的操作之前，先看看二叉搜索树的遍历。二叉搜索树可以使用先序遍历（preorder tree walk）、中序遍历（inorder tree walk）和后序遍历（postorder tree walk）。这样命名的依据是根据输出关键字相对于左右子树的位置。以中序遍历为例，伪代码如下：

INORDER-TREE-WALK(x)
if x != nil  // 如果节点不为空
        INORDER-TREE-WALK(x.left)  // 首先递归地遍历左孩子，直到左孩子为空
        print x.key     // 输出当前节点（显然第一次运行到这里时，它是最小值，因为它是整棵树的最左节点） 
        INORDER-TREE-WALK(x.right)  // 递归地遍历右孩子

对于上图中的二叉搜索树，动态过程如下，这样输出结果为：2，4，5，6，7，8，即按照从小到大的顺序排列。因为输出时一直遍历左孩子，知道遇到第一个左孩子为空的节点，将它输出，然后出栈返回继续输出。

查询

二叉搜索树还应该可以完成MINIMUM，MAXIMUM，SUCCESSOR和PREDECESSOR操作，即求最小值，最大值，后继和前驱，并且这些操作都可以在o(lgn)的时间内完成。

查找指定关键字

TREE-SEARCH操作在二叉树中查找一个具有指定的关键字的节点，输入树的根节点指针和关键字k，如果存在，返回节点指针，否则，返回nil。

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)

比如查找关键字为5的节点，首先从根节点6开始，与5进行比较，因为5小于6，因此在节点6的左子树继续搜索。到达节点4时因为5大于4，所以在4节点的右子树搜索，这样就顺利找到了节点5，此时函数将返回指向节点5的指针。如果找不到目标节点，TREE-SEARCH函数将返回nil。整个搜索过程如下：

最小/最大关键字

通过从树根开始，沿着left孩子向下搜索，直到遇到nil，那么根据二叉搜索树的性质，如果节点x没有左子树，而x的右子树的关键字肯定都大于x.key，因此此时当前节点一定是整个树中的最小值。

TREE-MINIMUM(x)
while x.left != nil  // 沿着左子树一直深入搜索下去，直到遇到左子树为空的节点，此时当前节点为最小值
        x = x.left
return x

同理，最大关键字的伪代码如下：

TREE-MAXIMUM(x)
while x.right != nil  // 沿着右子树一直深入搜索下去，直到遇到右子树为空的节点，此时当前节点为最大值
        x = x.right
return x

求取最大、最小关键字的时间复杂度仅为o(lgn)，即与树的高度成正比，因为查找过程自上而下形成一条线，线的最大长度为数的高度，如求取最小值的过程：

前驱/后继

给定二叉搜索树的一个节点，有事需要按照中序遍历的次序查找它的后继，如果所有的关键字互不相同，则一个节点x的后继一定是大于x.key的最小关键字。

TREE-SUCCESSOR(x)
if x.right != nil   //case 1:如果右子树不为空，则后继一定是右子树的最小值，即大于x的最小值（右子树的值都大于x节点）
return TREE-MINIMUM(x.right)
    y = x.p    // case 2:右子树为空时
while y != nil and x == y.right
        x = y   // 变量x代表节点原始x的祖先，如果找到x，它是父节点的左孩子，则循环终止
        y = y.p   // y 代表节点x的父节点，如果x是y的左孩子，循环终止，并且返回y
return y

1.对于第一种情况比较简单，如果x右子树不为空，那它的后继就是右子树的最左节点，对应伪代码case 1，例如下图寻找68的后继，即寻找68的右子树的最小节点72，同时它也是右子树的最左节点。

2.第二种情况是x的右子树为空，注意x的后继始终是大于x的最小值（或者不存在），所以当x的右子树不存在时大于x的最小值在哪儿呢？我们只需要简单的从x开始沿树而上，找到第一个这样一个节点：它的父节点为空（即根节点）或者它的左孩子是x节点的祖先节点（不一定是直接祖先）。例如下图中为了寻找17的后继，沿着树上升，首先以此遇到了节点13，11，它们均不符合条件，因为它们不是父节点的左孩子。当遇到节点10时，此时x指向节点10，y指向节点19，并且节点10是节点19的左孩子，符合条件，所以返回节点y，它是节点x的后继。

再举一个例子，下图为了找15的后继，仍然沿着树上升，直到遇到节点10（此时伪代码中的变量x指向节点10）：它是15的祖先，而且是左孩子。所以此时返回节点10的父节点19，即节点15的后继。

一个二叉搜索树中除了最大节点外，都有后继。对于前驱节点，和后继节点原理一样，这里不再赘述。

插入

插入操作会引起二叉搜索树集合的动态变化，因此需要一定的修改来维持二叉搜索树。由于二叉搜索树的性质，即左孩子小于等于父节点，右孩子大于等于父节点，因此插入操作相对简单。

将一个节点插入到二叉搜索树中，需要调用TREE-INSERT，该过程以节点z作为输入，其中z.left = nil, z.right = nil, z.key = 将要插入数据的关键字：

TREE-INSERT(T, z)
    y = nil
    x = T.root
while x != nil //循环结束后，x一定为空，此时x即为节点z要插入的地方
        y = x    //在这里给y赋值，保证循环结束后y始终是x的父节点
if z.key < x.key
            x = x.left
else
            x = x.right
        z.p = y  // y始终是x的父节点，为了插入z，需要让z的父节点指向x的父节点，即指向y
if y == nil  // 如果y为空，说明插入时是一棵空的树，需要将树根指向z
            T.root = z
        elseif z.key < y.key   // 判断节点z是y的左孩子还是右孩子
            y.left = z
else
            y.right = z

上述伪代码从树根开始，指针x记录了一条向下的简单路径，通过while循环比较z.key和x.key的大小，使指针x和指针y向下移动，循环结束时则找到一个空的x并作为一个槽，将节点z放到这里（插入），同时保持节点y为节点x的父节点，这样可以很方便的决定插入之后将z作为它的左孩子还是右孩子。举一个例子：

上图为了在树中插入节点46，首先x指向根节点，节点46与根节点68（x节点）比较，小于68，因此指针x指向根节点（x节点）的左孩子62，然后一直下移。注意当x指向45的时候，节点46大于45，因此将x指向节点45的右孩子，此时x为nil了，循环结束，也就找到了节点46的位置：节点45的右孩子。然后进行一些操作将节点46插入到树中即可。

删除

从二叉搜索树中删除一个节点z稍微有点棘手，但总的来说可以分为三种情况：

1. 如果z没有孩子节点，那么简单的将它删除，并修改它的父节点，用nil作为孩子节点代替z即可。
2. 如果z只有一个孩子，那么将这个孩子提升到z的位置，并修改它的父节点，用z的孩子代替z即可。
3. 如果z有两个孩子，那么用z的后继y（此时z的后继y一定在z的右子树中，因为z的右孩子不为空）来占据z的位置，此时z的原来的右子树部分称为y的新的右子树，并且z的左子树称为y的新的左子树。这种情况稍微麻烦，因为还与y是否为z的右孩子相关。

第一种情况：节点z没有孩子

这种情况比较简单，我们直接删除节点z即可，并不会影响到二叉搜索树的性质：

用动图来表示就是：

第二种情况：节点z只有一个孩子

这种情况也比较简单，直接用节点z的孩子代替节点z即可。其实第一种情况和第二种情况可以归为一个：节点z的孩子个数小于2个，直接用节点z的孩子代替节点z即可，只是节点z没有孩子时是用的nil代替节点z，这里为了更加清楚地说明分了三种情况。

例如如下图，当节点42只有左孩子时，直接将42的父节点6的右孩子指向节点29，将节点29的父节点设置为节点6即可：

或者只有右孩子时也是如此，直接将94的左孩子指向78，78的父节点指向94即可：

第三种情况：节点z有两个孩子

这种情况稍微复杂一点，因为此时我们需要找到节点z的后继y，而后继节点y又分为y是节点z的直接右孩子或者不是。

1. z的后继y是 z的右孩子
   此时可以直接用后继y代替z，而且y的左孩子此时一定为空（因为后继的左孩子一定为空），再用z的左孩子代替y的原来为空的左孩子即可。
   
   用动图表示删除节点67就是：
   

2. z的后继y不是 z的右孩子
   在这种情况下我们先用y的右孩子x代替y，然后再用y代替z:

用动图表示删除节点50就是用74代替73，即将73的父节点82的右孩子指向74,74的父节点设置为82，然后再用73代替50，即将50左孩子31设置为73的左孩子，50的右孩子82设置为73的右孩子：

为了实现删除过程的伪代码，我们需要定义一个子过程TRANSPLANT，它是用为了用以v为根的子树替换以u为根的子树，让u的双亲节点变为v的双亲节点，即让v称为u的双亲节点的孩子：

TRANSPLANT(T, u, v)
if u.p == nil   // 当u位树的根节点时，直接将树的根节点指向v
        T.root = v
    elseif u == u.p.left   // 如果u是左孩子，则u的父节点的左孩子指向v
        u.p.left = v
else    // 如果u是右孩子，则u的父节点的右孩子指向v
        u.p.right = v
if v != nil   
        v.p = u.p    // 将v的父节点设为u的父节点

然后实现具体的删除过程：

TREE-DELETE(T, z)
if z.left == nil  // 如果左孩子为空，则直接用右孩子代替z即可，而不管右孩子是否为空（右孩子为空时对应情况一否则对应情况二）
        TRANSPLANT(T, z, z.right)
    elseif z.right == nil  // 右孩子为空，直接用做孩子代替z
        TRANSPLANT(T, z, z.left)
else y = TREE-MINIMUM(z.right)  // 左右孩子均不为空，找到z的后继y，即z的右子树的最小值，对应第三种情况
if y.p != z   // 如果z的后继y不是z的右孩子，对应第三种情况的2
            TRANSPLANT(T, y, y.right)  // 用y的右孩子代替y
            y.right = z.right    // 将y的右孩子指向z的右孩子
            y.right.p = y     // 将y的右孩子(原来的z的右孩子)的父节点设为y
        TRANSPLANT(T, z, y)  // 用y代替z
        y.left = z.left
        y.left.p = p

因此总的来说，删除操作可以分为两大类：

1. z的孩子总数小于2时，直接用z的孩子代替z即完成了对z的删除。
2. z有两个孩子时：
   2.1. z的后继y是z的右孩子：直接用y代替z即可（别忘了将z的左孩子的父节点设置为y）。
   2.2. z的后继y不是z的右孩子：先用y的右孩子x代替y，再用y代替z。

总结

因为二叉搜索树的性质，即可以在每个比较之后将数据规模变为原来的一半，因此平均情况下每一个操作都可以在o(lgn)的时间内完成，即花费时间与树的高度成正比。但在最坏的情况下，二叉搜索树就退化为一个链表，此时的时间复杂度退化到了o(n)。但很多改进版的二叉查找树可以使树高为o(lgn)，如SBT，AVL树，红黑树等。