算法导论12.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 475 阅读时长 ≈ 1 分钟

12.1-1

对于键的集合${1, 4, 5, 10, 16, 17, 21}$，高度为$2,3,4,5,6$的树分别如图所示：

12.1-2

区别在于，二叉搜索树要求右子树所有的关键字都大于当前节点，而左子树的关键字都小于当前节点，这个定义是针对子树的；而最小堆仅要求两个子节点的关键字都大于当前节点，这个定义是针对子节点的。最小堆的两个子节点在定义上并没有先后的区别，因此如果要设计以$O(n)$的时间遍历最小堆按序打印关键字的算法，将会无法做出先遍历左子节点还是右子节点的选择。最终，这个算法无法设计出来。

12.1-3

1
2
3
4
5
6
7
8
9
10
11
12
NONRECURSIVE-INORDER-TREE-WALK(x)
  let S be a new STACK
  p = x
  while not STACK-EMPTY(S) or p != NIL
    while p != NIL
      PUSH(S, p)
      p = p.left
    if STACK-EMPTY(S)
      p = POP(S)
      print p.key
      p = p.right

12.1-4

1
2
3
4
5
6
7
8
9
10
11
PREORDER-TREE-WALK(x)
  if x ≠ NIL
    print x.key
    PREORDER-TREE-WALK(x.left)
    PREORDER-TREE-WALK(x.right)

POSTORDER-TREE-WALK(x)
  if x ≠ NIL
    POSTORDER-TREE-WALK(x.left)
    POSTORDER-TREE-WALK(x.right)
    print x.key

12.1-5

考虑使用反证法证明：如果通过任意一个序列构造一棵二叉搜索树的时间复杂度为$o(n\lg n)$，那么通过中序遍历这棵二叉搜索树，可以以$\Theta(n)$的时间复杂度导出一个有序序列，整个过程的时间复杂度为$o(n\lg n)+\Theta(n)=o(n\lg n)$，这和原题目条件中基于比较排序的运行时间为$\Omega(n\lg n)$矛盾。因此构造任意一个序列的二叉搜索树的时间复杂度为$\Omega(n\lg n)$。