一種高效的二叉查找樹紅黑樹

1、一種高效的二叉查找樹——紅黑樹1紅黑樹的定義查找是計(jì)算機(jī)信息管理的最常見操作。普通的二叉查找樹的查找效率與樹的深度有關(guān)。當(dāng)它的左右子樹深度相差較大時(shí)，查找效率就與單鏈表差不多。為提高查找效率，必須設(shè)法使二叉查找樹的左、右子樹的深度保持平衡。紅黑查找樹就是一種平衡的二叉查找樹。定義一棵二叉查找樹如果滿足下列性質(zhì)，則稱為紅黑樹：（1）每個(gè)結(jié)點(diǎn)或是紅色的，或是黑色的（增加一位表示顏色的存儲(chǔ)位）；（2）每個(gè)空結(jié)點(diǎn)NIL是黑色的；（3）如果一個(gè)結(jié)

2、點(diǎn)是紅色的，則它的兒子應(yīng)是黑色的；（4）從任何一給定結(jié)點(diǎn)到其子孫葉結(jié)點(diǎn)每條簡(jiǎn)單路徑上都具有相同個(gè)數(shù)的黑結(jié)點(diǎn)。圖1給出了一棵紅黑樹的例子，其中黑結(jié)點(diǎn)用方框表示，紅結(jié)點(diǎn)用橢圓表示。2、例：3、推論：若一棵二叉查找樹是紅黑樹，則它的任一子樹也必為紅黑樹。4、紅黑樹的生成可以從空樹開始，通過逐步插入結(jié)點(diǎn)來生成一棵紅黑樹。2紅黑樹的查找效率為方便起見，我們把紅黑樹的葉結(jié)點(diǎn)（NIL）稱為外部結(jié)點(diǎn)，帶有關(guān)鍵字的結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn)。定義定義從某個(gè)結(jié)點(diǎn)x出

3、發(fā)（不包括結(jié)點(diǎn)x本身）到葉結(jié)點(diǎn)的路徑上的黑結(jié)點(diǎn)個(gè)數(shù)，稱為該結(jié)點(diǎn)x的黑深度，記為bd（x），根結(jié)點(diǎn)的黑深度就是該紅黑樹的黑深度。定理1以結(jié)點(diǎn)x為根的子樹，至少有2bd(x)1個(gè)內(nèi)部結(jié)點(diǎn)。證：對(duì)以x結(jié)點(diǎn)為根的子樹深度用歸納法。為方便起見，將以x為根的子樹深度記為d（x）。若d（x）=0，則x就是葉結(jié)點(diǎn)NIL，這時(shí)該子樹的內(nèi)部結(jié)點(diǎn)數(shù)為0，bd(x)=0，故結(jié)論為真。設(shè)d（x）≤k1時(shí)結(jié)論為真，考察d（x）=k的情形。由紅黑樹定義中的性質(zhì)要求3