CLRS12 二叉搜索树

2017-05-18 | 阅读：次

12.1 什么是二叉搜索树

左子树关键字不大于x，右子树关键字不小于x

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

练习12.1-1 For the set of keys {1, 4, 5, 10, 16, 17, 21}, draw binary search trees of height 2, 3, 4, 5, and 6.

这个蛮简单的

练习12.1-2 What is the difference between the binary-search-tree property and the min-heap property (see page 129)? Can the min-heap property be used to print out the keys of an n-node tree in sorted order in O(n) time? Explain how or why not.

最小堆根结点的值是最小的。做不到因为每次extract-min之后还要min-heapify

练习12.1-3 Give a nonrecursive algorithm that performs an inorder tree walk. (Hint: There is an easy solution that uses a stack as an auxiliary data structure and a more complicated but elegant solution that uses no stack but assumes that two point- ers can be tested for equality.)

这个题在前几章做过了，一种做法是用栈，另一种做法是用两个指针遍历树。

练习12.1-4 Give recursive algorithms that perform preorder and postorder tree walks in Θ (n) time on a tree of n nodes.

和inorder一样，稍微改变下print的位置。

练习12.1-5 Argue that since sorting n elements takes Ω(nlgn) time in the worst case in the comparison model, any comparison-based algorithm for constructing a binary search tree from an arbitrary list of n elements takes Ω(nlgn) time in the worst case.

构造好二叉搜索树后只需要O(n)时间就能inorder输出，所以如果不是Omega(nlgn)就矛盾了。

12.2 查询二叉搜索树

查询操作包括SEARCH、MINIMUM、MAXIMUM、SUCCESSOR、PREDECESSOR，均在O(h)时间完成。

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)

ITEREATIVE-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

即使关键字并非全不相同，我们仍然定义任何结点x的后继和前驱为分别调用TREE-SUCCESSOR(x)和TREE-PREDECESSOR(x)所返回的结点。
练习12.2-1 Suppose that we have numbers between 1 and 1000 in a binary search tree and want to search for the number 363. Which of the following sequences could not be the sequence of nodes examined?

1. 2, 252, 401, 398, 330, 344, 397, 363.
2. 924, 220, 911, 244, 898, 258, 362, 363.
3. 925, 202, 911, 240, 912, 245, 363.
4. 2, 399, 387, 219, 266, 382, 381, 278, 363.
5. 935, 278, 347, 621, 299, 392, 358, 363.

3是不可能的，因为912>911
5是不可能的，因为347>299

练习12.2-2 Exercises 12.2-2 Write recursive versions of the TREE-MINIMUM and TREE-MAXIMUM procedures.

RECURSIVE-TREE-MINIMUM(x)
    if x == NIL
        return NIL
    if x.left == NIL
        return x.key
    return RECURSIVE-TREE-MINIMUM(x.left)

RECURSIVE-TREE-MAXIMUM(x)
    if x == NIL
        return NIL
    if x.right == NIL
        return x.key
    return RECURSIVE-TREE-MAXIMUM(x.right)

练习12.2-3 Write the TREE-PREDECESSOR procedure.

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

练习12.2-4 Professor Bunyan thinks he has discovered a remarkable property of binary search trees. Suppose that the search for key k in a binary search tree ends up in a leaf. Consider three sets: A, the keys to the left of the search path; B, the keys on the search path; and C, the keys to the right of the search path. Professor Bunyan claims that any three keys a∈A, b∈B, and c∈C must satisfy a ≤ b ≤ c. Give a smallest possible counterexample to the professor’s claim.

反例到处都是= =

练习12.2-5 Show that if a node in a binary search tree has two children, then its successor has no left child and its predecessor has no right child.

如果后继有left-child，那么left-child就是后继，同理前驱。

练习12.2-6 Consider a binary search tree T whose keys are distinct. Show that if the right subtree of a node x in T is empty and x has a successor y, then y is the lowest ancestor of x whose left child is also an ancestor of x. (Recall that every node is its own ancestor.)

This is how we ran SUCCESSOR algorithm.

练习12.2-7 inorder tree walk of an n-node binary search tree can be implemented by finding the minimum element in the tree with TREE-MINIMUM and then making n − 1 calls to TREE- SUCCESSOR. Prove that this algorithm runs in Θ(n) time.

遍历每条边两次，所有O(n)

练习12.2-8 Prove that no matter what node we start at in a height-h binary search tree, k successive calls to TREE-SUCCESSOR take O(k + h) time.

上一题是这题的一个实例。只需要证明访问边的次数 N ≤ (4h + 2k) ,假设 S 是开始起点,E 是结束点.

