Skip to content

Latest commit

 

History

History
120 lines (80 loc) · 3.95 KB

14.1.md

File metadata and controls

120 lines (80 loc) · 3.95 KB
Raw

Exercises 14.1-1

Show how OS-SELECT(T, 10) operates on the red-black tree T of Figure 14.1.

Answer

Straightforward.

Exercises 14.1-2

Show how OS-RANK(T, x) operates on the red-black tree T of Figure 14.1 and the node x with key[x] = 35.

Answer

Straightforward.

Exercises 14.1-3

Write a nonrecursive version of OS-SELECT.

Answer

OS-SELECT(x, i)
	while x != null
		r <- size[left[x]]+1
		if i = r
			then return x
		elseif i < r
			x = left[x]
		else
			x = right[x]
			i = i - r

Exercises 14.1-4

Write a recursive procedure OS-KEY-RANK(T, k) that takes as input an order-statistic tree T and a key k and returns the rank of k in the dynamic set represented by T . Assume that the keys of T are distinct.

Answer

OS-KEY-RANK(T,k)
	r <- size[left[T]] + 1
	if k = key[T]
		return r
	else if key[T] > k
		return OS-KEY-RANK(left[T],k)
	else 		
        return r + OS-KEY-RANK(right[T],k)

Exercises 14.1-5

Given an element x in an n-node order-statistic tree and a natural number i, how can the ith successor of x in the linear order of the tree be determined in O(lg n) time?

Answer

i-SUCCESSOR(x, i)
1.y <-- OS-RANK(T,x)
2.r <-- OS-SELECT(T,y + i)
3.return r

Exercises 14.1-6

Observe that whenever the size field of a node is referenced in either OS-SELECT or OS- RANK, it is used only to compute the rank of the node in the subtree rooted at that node. Accordingly, suppose we store in each node its rank in the subtree of which it is the root. Show how this information can be maintained during insertion and deletion. (Remember that these two operations can cause rotations.)

Answer

插入

遍历所有的节点,根据节点值与插入节点值的大小,遍历到的节点的rank分别是增1和减1.(O(n),所以记录rank值效率很低)

旋转操作不影响rank价值.

删除

删除操作跟插入类似,也需要遍历所有的节点更新rank值.

Exercises 14.1-7

Show how to use an order-statistic tree to count the number of inversions (see Problem 2-4) in an array of size n in time O(n lg n).

Answer

注意,红黑树建树的时间是O(nlgn),因此我们需要边建树边计算inversions.

而这个过程相当简单，因为每次INSERT的时候，我们都能利用OS-RANK计算出该节点的rank,从而计算出inversion.

Exercises 14.1-8

Consider n chords on a circle, each defined by its endpoints. Describe an O(n lg n)-time algorithm for determining the number of pairs of chords that intersect inside the circle. (For example, if the n chords are all diameters that meet at the center, then the correct answer is .) Assume that no two chords share an endpoint.

Answer

reference

n条弦共有2n个端点，每个端点对于圆心来说，都对应一个[0,2pi)内的角度.

我们按角度大小（实际上就是逆时针方向）对这2n个角度进行排序，这一步需要花费O(n*logn)

对于每条弦来说，它的两个端点都可以看做是“事件点”：从0角度开始逆时针在圆上扫描，遇到弦的第一个点可以看成是弦的“起点”，遇到的第二个点看成是弦的“终点”.

然后，我们用一棵“顺序统计树”来辅助进行处理(初始化当然为空).

按照角度小到大的顺序遍历这2n个端点：
	如果该端点是某条弦X的“起点”
		将弦X插入顺序统计树中（以X的“起点”角度作为key）；
	如果该端点是某条弦X的“终点”
		统计出目前这棵树中有多少条弦的“起点”角度比X的“起点”角度大，这就是与X相交的弦的数量；
		//对于顺序统计树来说，上面这步只要O(logn)就能实现
		将弦X从顺序统计树中删除； //这一步同样只需要O(logn)

所以整个下来，O(n*logn)内可以完成。

Follow @louis1992 on github to help finish this task.