[关闭]
@zqbinggong 2018-03-11T13:57:30.000000Z 字数 1644 阅读 361

chap12 二叉搜索树

二叉搜索树 算法导论

内容


性质

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

--

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

基本操作

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个关键字的随机构建的二叉搜索树的期望高度是
所谓随机是指,构建搜索树的时候,关键字是以随机的次序插入到二叉树中。次序对二叉树的影响体现在

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


代码实现

java

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注