chap12 二叉搜索树

二叉搜索树 算法导论

内容

性质

1. 对任一结点x，左孩子l和右孩子r满足$l.key <= x.key <= r.key$
2. 在一棵高为h二叉搜索树上，动态集合上的操作search minimum maximum successor predecessor 可以在$O(h)$时间内完成
3. 中序遍历
   x是一棵有n个结点的二叉树的根
   Inorder-Tree-Walk(x)——$\Theta(n)$

--

if x != NIL
    Inorder-Tree-Walk(x.left)
    print x.key
    Inorder-Tree-Walk(x.right)

基本操作

search

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

前驱和后继

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-Prodecessor(x)

if x.left != NIL
    return Tree-Minimum(x.left)
y = x.p
while y != NIL and x == y.left
    x = y
    y = y.p
return y

插入

注意，无论插入的是什么数，它必然被插入到最低端或者只有一个孩子的结点上
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

删除

1. 删除操作分为4中情况
   前三者情况都属于z和其替代者的孩子数为2，因而直接替换即可，情况4孩子数为3，因而设计到孩子的重新分配问题，要复杂一点。另外，3，4设计到孩子的重新连接问题
   
   • z没有左孩子-----------------------------------------------1
   • z有左孩子
     　　　　z没有右孩子------------------------------------------2
     　　　　z有右孩子
     　　　　　　　　后继y是z右孩子-------------------------------3
     　　　　　　　　后继y不是z右孩子-----------------------------4

Transplant(T,u,v)
该过程会使u的父亲变成v的父亲，v变成原来u父亲的孩子，但不涉及到这两个结点孩子的操作，因而在主程序中，还需要进行孩子的拼接

if u.p == NIL
    T.root = v
esle if u == u.p.left
    u.p.left = v
else u.p.right = v
if v != NIL #哨兵不涉及父亲指标

    v.p = u.p

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     #该if分支，将y移到z的右孩子位置，执行完后，情况4变成了情况3
        Tranplant(T,y,y.right)
        y.right = z.right
        y.right.p = y
    Transplant(T,z,y)
    y.left = z.left
    y.left.p = y

随机构建二叉搜索树

定理：一棵有n个关键字的随机构建的二叉搜索树的期望高度是$O(\lg n)$
所谓随机是指，构建搜索树的时候，关键字是以随机的次序插入到二叉树中。次序对二叉树的影响体现在

注意，无论插入的是什么数，它必然被插入到最低端或者只有一个孩子的结点上

代码实现

java