《算法导论》第12章 二叉搜索树 个人笔记

第12章 二叉搜索树

12.1 定义

设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点，则有y.key≤x.key。如果y是x右子树中的一个结点，则有y.key≥x.key。
遍历：

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

如果x是一颗有n个结点子树的根，那么调用INORDER-TREE-WALK(x)需要Θ(n)时间。

12.2 查询

查找指定关键字k

• 递归式：

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

• while循环式：

ITERATIVE-TREE-SEARCH(x,k)
while x != NULL && k != x.key
    if k < x.key
        x = x.left
    else x = x.right
return x

查找最小和最大关键字、前继和后驱

• 最小关键字

TREE-MINIMUM(x)
while x.left != NULL
    x = x.left
return x

• 最大关键字

TREE-MAXIMUM(x)
while x.right != NULL
    x = x.right
return x

• 后驱

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

• 前继

TREE-PREDECESSOR(x)
if x.left != NULL
    return TREE-MAXIMUM(x.left)
y = x.p
while y != NULL && y.left == x
    x = y
    y = y.p
return y

定理：在一颗高度为h的二叉搜索树上，动态集合上的以上5个查询操作可以在O(h)时间内完成。

12.3 插入和删除

• 插入（默认树中不存在待插入的关键字）

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

• 删除

// 用一颗以v为根的子树替换一颗以u为根的子树，
// 结点u的双亲变为结点v的双亲
TRANSPLANT(T,u,v)
if u.p == NULL
    T.root = v
elseif u == u.p.left
    u.p.left = v
else u.p.right = v
if v != NULL
    v.p = u.p

TREE-DELETE(T,z)
if z.left ==  NULL
    TRANSPLANT(T,z,z.right)
elseif z.right == NULL
    TRANSPLANT(T,z,z.left)
else
    y = TREE-MINIMUM(z.right) // find z's successor
    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
    t.left.p = y

定理：在一颗高度为h的二叉搜索树上，动态集合上的INSERT和DELETE操作可以在O(h)时间内完成。

12.4 随机构建二叉搜索树

定理：一颗有n个不同关键字的随机构建二叉搜索树的期望为O(lgn)。