Write pseudocode for LEFT-ROTATE that operates on nodes in an interval tree and updates the max fields in O(1) time.
max[y] = max[x]
max[x] = maximum(high[x], max(left[x]), max(right[x]))Rewrite the code for INTERVAL-SEARCH so that it works properly when all intervals are assumed to be open.
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 xDescribe 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.
MIN-INTERVAL-SEARCH(T, i)
x <- root[T]
res <- INT_MAX
while x != nil[T]
if i overlap int[x]
res <- min(res, low[x])
do if left[x] != nil[T] and max[left[x]] >= low[i]
then x<-left[x]
else x<-right[x]
return x 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.)
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.
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.
INTERVAL-SEARCH-EXACTLY(T, i)
x = SEATCH(T, low[i]) //SEARCH为普通红黑树的查找操作
if high[x] == high[i]
return x
return nil[T] 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.
给节点新增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])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.)
先根据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.