当S和E在同一条路径时(S是E的祖先或者E是S的祖先),结论很明显。
当S和E不在同一条路径时,令A为S和E的最小公共祖先。考虑节点S到 A,后继函数回溯的成本至多只有 2h(思考的时候千万不要将后继到的点的 成本算进去,那部分在 2k 里),A 到 E 的多余的成本至多也只有 2h, 其他都 是正常的回溯到的点访问边 2k.

练习12.2-9 Let T be a binary search tree whose keys are distinct, let x be a leaf node, and let y be its parent. Show that key[y] is either the smallest key in T larger than key[x] or the largest key in T smaller than key[x].

那不然还能怎样= =
x是y的left-child, x的后继是y, x是y的right-child, x的前驱是y

12.3 插入和删除

插入和删除会引起二叉搜索树表示的动态集合的变化，一定要修改数据结构来反映这个变化。

TREE-INSERT(T, x)
    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
    elif z.key < y.key
        y.left - z
    else y.right = z

删除一个节点比较麻烦，分为三种基本情况。

# 用一棵子树替换另一棵子树并成为其parent的child结点
TRANSPLANT(T, u, v)
    if u.p == NIL
        T.root = v
    elif 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)
    elif 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)

在一棵高度为h的二叉搜索树上，实现动态集合INSERT和DELETE的运行时间均为O(h)
练习12.3-1 Give a recursive version of the TREE-INSERT procedure.

TREE-INSERT(T, z)
    if T.root == NIL
        T.root = z
    else
        if z < T.root.key
            TREE-INSERT(T.root.left, z)
        else TREE-INSERT(T.root.right, z)

练习12.3-2 Suppose that a binary search tree is constructed by repeatedly inserting distinct values into the tree. Argue that the number of nodes examined in searching for a value in the tree is one plus the number of nodes examined when the value was first inserted into the tree.

多检查一次是否相等。

练习12.3-3 We can sort a given set of n numbers by first building a binary search tree containing these numbers (using TREE-INSERT repeatedly to insert the numbers one by one) and then printing the numbers by an inorder tree walk. What are the worst-case and best-case running times for this sorting algorithm?

最坏情况即二叉搜索树退化为链表 O(n^2)
最好情况 O(nlgn)

练习12.3-4 Is the operation of deletion “commutative” in the sense that deleting x and then y from a binary search tree leaves the same tree as deleting y and then x? Argue why it is or give a counterexample.

不一样。反例很好找。

练习12.3-5 为每个结点换一个设计，x.p指向parent，x.succ指向后继。设计SEARCH, INSERT, DELETE.

待完成

练习12.3-6 When node z in TREE-DELETE has two children, we could splice out its predecessor rather than its successor. Some have argued that a fair strategy, giving equal priority to predecessor and successor, yields better empirical performance. How might TREE-DELETE be changed to implement such a fair strategy?

待完成

12.4 随机构建二叉搜索树

如果n个关键字按严格递增的次序插入，那么树一定是高度为n-1的一条链
可以证明平均情形性能更接近于最好情形。
定义n个关键字的一棵随机构建二叉搜索树为按随即次序插入这些关键字到一棵初始的空树中而生成的树。一棵随机构建二叉搜索树的期望高度为O(nlgn)
练习12.4-2 Describe a binary search tree on n nodes such that the average depth of a node in the tree is Θ(lg n) but the height of the tree is w(lg n). Give an asymptotic upper bound on the height of an n-node binary search tree in which the average depth of a node is Θ(lg n).

满二叉树就符合节点平均深度为Θ(lgn),高度是lgn
渐进上界为Θ(lgn)

练习12.4-3 Show that the notion of a randomly chosen binary search tree on n keys, where each binary search tree of n keys is equally likely to be chosen, is different from the notion of a randomly built binary search tree given in this section.

随即构建的构建过程有n!种可能。
随机选择二叉树是指在n个元素构成的所有二叉搜索树中随机选择一个。二叉搜索树需要满足一定条件，因此可能输小于n!.

练习12.4-4 Consider RANDOMIZED-QUICKSORT operating on a sequence of n distinct input numbers. Prove that for any constant k > 0, all but O(1/(n^k)) of the n! input permutations yield an O(nlgn) running time.

等价于证明不是O(nlgn)的排列只会有常数个
只有当输入数列有序(即最坏情况出现)时，才不是O(nlgn),故只有常数个。

思考题

12-1 带有相同关键字的二叉搜索树

a.
    O(n^2)

b.
    O(nlgn)

c.
    O(n)

d.
    最坏还是O(n^2)
    期望情况下接近最优情况即第二种，因此是O(nlgn)

12-2 基数树

中序遍历。

Sasuke

Jing

CLRS12 二叉搜索树

12.1 什么是二叉搜索树

12.2 查询二叉搜索树

12.3 插入和删除

12.4 随机构建二叉搜索树

思考题