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