Skip to content

Latest commit

 

History

History
110 lines (77 loc) · 4.69 KB

14.3.md

File metadata and controls

110 lines (77 loc) · 4.69 KB
Raw

Exercises 14.3-1

Write pseudocode for LEFT-ROTATE that operates on nodes in an interval tree and updates the max fields in O(1) time.

Answer

max[y] = max[x]
max[x] = maximum(high[x], max(left[x]), max(right[x]))

Exercises 14.3-2

Rewrite the code for INTERVAL-SEARCH so that it works properly when all intervals are assumed to be open.

Answer

INTERVAL-SEARCH(T, i)
	x <- root[T]
	while x != nil[T] and i does not overlap int[x]
		do if left[x] != nil[T] and max[left[x]] > low[i]
			then x<-left[x]
			else x<-right[x]
	return x

Exercises 14.3-3

Describe an efficient algorithm that, given an interval i, returns an interval overlapping i that has the minimum low endpoint, or nil[T] if no such interval exists.

Answer

MIN-INTERVAL-SEARCH(T,i):
  x = T.root
  while x != T.nil:
	  if x.left != T.nil and i.low <= x.left.max:
		  x = x.left
	  elif x.int overlaps i:
		  break
	  else
		  x = x.right
  return x

Exercises 14.3-4

Given an interval tree T and an interval i, describe how all intervals in T that overlap i can be listed in O(min(n, k lg n)) time, where k is the number of intervals in the output list. (Optional: Find a solution that does not modify the tree.)

Answer

INTERVAL-OVERLAP-LIST(T,x,i)
1.if i overlap int[x]
2.    print x
3.if left[x] != nil[T] and max(left[x]) >=low[i]
4.    INTERVAL-OVERLAP-LIST(T,left[x],i)
5.if right[x] != nil[T] and low[int[x]] <= high[i] and max[right[x]] >= low[i]
6.    INTERVAL-OVERLAP-LIST(T,right[x] != i)
7.return x

@Brief: Every branch returns at least an interval, thus at the maxmum there are k branches recur down the tree giving running time O(klgn).On the other hand if all n nodes are visted we can list all the required intervals for sure.

Exercises 14.3-5

Suggest modifications to the interval-tree procedures to support the new operation INTERVAL-SEARCH-EXACTLY(T, i), which returns a pointer to a node x in interval tree T such that low[int[x]] = low[i] and high[int[x]] = high[i], or nil[T] if T contains no such node. All operations, including INTERVAL-SEARCH-EXACTLY, should run in O(lg n) time on an n-node tree.

Answer

INTERVAL-SEARCH-EXACTLY(T, i)
	x = SEATCH(T, low[i])      //SEARCH为普通红黑树的查找操作
	if high[x] == high[i]
		return x
	return nil[T]

Exercises 14.3-6

Show how to maintain a dynamic set Q of numbers that supports the operation MIN-GAP, which gives the magnitude of the difference of the two closest numbers in Q. For example, if Q = {1, 5, 9, 15, 18, 22}, then MIN-GAP(Q) returns 18 - 15 = 3, since 15 and 18 are the two closest numbers in Q. Make the operations INSERT, DELETE, SEARCH, and MIN-GAP as efficient as possible, and analyze their running times.

Answer

给节点新增3个属性

  • mingap : 以当前节点为根,其子树的最小gap.叶子结点为∞
  • maxval : 以当前节点为根,其子树的最大关键字
  • minval : 以当前节点为根,其子树的最小关键字

根据定理14.1(红黑书的扩张):每次红黑树的插入,删除都能在O(lgn)的时间内更新这些信息

<br >

minval[x] = min(key[x], minval[x->left])
maxval[x] = max(key[x], maxval[x->right])
mingap[x] = min(mingap[left[x]], mingap[right[x], key[x]−maxval[left[x]], minval[right[x]]−key[x])

Exercises 14.3-7

VLSI databases commonly represent an integrated circuit as a list of rectangles. Assume that each rectangle is rectilinearly oriented (sides parallel to the x- and y-axis), so that a representation of a rectangle consists of its minimum and maximum x- and y-coordinates. Give an O(n lg n)-time algorithm to decide whether or not a set of rectangles so represented contains two rectangles that overlap. Your algorithm need not report all intersecting pairs, but it must report that an overlap exists if one rectangle entirely covers another, even if the boundary lines do not intersect. (Hint: Move a "sweep" line across the set of rectangles.)

Answer

reference

先根据x坐标排序所有2n个点,然后将一扫描线扫过整个矩形,我们让扫描线和y轴平行,从最左开始扫描.如果碰到某矩形平行y轴的左边那条边条边，就把这条边插入到区间树中，如果碰到某矩形平行y轴的右边那条边，就把这条边从区间树中删除，如果碰到在插入边时，和前面插入的边有重叠，那么就是矩形重叠了.

Time: O(n lg n)

• O(n lg n) to sort the rectangles (we can use merge sort or heap sort).

• O(n lg n) for interval-tree operations (insert, delete, and check for overlap).

Follow @louis1992 on github to help finish this task.