紅黑樹數(shù)據(jù)結(jié)構(gòu)描述

《紅黑樹數(shù)據(jù)結(jié)構(gòu)描述》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、紅黑樹數(shù)據(jù)結(jié)構(gòu)描述紅黑樹數(shù)據(jù)結(jié)構(gòu)描述紅黑樹紅黑樹是一種自平衡二叉查找樹，是在計(jì)算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實(shí)現(xiàn)關(guān)聯(lián)數(shù)組。它是在1972年由魯?shù)婪颉へ悹柊l(fā)明的，他稱之為"對(duì)稱二叉B樹"，它現(xiàn)代的名字是在LeoJ.Guibas和RobertSedgewick于1978年寫的一篇論文中獲得的。它是復(fù)雜的，但它的操作有著良好的最壞情況運(yùn)行時(shí)間，并且在實(shí)踐中是高效的它可以在O(logn)時(shí)間內(nèi)做查找，插入和刪除，這里的n是樹中元素的數(shù)目。用途和好處紅黑樹和AVL樹一樣都對(duì)插入時(shí)間、刪除時(shí)間和查找時(shí)間提供了最好可能的最壞情況擔(dān)保。這不只是使它們?cè)跁r(shí)間敏感的應(yīng)用如實(shí)時(shí)應(yīng)用

2、(realtimeapplication)中有價(jià)值，而且使它們有在提供最壞情況擔(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(logn)的時(shí)間之外，紅黑樹的持久版本對(duì)每次插入或刪除需要O(logn)紅黑樹是的一種等同。換句話說(shuō)，對(duì)于每個(gè)2-3-4樹，都存在至少一個(gè)數(shù)據(jù)元素是同樣次序的紅黑樹。在2-3-4樹上的插入和刪除操作也等同于在紅黑樹中顏色翻轉(zhuǎn)和旋轉(zhuǎn)。這使得2-3-4樹成為理解紅黑樹背

3、后的邏輯的重要工具，這也是很多介紹算法的教科書在紅黑樹之前介紹2-3-4樹的原因，盡管2-3-4樹在實(shí)踐中不經(jīng)常使用。性質(zhì)紅黑樹是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的，顏色或紅色或黑色。在二叉查找樹強(qiáng)制一般要求以外，對(duì)于任何有效的紅黑樹我們?cè)黾恿巳缦碌念~外要求性質(zhì)1.節(jié)點(diǎn)是紅色或黑色。性質(zhì)2.根是黑色。性質(zhì)3.所有葉子都是黑色(葉子是NIL節(jié)點(diǎn))。性質(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)。這些約束強(qiáng)制了紅黑樹的關(guān)鍵性質(zhì)從根到葉子的最長(zhǎng)的可能路徑不多于最短的可能路徑的兩倍

4、長(zhǎng)。結(jié)果是這個(gè)樹大致上是平衡的。因?yàn)椴僮鞅热绮迦?、刪除和查找某個(gè)值的最壞情況時(shí)間都要求與樹的高度成比例，這個(gè)在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的。要知道為什么這些特性確保了這個(gè)結(jié)果，注意到屬性4導(dǎo)致了路徑不能有兩個(gè)毗連的紅色節(jié)點(diǎn)就足夠了。最短的可能路徑都是黑色節(jié)點(diǎn)，最長(zhǎng)的可能路徑有交替的紅色和黑色節(jié)點(diǎn)。因?yàn)楦鶕?jù)屬性5所有最長(zhǎng)的路徑都有相同數(shù)目的黑色節(jié)點(diǎn)，這就表明了沒(méi)有路徑能多于任何其他路徑的兩倍長(zhǎng)。在很多樹數(shù)據(jù)結(jié)構(gòu)的表示中，一個(gè)節(jié)點(diǎn)有可能只有一個(gè)子節(jié)點(diǎn)，而葉子節(jié)點(diǎn)包含數(shù)據(jù)。用這種范例表示紅黑樹是可能的，但是這會(huì)改變一些屬性并使算法復(fù)雜。為此，

5、本文中我們使用"nil葉子"或"空(null)葉子"，如上圖所示，它不包含數(shù)據(jù)而只充當(dāng)樹在此結(jié)束的指示。這些節(jié)點(diǎn)在繪圖中經(jīng)常被省略，導(dǎo)致了這些樹好像同上述原則相矛盾，而實(shí)際上不是這樣。與此有關(guān)的結(jié)論是所有節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，盡管其中的一個(gè)或兩個(gè)可能是空葉子。操作因?yàn)槊恳粋€(gè)紅黑樹也是一個(gè)特化的二叉查找樹，因此紅黑樹上的只讀操作與普通二叉查找樹上的只讀操作相同。然而，在紅黑樹上進(jìn)行插入操作和刪除操作會(huì)導(dǎo)致不再符合紅黑樹的性質(zhì)?；謴?fù)紅黑樹的屬性需要少量(O(logn))的顏色變更實(shí)際是非?？焖俚暮筒怀^(guò)三次樹旋轉(zhuǎn)對(duì)于插入操作是兩次。雖然插入和刪除很復(fù)雜，但操作時(shí)間仍可以保持為O

6、(logn)次。插入我們首先以二叉查找樹的方法增加節(jié)點(diǎn)并標(biāo)記它為紅色。(如果設(shè)為黑色，就會(huì)導(dǎo)致根到葉子的路徑上有一條路上，多一個(gè)額外的黑節(jié)點(diǎn)，這個(gè)是很難調(diào)整的。但是設(shè)為紅色節(jié)點(diǎn)后，可能會(huì)導(dǎo)致出現(xiàn)兩個(gè)連續(xù)紅色節(jié)點(diǎn)的沖突，那么可以通過(guò)顏色調(diào)換(colorflips)和樹旋轉(zhuǎn)來(lái)調(diào)整。)下面要進(jìn)行什么操作取決于其他臨近節(jié)點(diǎn)的顏色。同人類的家族樹中一樣，我們將使用術(shù)語(yǔ)叔父節(jié)點(diǎn)來(lái)指一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)。注意性質(zhì)和性質(zhì)總是保持著。性質(zhì)只在增加紅色節(jié)點(diǎn)、重繪黑色節(jié)點(diǎn)為紅色，或做旋轉(zhuǎn)時(shí)受到威脅。性質(zhì)只在增加黑色節(jié)點(diǎn)、重繪紅色節(jié)點(diǎn)為黑色，或做旋轉(zhuǎn)時(shí)受到威脅。在下面的示意圖中，將要插入的

7、節(jié)點(diǎn)標(biāo)為N，N的父節(jié)點(diǎn)標(biāo)為P，N的祖父節(jié)點(diǎn)標(biāo)為G，N的叔父節(jié)點(diǎn)標(biāo)為U。在圖中展示的任何顏色要么是由它所處情形所作的假定，要么是這些假定所暗含(imply)的。對(duì)于每一種情況，我們將使用示例代碼來(lái)展示。通過(guò)下列函數(shù)，可以找到一個(gè)節(jié)點(diǎn)的叔父和祖父節(jié)點(diǎn)nodegrandparentnoden{returnnparentparent；}nodeunclenoden{ifnparent==grandparentnleftreturngrandparentnright；elsereturngrandparentnleft；}情形1新節(jié)點(diǎn)N