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

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

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

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