第14章 14.3 区间树

# 一、综述 ### 1.区间树 区间树中一种对动态集合进行维护的红黑树，该集合中的每个元素x都包含一个区间int[x] ### 2.基础数据结构 红黑树，其中每个结点x包含一个区间域int[x]，x的关键字为区间的低端点 ### 3.附加信息 max[x]：以x为根的子树中所有区间的 端点的最大值 ### 4.对信息的维护 max[x] = max(high[int[x]], max[left[x]], max[right[x]]) ### 5.设计新的操作 INTERVAL-SEARCH(T, i)：找出树T中覆盖区间i的那个结点。 # 二、代码 ### 1.section14_3.cpp https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter14/section14_3.cpp ### 2.main.cpp https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter14/section14_3Test.cpp # 三、练习 ### 14.3-1 ~~~ LEFT-ROTATE(T, x) 1 y <- right[x] 2 right[x] <- left[y] 3 if left[y] != nil[T] 4 then p[left[y]] <- x 5 p[y] <- p[x] 6 if p[x] = nil[T] 7 then root[T] <- y 8 else if x = left[p[x]] 9 then left[p[x]] <- y 10 else right[p[x]] <- y 11 left[y] <- x 12 p[x] <- y 13 max[y] <- max[x] 14 max[x] <- max(high[int[x]], max[left[x]], max[right[x]]) ~~~ ### 14.3-2 ~~~ 对二中的程序做三点修改 （1）L37，<改成<= （2）L40，>改成>= （3）L443，>=改成> ~~~ ### 14.3-3 那本答案PDF写得比较麻烦，不明天为什么要写得这么复杂，我只分了三种情况 ~~~ node* Interval_Tree::Search_Min(node *root, interval i) { node *x = root, *y; //先从左子树上找 if(x->left && x->left->max >= i.low) { y = Search_Min(x->left, i); if(y != nil) return y; } //如果x与i相交，就不需要找左子树了 if(Overlap(x->inte, i)) return x; //最后在右子树上找 if(x->right) return Search_Min(x->right, i); return nil; } ~~~ ### 14.3-4 ~~~ void Interval_Tree::Search_All(node *root, interval i) { node *x = root, *y; //如果当前结点与i相交 if(Overlap(x->inte, i)) cout<<x->inte.low<<' '<<x->inte.high<<endl; //先从左子树上找 if(x->left && x->left->max >= i.low) Search_All(x->left, i); //从右子树上找 if(x->right && x->key <= i.high) Search_All(x->right, i); } ~~~ ### 14.3-5 ~~~ node* Interval_Tree::Search_Exactly(interval i) { //从根结点开始 node *x = root; //不是叶子且不重叠 while(x != nil) { if(x->inte.low == i.low && x->inte.high == i.high) return x; //在左子树中 if(x->left != nil && x->key >= i.low) x = x->left; //在右子树中 else x = x->right; } return nil; } ~~~ ### 14.3-6 见[算法导论-14.3-6-MIN-GAP](http://blog.csdn.net/mishifangxiangdefeng/article/details/7907597) ### 14.3-7 见[算法导论-14.3-7-O(nlgn)时间求矩形集合中重叠矩形的个数](http://blog.csdn.net/mishifangxiangdefeng/article/details/7909307)