第12 章 二叉搜索树

　　搜索树结构支持许多动态集合操作，因此，使用一棵搜索树既可以作为一个字典又可以作为一个优先队列。
　　二叉搜索树的基本操作所花费的时间与这棵树的高度成正比。对于 n 个节点的一个完全二叉树来说，这些操作的最坏运行时间为θ（lgn）。然而，如果这棵树是一条 n 个节点组成的线性链，那么同样的操作就要花费θ（n）的最坏运行时间。
　　

12.1 什么是二叉搜索树

　　一颗二叉搜索树是以一颗二叉树来组织的，这样一棵树可以用一个链表数据结构来表示，其中每个节点就是一个对象。除了 key 和卫星数据之外，每个节点还包含属性left 、right、和p。如果某个孩子结点和父结点不存在，则相应属性的值为NIL。跟节点是树中唯一父指针为NIL的结点。
　　二叉搜索树：对任何节点 x，其左子树（并不是左孩子）中的关键字最大不超过x.key，其右子树中的关键字最小不低于x.key。不同的二叉树可以代表同一组值的集合。
　　二叉搜索树按序输出树中的所有关键字的递归算法：中序遍历算法。这样命名的原因是输出的子树根的关键字位于其左子树的关键字值和右子树的关键字值之间。（类似地，先序遍历中输出的根的关键字在其左右子树的关键字值之前，而后序遍历输出的根的关键字在其左右子树的关键字值之后）。
INORDER-TREE-WALK（T.root）

if x != NIL
    INORDER-TREE-WALK(x.left)
    print x.key
    INORDER-TREE-WALK(x.right)

定理 12.1 如果 x 是一颗有 n 个结点子树的根，那么调用INORDER-TREE-WALK（x）需要θ（n）时间

12.2 查询二叉搜索数

查找
　　在一颗二叉搜索树中查找一个具有给定关键字的结点。输入一个指向树根的指针和一个关键字 k。存在，返回一个指向关键字为 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)

TREE-SEACH的运行时间为O（h），其中 h 为这颗数的高度。
同样可以采用while循环来展开递归，用一种迭代方式重写这个过程。对于大多数计算机，迭代版本的效率要高的多。
ITERATIVE-TREE-SEARCH(x, k)

while x!= NIL and k != x.key
    if k < x.key
        x = x.left
    else x = x.right
return x

最大关键字和最小关键字元素
TREE-MINIMUM(x)

while x.left != NIL
    x = x.left
return x

TREE-MAXIMUM(x)

while x.right != NIL
    x = x.right
return x

这两个过程在一颗高度为 h 的树上均能在O(h)时间内完成。
后继和前驱
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

TREE-SUCCESSOR的运行时间为O(h)。
定理12.2 在一颗高度为 h 的二叉树搜索树上，动态集合上的操作SEARCH、MINIMUN、MAXIMUN、SUCCESSOR和PREDECESSOR可以在O(h)时间内完成

12. 3 插入和删除

插入一个新结点带来的树修改要相对简单些，而删除的处理有些复杂。
插入
将一个新值 v插入到一个二叉搜索数T中，调用TREE-INSERT，该过程以结点z作为输入，其中z.key = v，z.left = NIL，z.right = NIL。
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 = y
if y == NIL
    T.root = z
else if z.key < y.key
    y.left = z
else y.right = z

TREE-INSERT从树根开始，指针 x 记录一条向下的简单路径，并查找替换的输入项 z 的NIL。该过程保持遍历指针 y 作为 x 的双亲。初始化后，第 3~7 行的while循环使得这两个指针沿树向下移动，向左或向右取决于z.key和x.key的比较，知道x变为NIL。这个NIL占据的位置就是输入项 z要放置的地方。需要遍历指针 y，因为找到 NIL时要知道z属于那个节点。第 8~13 行设置相应的指针，使得 z 插入其中。
与其他搜索数的原始操作一样，过程TREE-INSERT在一颗高度为h的树上的运行时间为O(h)。
删除
　　从一颗二叉搜索树 T 中删除一个结点 z 的整个策略分为三种基本情况，但只有一种情况棘手：
　　

• 如果 z 没有孩子结点，那么只是简单的将它删除，并修改它的父节点，用NIL作为孩子来替换 z。
• 如果z只有一个孩子，那么将这个孩子提升到树 中 z 的位置上，并修改 z 的父结点，用 z 的孩子来替换 z。

• 如果 z 有两个孩子，那么找 z 的后继 y（一定在 z 的右子树中），并让 y 占据树中 z 的位置。 z的原来右子树部分成为 y 的新的右子树，并且 z 的左子树成为 y 的新左子树。

  　　从一颗二叉搜索树 T 中删除一个给定的结点 z，这个过程取指向 T 和 z的指针作为输入参数。它与前面概括出的三种情况有些不同。
  　　

• 如果 z 没有左孩子，那么用其右孩子来替换 z，这个右孩子可以是 NIL，也可以不是。当 z 的右孩子是 NIL时，此时这种情况归为 z 没有孩子结点的情形。当 z 的右孩子非 NIL时，这种情况就是 z 仅有一个孩子节点的情形，该孩子就是其右孩子。
• 如果 z 仅有一个孩子且为其左孩子，那么用其左孩子来替换 z。
• 否则， z既有一个左孩子又有一个右孩子，要查找 z 的后继 y，这个后继位与 z 的右子树中并且没有左孩子。需要将 y 移除原来的位置进行拼接，并替换树中的z。
• 如果 y 是 z 的右孩子，那么用 y 替换 z ，并仅留下 y 的右孩子。
• 否则，y 位于 z 的右子树中当并不是 z 的右孩子。在这种情况下，先用 y 的右孩子替换 y，然后再用 y 替换 z。
  为了在二叉搜索树中，定义一个子过程TRANSPLANT，它是用另一颗子树替换一颗子树并成为其双亲的孩子结点。但TRANSPLANT用一颗以 v 为根的子树替换一颗以 u 为根的子树时，结点 u 的双亲就变为 v 的双亲，并且最后 v成为 u 的双亲的相应孩子。
  TRANSPLANT（T, u, v)

if u.p == NIL
    T.root = v
else if u == u.p. left
    u.p.left = v
else u.p.right = v
if v != NIL
    v.p = u.p

下面是从二叉搜索树中删除结点 z 的删除过程：
TREE-DELETE(T, z）

if z.left == NIL
    TRANSPLANT(T, z, z.right)
else if 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

TREE-DELETE的花费时间为O(h)。
定理12.3 在一颗高度为h 的二叉搜索树上，实现动态集合操作INSERT和DELETE的运行时间为O(h)。

12.4 随机构建二叉搜索树

　　二叉搜索树的高度ｈ>= lgn.我们定义 n 个关键字的一颗随机构建二叉搜索树为按随机次序插入这些关键字到一颗初始为空树中而生成的数。
定理 12.4 一颗有 n 个不同关键字的随机构建二叉搜索树的期望高度为O(lgn)。