算法导论习题Exercises 14.2-5

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.)

解：

RB-ENUMERATE(x, a, b)
1 start TREE-SEARCH(x, a) //该方法返回不大于a的最紧下解,时间复杂度O(lgn)
2 if start < a
3 then start SUCC[start]
4 while start< b //O(m) 次循环
5 print start
6 start SUCC[start] //时间复杂度O(1),每个节点必须存储Succ这个域,指向下一个节点的位置.

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

We can also answer this question without resorting to augmenting the data
structure: we perform an inorder tree walk, except we ignore (do not recurse
on) the left children of nodes with key < a and the right children of nodes with
key > b. Thus, if we consider both children of a node we will output at least one
of them, therefore, all nodes not counted by m will lie on two paths from the root
to a leaf in the tree. This yields a total running time of (m + lg n) as before.

RB-ENUMERATE(x, a, b)

{

1. if( a<=x<=b)
2. print (x)
3. RB-ENUMERATE(left[x], a, b)
4. RB-ENUMERATE(right[x], a, b)
5. else if(x<a)
6. RB-ENUMERATE(right[x], a, b)
7. else if(x>b)
8. RB-ENUMERATE(left[x], a, b)

}

这个时间复杂度会是O(m+lgn)吗?不解.