Skip to content

Latest commit

 

History

History
90 lines (59 loc) · 5.32 KB

14.2.md

File metadata and controls

90 lines (59 loc) · 5.32 KB
Raw

some English answers come from here

Exercises 14.2-1

Show how the dynamic-set queries MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR can each be supported in O(1) worst-case time on an augmented order- statistic tree. The asymptotic performance of other operations on order-statistic trees should not be affected. (Hint: Add pointers to nodes.)

Answer

MINIMUM : 用一个指针指向最小的元素，每次插入的时候跟最小元素比较看是否需要更新，如果删除的是最小元素，那么MINIMUM更新为原来元素的SUCCESSOR

MAXIMUM : 同MINIMUM类似

SUCCESSOR : 给每个节点增加一个successor指针.左旋和右旋不改变successor属性.在插入的时候,如果最终插入到x的左边,那么

temp = x->predecessor
temp->successor = newnode
x->predecessor = newnode
newnode->predecessor = temp
newnode->successor = x

PREDECESSOR : 跟SUCCESSOR类似

Exercises 14.2-2

Can the black-heights of nodes in a red-black tree be maintained as fields in the nodes of the tree without affecting the asymptotic performance of any of the red-black tree operations? Show how, or argue why not.

Answer

可以.

因为插入和删除影响的基本只有根节点到叶子节点路径上的点(包括每个节点的一些"邻居"),总共影响的是O(lgn)的节点，因此是可以维护的.

具体操作就要根据书中几个不同的case去处理叻.

Yes, we can maintain black-heights as attributes in the nodes of a red-black tree without affecting the asymptotic performance of the red-black tree operations. Because the black-height of a node can be computed from the information at the node and its two children (actually one). According to Theorem 14.1 (page 309 of CLRS) insertion and deletion can be still performed in O(lg n) time.

Exercises 14.2-3

Can the depths of nodes in a red-black tree be efficiently maintained as fields in the nodes of the tree? Show how, or argue why not.

Answer

No, because the depth of a node depends on the depth of its parent. When the depth of a node changes, the depths of the whole nodes in the subtree rooted at that node must be updated. It may lead to run in more than O(lg n) time in worse case.

Exercises 14.2-4

Let ⊗ be an associative binary operator, and let a be a field maintained in each node of a red- black tree. Suppose that we want to include in each node x an additional field f such that f[x] = a[x1] ⊗ a[x2] ⊗ ··· ⊗ a[xm], where x1, x2,..., xm is the inorder listing of nodes in the subtree rooted at x. Show that the f fields can be properly updated in O(1) time after a rotation. Modify your argument slightly to show that the size fields in order-statistic trees can be maintained in O(1) time per rotation.

Answer

  1. 证明f fields 可以在O(1)时间内更新
    设x的左右儿子分别为x.left和x.right，且x的左子树包含k个节点。
    因为红黑树是排序二叉树，且在f的定义中，这些节点是按照中序遍历的顺序排列, 所以前k个节点属于x的左子树，后面的节点属于x的右子树， 所以有：
    f[x.left] = a[x1] ⊗ a[x2] ⊗ ··· ⊗ a[xk]
    f[x.right] = a[x(k+1)] ⊗ ··· ⊗ a[xm]
    又因为f满足结合律(associative binary operator)，
    可得：f[x] = f[x.left] ⊗ a[x] ⊗ f[x.right]
    故f可在O(1)内更新。
  2. 通过f，证明size fields可以在O(1)时间内更新
    令每个节点的a field都等于1，运算⊗ 为加法，则f即为每个节点的size属性，由以上证明可知，size可以在O(1)内更新

Exercises 14.2-5

We wish to augment red-black trees with an operation RB-ENUMERATE(x, a, b) that outputs all the keys k such that a ≤ k ≤ b in a red-black tree rooted at x. Describe how RB- ENUMERATE can be implemented in Θ(m +lg n) time, where m is the number of keys that are output and n is the number of internal nodes in the tree. (Hint: There is no need to add new fields to the red-black tree.)

Answer

RB-ENUMERATE(x, a, b)
	start <- TREE-SEARCH(x, a) //该方法返回不大于a的最紧下解,时间复杂度O(lgn)
	if start < a
		start <- successor[start]
		while start < b   //O(m) 次循环
			print start
			start <- SUCC[start]

根据练习12.2-8的结论，查找m个下继的时间为O(m+lgn)

因此总的时间复杂度O(m+lgn)

We first call TREE-SEARCH(x, a). We must modify this procedure a bit to return the smallest element greater than or equal to a rather than NIL if a is not in the tree. This step runs in time O(lg n). Then we call a sequence of TREE-SUCCESSOR(x) until we encounter a node whose key is larger than b. So we call this m times. According to execise 12.2-8, that starting at an arbitrary node, m successive calls to TREE-SUCCESSOR take O(m + h) time. Thus RB-ENUMERATE can be implemented in Θ(m + lg n) time. We can also use SUCCESSOR and PREDECESSOR pointers as previous execise 14.2-1 shows with O(1) running time to output m keys in the second step. Total running time is O(m + lg n) too.

Follow @louis1992 on github to help finish this task.