算法导论12.3 Exercises 答案

发表于 2023-01-30 更新于 2023-07-03 分类于算法导论阅读次数：本文字数： 959 阅读时长 ≈ 1 分钟

12.3-1

该过程由算法TREE-INSERT-RECURSIVE给出。

INSERT-RECURSIVE(x, p, z)
  if x == NIL
    z.p = p
    if z.key < p.key
      p.left = z
    else
      p.right = z
  else if z.key < x.key
    INSERT-RECURSIVE(x.left, x, z)
  else
    INSERT-RECURSIVE(x.right, x, z)

TREE-INSERT-RECURSIVE(T, z)
  if T.root == NIL
    T.root = z
  else INSERT-RECURSIVE(T.root, NIL, z)

12.3-2

ITERATIVE-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-INSERT(T, z)
  x = T.root // node being compared with z
  y = NIL // y will be parent of z
  while x ≠ NIL // descend until reaching a leaf
    y = x
    if z.key < x.key
      x = x.left
    else x = x.right
  z.p = y // found the location—insert z with parent y
  if y == NIL
    T.root = z // tree T was empty
  elseif z.key < y.key
    y.left = z
  else y.right = z

对比算法ITERATIVE-TREE-SEARCH和TREE-INSERT，可以发现while循环完全一致。原因也很简单：插入和查询节点时，遍历二叉搜索树的路径基本相同，区别仅在于查询路径比插入路径多了一个节点\(k\)，也就是自身。因此查询节点的次数比插入时多了\(1\)。

12.3-3

最好情况：\(n\)个节点构成的树足够平衡，此时所有节点的高度都不超过\(O(\lg n)\)。因此在这种情况下，这个排序算法的时间复杂度为\(n\cdot O(\lg n)=O(n\lg n)\)。

最坏情况：\(n\)个数有序插入，此时整棵树仅通过左子节点（或右子节点）串联成一棵高度为\(n\)的树。第\(i\)个节点需要遍历\(i-1\)个节点才能插入，那么整个排序算法总共需要遍历\(\dfrac{n(n-1)}{2}\)次的节点，这种情况下的排序算法的时间复杂度为\(\Theta(n^2)\)。

12.3-4

当\(z\)是一个叶子节点的时候，算法TREE-DELETE的第2行的第3个参数z.right为NIL。
当\(z\)有右子节点，并且\(z\)的后继\(y\)不是\(z\)的右子节点时，如果\(y\)没有右子节点，算法TREE-DELETE的第7行的第3个参数y.right为NIL。

12.3-5

不正确，考虑如下二叉搜索树删除\(1,2\)的区别。

最终得到的二叉树形态并不一样，因此这个说法是错误的。原因在于前4行代码，如果其中删除的节点的其中1个儿子为空，那么直接将另一个子树移到这个节点上，而不会再去找将要删除节点的后继。

12.3-6

算法PARENT的代码和插入INSERT非常相似，只是由判断空指针变成了判断是否当前键。

PARENT(T, z)
  x = T.root
  y = NIL
  while x != NIL and x.key != z.key
    y = x
    if z.key < x.key
      x = x.left
    else
      x = x.right
  if x == NIL
    return NIL
  return y

INSERT(T, z)
  x = T.root
  y = NIL
  // pre是z的前驱节点。由于z是叶子节点，因此z的前驱必定在从根节点r到z的路径上。
  pre = NIL
  while x != NIL
    y = x
    if z.key < x.key
      x = x.left
    else
      pre = x
      x = x.right
  if y == NIL
    T.root = z
  else if z.key < y.key
    y.left = z
    // z是叶子节点，没有右孩子，因此其后继就是y。
    z.succ = y
    if pre != NIL
      pre.succ = z
  else
    y.right = z
    z.succ = y.succ
    y.succ = z

TRANSPLANT'(T, u, v)
  p = PARENT(T, u)
  if p == NIL
      T.root = v
  else if u == p.left
      p.left = v
  else
      p.right = v
  // 相比于TRANSPLANT，算法TRANSPLANT'不再考虑父节点指针的指向。

//此为求取z的前驱节点的算法。
PREDECESSOR(T, z)
  if z.left != NIL
    return TREE-MAXIMUM(x.left)
  x = T.root
  // 此时前驱节点pre必定在从根节点r到z的路径上。
  pre = NIL
  while x != NIL and x.key != z.key
    if z.key < x.key
      x = x.left
    else
      pre = x
      x = x.right
  return pre

DELETE(T, z)
  pre = PREDECESSOR(T, z)
  if pre != NIL
    pre.succ = z.succ
  if z.left == NIL
    TRANSPLANT(T, z, z.right)
  else if z.right == NIL
    TRANSPLANT(T, z, z.left)
  else
    y = TREE-MIMIMUM(z.right)
    if PARENT(T, y) != z.right
      TRANSPLANT(T, y, y.right)
      y.right = z.right
    TRANSPLANT(T, z, y)
    y.left = z.left

12.3-6

这种新的删除算法由TREE-DELETE'给出，对它的修改仅仅是第6行求\(z\)的后继变成了求\(z\)的前驱，并且子节点指针都从left改成right，right改成left。

为了保证这种前驱和后继地位的平等性，可以考虑使用随机算法。每次执行删除一个节点\(z\)，如果\(z\)有两个子节点，那么随机选择前驱或者是后继来覆盖当前节点。更形象的，这个算法由TREE-DELETE-FAIR给出。

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-MAXIMUM(z.left)
    if y ≠ z.left
      TRANSPLANT(T, y, y.left)
      y.left = z.left
      y.left.p = y
    TRANSPLANT(T, z, y)
    y.right = z.right
    y.right.p = y

TREE-DELETE-FAIR(T, z)
  r = RANDOM(0, 1)
  if r == 0
    TREE-DELETE'(T, z)
  else
    TREE-DELETE(T, z)