• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    基于紅黑樹的操作與檢驗(yàn)

    2014-09-26 01:15:06格桑多吉高定國(guó)
    關(guān)鍵詞:左旋結(jié)點(diǎn)黑色

    唐 松,格桑多吉,高定國(guó)

    (西藏大學(xué)工學(xué)院,拉薩850000)

    紅黑樹屬于自平衡二叉查找樹,是二叉2-3-4樹和對(duì)稱B-樹,是在計(jì)算機(jī)科學(xué)技術(shù)中使用的一種數(shù)據(jù)結(jié)構(gòu),其典型用途是關(guān)聯(lián)數(shù)組的實(shí)現(xiàn)。紅黑樹的每個(gè)節(jié)點(diǎn)都有顏色屬性,顏色為紅色或黑色。除了二叉查找樹的一般要求以外,對(duì)于任何有效的紅黑樹增加了如下的要求:

    性質(zhì)1:節(jié)點(diǎn)顏色為紅色或黑色。

    性質(zhì)2:根節(jié)點(diǎn)為黑色。

    性質(zhì)3:每個(gè)葉節(jié)點(diǎn)(NIL)為黑色。

    性質(zhì)4:每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)皆為黑色(從根到每個(gè)葉子所有路徑上不能有兩個(gè)連續(xù)紅色節(jié)點(diǎn))。

    性質(zhì)5:從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都含有相等數(shù)目的黑色節(jié)點(diǎn)。

    這些約束規(guī)定了紅黑樹的關(guān)鍵性質(zhì):從根到葉子的最長(zhǎng)可能路徑少于或等于最短可能路徑的兩倍長(zhǎng),且這棵樹大致上是平衡的。因?yàn)椴迦?、刪除和查找某個(gè)值的操作的最壞情況,其時(shí)間都要求與樹高度成比例,這個(gè)高度的理論上限不同于普通的二叉查找樹,且允許紅黑樹在最壞情況下都是高效的。

    1 優(yōu)點(diǎn)和用途

    雖然hash表查找非常迅速,但隨著數(shù)據(jù)種類變多,hash表長(zhǎng)會(huì)變得更長(zhǎng)且沖突也會(huì)增多,那么如何能實(shí)現(xiàn)數(shù)據(jù)量無(wú)論多大,查找依然高性能?一般情況下,樹是很好的一種數(shù)據(jù)結(jié)構(gòu),用于插入、查找和刪除等操作都很高效,但在很壞的情況下,操作很費(fèi)時(shí)間,性能難以保證。向樹中插入時(shí),按一定規(guī)則調(diào)整,使其達(dá)到規(guī)則,從而提高其整體與局部的查找效率。

    紅黑樹復(fù)雜,但其操作有良好的最壞情況運(yùn)行時(shí)間,且在實(shí)踐中高效:可以在O(log n)時(shí)間內(nèi)插入、查找和刪除(log n中的n是樹中元素的數(shù)目)。它的統(tǒng)計(jì)性能優(yōu)于平衡二叉樹(AVL-樹),所以紅黑樹應(yīng)用很廣,如字典的實(shí)現(xiàn)、關(guān)聯(lián)數(shù)組上,且內(nèi)存使用率較高。在C++STL中,不少部分(目前包括set、multiset、map、multimap)應(yīng)用了紅黑樹的變體(SGI STL中的紅黑樹的修改提供了更好的性能、對(duì)set操作的支持)。

    2 紅黑樹的構(gòu)建、操作

    2.1 紅黑樹的構(gòu)建

    2.1.1 旋轉(zhuǎn)

    圖1 旋轉(zhuǎn)

    左旋:在某結(jié)點(diǎn)x上做左旋操作時(shí),先假設(shè)其右孩子y不是NIL[T],x可為樹內(nèi)任意右孩子而非NIL[T]結(jié)點(diǎn)。左旋以x至y間的鏈為“支軸”進(jìn)行,使y變?yōu)樵摵⒆訕湫碌母瑈的左孩子β變?yōu)閜ivot的右孩子。

    右旋:可由左旋類推之。

    樹旋轉(zhuǎn)后,保持不變的唯有原樹的搜索性質(zhì),而不能保持原樹的紅黑性質(zhì),紅黑樹的數(shù)據(jù)插入、刪除后可用旋轉(zhuǎn)和重新涂色來(lái)恢復(fù)樹的紅黑性質(zhì)。

    2.1.2 插入和調(diào)整

    調(diào)用插入操作時(shí),為了維護(hù)紅黑樹的五個(gè)性質(zhì),需要進(jìn)行左旋、右旋相應(yīng)操作,因?yàn)椴迦胨惴ㄖ袑涂為紅色可能違背紅黑性質(zhì)的某一條,所以要進(jìn)行相應(yīng)的調(diào)整和顏色重涂,直至滿足紅黑樹的全部性質(zhì)。

    2.2 紅黑樹的操作

    2.2.1 結(jié)點(diǎn)的插入

    插入分為下面兩類情況,相應(yīng)的流程圖如圖2和圖3。

    1)情況1(如圖2):z的叔叔y為紅色。(a)情況,即z是右孩子,因p[p[z](]c)為黑色,所以將p[z]、y都涂成黑色,這就解決了z、p[z]皆為紅色的問(wèn)題,將p[p[z]]涂為紅色,則維持了性質(zhì)5。(b)情況同理分析。

    圖2 結(jié)點(diǎn)的插入情況1

    2)插入情況2(如圖3):z的叔叔y為黑色,且z為右孩子。

    插入情況3(如圖3):z的叔叔y為黑色,且z為左孩子。

    對(duì)于情況2(z是它父親的右孩子),為了維持紅黑樹性質(zhì),左旋變成情況3,此時(shí)z為左孩子,因z、p[z]皆為黑色,故不違背紅黑樹性質(zhì)(注:情況3中,z的叔叔y為黑色,否則此種情況就變?yōu)榍闆r1)。

    情況2、情況3都違背性質(zhì)4(一個(gè)紅結(jié)點(diǎn)的兩個(gè)兒子都為黑色)。因此,情況2->左旋后->情況3,這時(shí)情況3同樣違背性質(zhì)4,所以情況3->右旋,同時(shí)B變成黑色,C變成紅色,得到圖3的最后那一部分。(注:情況2、3都只違背性質(zhì)4,不違背其他性質(zhì)。)

    圖3 結(jié)點(diǎn)的插入情況2

    對(duì)以上三種情況,首先將待插入結(jié)點(diǎn)涂成紅色,接著按照二叉樹的方式進(jìn)行插入操作,因此元素的搜索性質(zhì)不會(huì)改變。為了保證紅黑樹性質(zhì)在插入后依然保持,上面代碼調(diào)用了一個(gè)調(diào)整的輔助程序,對(duì)結(jié)點(diǎn)進(jìn)行重新涂色并旋轉(zhuǎn)。若插入的結(jié)點(diǎn)是根結(jié)點(diǎn),會(huì)破壞性質(zhì)2,若插入結(jié)點(diǎn)的父結(jié)點(diǎn)為紅色,則性質(zhì)4會(huì)被破壞??偠灾迦胍粋€(gè)紅色結(jié)點(diǎn)只會(huì)破壞性質(zhì)2或性質(zhì)4。

    (a)結(jié)點(diǎn)z為紅色。

    (b)若p[z]是根,則p[z]為黑色。

    (c)若有紅黑樹的性質(zhì)被破壞,則最多有一個(gè)被破壞,不是性質(zhì)2就是性質(zhì)4。若違反性質(zhì)2,則發(fā)生原因是z為根且為紅色。若違反性質(zhì)4,則原因?yàn)閦和p[z]皆為紅色,p[p[z]]必然為黑色。

    2.2.2 結(jié)點(diǎn)的刪除

    1)若待刪除結(jié)點(diǎn)不在紅黑樹中,則輸出“not found!”提示。

    2)若待刪除結(jié)點(diǎn)在紅黑樹中,則刪除分為四種情形,相應(yīng)的操作如圖4。

    圖4 結(jié)點(diǎn)的刪除

    注:若待刪除結(jié)點(diǎn)y有左孩子,那么x是y的左孩子,否則為右孩子。

    情況1:x的兄弟w為紅色。同時(shí)改變w、p[z]的顏色,對(duì)p[x]左旋一次,保持了紅黑樹全部性質(zhì)。x的新兄弟new w為旋轉(zhuǎn)之前w的左孩子,且為黑色。所以,情況1轉(zhuǎn)變成情況2或3、4。

    情況2:x的兄弟w為黑色,且w的兩個(gè)孩子都為黑色。因?yàn)閣也為黑色,所以x和w中必須去掉一個(gè)黑色,經(jīng)顏色重涂,w變?yōu)榧t色。p[x]為新結(jié)點(diǎn)new x,賦給x,即操作x<-p[x]。

    情況3:x的兄弟w為黑色,w的左孩子為紅色,w的右孩子為黑色。將w和其左孩子left[w]的顏色都改變(即它們的顏色交換——上圖的D、C顏色互換),并對(duì)w進(jìn)行右旋操作,從而保持了紅黑樹性質(zhì)?,F(xiàn)在x的新兄弟new w是有紅色右孩子的黑結(jié)點(diǎn),從而把情況3轉(zhuǎn)變?yōu)榍闆r4.

    情況4:x的兄弟w為黑色,且w的右孩子為紅色。改變w顏色,并旋轉(zhuǎn)p[x]一次,可以去掉x的額外的黑色,變x為單一黑色,這些并沒(méi)有破壞紅黑樹性質(zhì)。將x置為根(new x=root[T]),結(jié)束程序循環(huán)。

    若從被刪除結(jié)點(diǎn)的顏色分析,可以得到:

    結(jié)論1:若被刪除的結(jié)點(diǎn)為紅色,則結(jié)點(diǎn)被刪除后,紅黑樹性質(zhì)仍保持,原因如下:

    (a)樹中各結(jié)點(diǎn)的黑高都沒(méi)變。

    (b)不存在兩個(gè)相鄰紅色結(jié)點(diǎn)。

    (c)因?yàn)槿粼摴?jié)點(diǎn)為紅色,就不可能為根,所以根仍然為黑色。

    結(jié)論2:若被刪除的結(jié)點(diǎn)為黑色,則會(huì)產(chǎn)生三個(gè)問(wèn)題。(待刪除結(jié)點(diǎn)是y,若y有一個(gè)不是NIL的孩子,則x是y的唯一孩子;若y沒(méi)有孩子,則x為NIL,賦y的父節(jié)點(diǎn)值給x的父節(jié)點(diǎn)(原來(lái)是y)。)

    (a)若y原來(lái)為根,而y的一個(gè)紅色孩子變?yōu)樾碌母?,這就違背了性質(zhì)2。

    (b)若x和p[y](現(xiàn)在也為p[x])都為紅色,就違背了性質(zhì)4。

    (c)刪除y將導(dǎo)致之前包含y的任何路徑上黑結(jié)點(diǎn)個(gè)數(shù)少1。因此,y的一個(gè)祖先破壞了性質(zhì)5,應(yīng)對(duì)的一個(gè)方法是將x視為還有另外的一重黑色,即是說(shuō),若將任意包含x的路徑上的黑結(jié)點(diǎn)個(gè)數(shù)加1,則此假設(shè)下性質(zhì)5成立。當(dāng)刪除黑節(jié)點(diǎn)y時(shí),將其黑色“下推”至y的子節(jié)點(diǎn)?,F(xiàn)在就有這樣的問(wèn)題,x可能既不是紅,也不是黑,違背了性質(zhì)1。x為雙重黑色或紅黑,這就分別給包含x的路徑上黑結(jié)點(diǎn)的個(gè)數(shù)貢獻(xiàn)2個(gè)或1個(gè)。x的顏色屬性仍為紅(若x是紅黑的)或者黑(若x為雙重黑色)。換言之,一個(gè)結(jié)點(diǎn)額外的黑色體現(xiàn)在x指向它,而不是它的顏色屬性。

    3 紅黑樹的檢驗(yàn)

    利用中序遍歷函數(shù),將構(gòu)建或是操作(插入、刪除)后經(jīng)過(guò)調(diào)整的紅黑樹輸出,能直觀地看出構(gòu)建或是操作(插入、刪除)后經(jīng)過(guò)調(diào)整的紅黑樹的正確與否,若輸出的數(shù)列是升序,那么正確(調(diào)整后結(jié)點(diǎn)顏色的正確性基于算法的正確性),反之錯(cuò)誤,因?yàn)闃涞闹行虮闅v按照結(jié)點(diǎn)進(jìn)行升序排列。

    4 流程圖和運(yùn)行結(jié)果

    流程圖和運(yùn)行結(jié)果如圖5和圖6所示。

    圖5 流程圖

    5 小結(jié)

    紅黑樹為樹的構(gòu)建、插入、查找和刪除操作的時(shí)間提供了最佳可能的最壞情況保證,這不僅使它們?cè)趯?duì)時(shí)間敏感的應(yīng)用如實(shí)時(shí)應(yīng)用中有價(jià)值,而且使它們?cè)谧顗那闆r擔(dān)保的其他數(shù)據(jù)結(jié)構(gòu)中擁有作為建造板塊的價(jià)值,如計(jì)算幾何中使用的很多數(shù)據(jù)結(jié)構(gòu)皆可基于紅黑樹。在函數(shù)式編程中,紅黑樹也特別有用,它們是最常用的持久數(shù)據(jù)結(jié)構(gòu)之一,用來(lái)構(gòu)造集合和關(guān)聯(lián)數(shù)組,且在突變之后仍能保持以前的版本。除了O(log n)的時(shí)間,紅黑樹持久版本對(duì)每次的插入或刪除都要O(log n)的空間。

    圖6 運(yùn)行結(jié)果

    因此,深入研究紅黑樹的算法,在理解的基礎(chǔ)上實(shí)現(xiàn),并用中序遍歷輸出這種簡(jiǎn)易且可靠的方法檢驗(yàn),對(duì)紅黑樹的應(yīng)用方面有很重要的參考價(jià)值。

    [1]THOMAS H C,LEISERSON C E.Introduction to algorithms[M].北京:機(jī)械工業(yè)出版社,2006.

    [2]Kenneth A·Reek.C和指針 POINTERS ON C[M].北京:人民郵電出版社,2008.

    [3]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社,2001.

    猜你喜歡
    左旋結(jié)點(diǎn)黑色
    非杓性高血壓宜選用左旋氨氯地平
    氨氯地平:“左旋”是否更好
    左旋的柳
    布達(dá)拉(2019年3期)2019-06-11 05:34:00
    Ladyzhenskaya流體力學(xué)方程組的確定模與確定結(jié)點(diǎn)個(gè)數(shù)估計(jì)
    黑色
    黑色星期五
    那個(gè)黑色的夜晚
    不同時(shí)間段服用左旋氨氯地平治療老年非杓型高血壓患者31例
    基于Raspberry PI為結(jié)點(diǎn)的天氣云測(cè)量網(wǎng)絡(luò)實(shí)現(xiàn)
    基于DHT全分布式P2P-SIP網(wǎng)絡(luò)電話穩(wěn)定性研究與設(shè)計(jì)
    隆昌县| 县级市| 临桂县| 宝丰县| 乐陵市| 铜山县| 岑巩县| 彰武县| 绥滨县| 桃园市| 花莲县| 伊金霍洛旗| 渝中区| 湖北省| 康保县| 长海县| 夏津县| 个旧市| 图木舒克市| 博客| 洛浦县| 固阳县| 景东| 军事| 石屏县| 财经| 三穗县| 霍林郭勒市| 昭觉县| 山东省| 泰和县| 门头沟区| 青河县| 聂拉木县| 重庆市| 民和| 方城县| 池州市| 宣化县| 凌海市| 漳浦县|