如何擴(kuò)張數(shù)據(jù)結(jié)構(gòu)

1） 選擇基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)

2） 確定要在基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)中記錄得附加信息

3） 提供基本（內(nèi)部）操作來(lái)維護(hù)附加信息

4） 設(shè)計(jì)新得接口

?

?

1 是一顆紅黑樹(shù)

2 是以區(qū)間左端點(diǎn)維護(hù)的紅黑樹(shù)

3 額外信息是在每個(gè)節(jié)點(diǎn)中， 保存了以該節(jié)點(diǎn)為根的樹(shù)中的最右的區(qū)間端點(diǎn)

?

class Seg {int i, j;int upbound; public:int lower() const {return i;}int higher() const {return j;}int upper() const {return upbound;}bool interval(const Seg &r){if(i > r.j || j < r.i)return false;return true;} };interval-search(T, Seg &i) {x = root(T);while(x && !x.interval(i)){if(x.left && x.left.upper() >= i.lower())x = x.left;else x = x.right;}return x; }

?

個(gè)人說(shuō)明：

1） 算法是正確的，可以正確返回與指定區(qū)間重疊的區(qū)間

2） 該算法只返回與i有重疊得一個(gè)區(qū)間， 并不是所有的區(qū)間

3） 該算法應(yīng)該是非常容易錯(cuò)的。 若把其中的語(yǔ)句修改一下， 算法就錯(cuò)了。

修改之前 if(x.left && x.left.upper() >= i.lower())x = x.left; else x = x.right;修改之后為：/errorrrrrrrr if(x.right && x.right.upper() >= i.lower())x = x.right; elsex = x.left;舉例如下， 根節(jié)點(diǎn)區(qū)間為[20, 21, 40] //40為upper 左孩子區(qū)間為[10, 40, 40] 右孩子區(qū)間為[25, 40, 40] 查找的區(qū)間為 [12,13] 按照修改之后的算法流程， 則到右子樹(shù)中去查找了； 但這個(gè)[12,13]恰恰是只可能出現(xiàn)在左孩子樹(shù)中。

算法導(dǎo)論中文版pdf中有細(xì)微描述是有問(wèn)題的

?

?

根本原因是該區(qū)間樹(shù)是以左端點(diǎn)遞增有序的方式構(gòu)建的紅黑樹(shù)（二叉排序樹(shù)）。

?

?

?

interval_insert, interval_delete 待補(bǔ)充

?

?

interval_insert很簡(jiǎn)單， 只需要注意更新upper就行

interval_insert(x, i) //i插入到以x為根的樹(shù)中 {while(1){if(i.higher() > x.upper()) //更新上界x.upbound = i.higher();if(i.lower() < x.lower()) //然后一直走到尾插入{if(x.left)x = x.left;else{x.left = i;return;}}else{if(x.right)x = x.right;else{x.right= i;return;}} }

?

?

interval_delete 需要回溯， 而且需要精確判斷兩個(gè)區(qū)間是否相同， 相同才能delete ?

?

// 找到x的前驅(qū)或者后繼替換x 【二叉樹(shù)的刪除操作】

// 只需要修改該路徑上的upper

使用棧是肯定可以解決的遞歸呢？ interval_delete(T, p, x, i) //在以樹(shù)T中刪除i {if(x == i){delete(T, p, x, i);} else if(i < x){p = x;x = x.leftinterval_delete(T, p, x, i);}else {p = x;x = x.right;interval_delete(T, p, x, i);}//TODO修改p,x的upper }

?

總結(jié)

以上是生活随笔為你收集整理的区间树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。