說道紅黑樹先講什么是二叉樹
二叉樹簡單來說就是 每一個節(jié)上可以關(guān)聯(lián)倆個子節(jié)點(diǎn)
大概就是這樣子：
紅黑樹
紅黑樹是一種特殊的二叉查找樹。紅黑樹的每個結(jié)點(diǎn)上都有存儲位表示結(jié)點(diǎn)的顏色，可以是紅(Red)或黑(Black)。
紅黑樹的每個結(jié)點(diǎn)是黑色或者紅色。當(dāng)是不管怎么樣他的根結(jié)點(diǎn)是黑色。每個葉子結(jié)點(diǎn)(葉子結(jié)點(diǎn)代表終結(jié)、結(jié)尾的節(jié)點(diǎn))也是黑色 [注意：這里葉子結(jié)點(diǎn)，是指為空(NIL或NULL)的葉子結(jié)點(diǎn)!]。
如果一個結(jié)點(diǎn)是紅色的，則它的子結(jié)點(diǎn)必須是黑色的。
每個結(jié)點(diǎn)到葉子結(jié)點(diǎn)NIL所經(jīng)過的黑色結(jié)點(diǎn)的個數(shù)一樣的。[確保沒有一條路徑會比其他路徑長出倆倍，所以紅黑樹是相對接近平衡的二叉樹的!]
紅黑樹的基本操作是添加、刪除。在對紅黑樹進(jìn)行添加或刪除之后，都會用到旋轉(zhuǎn)方法。為什么呢?道理很簡單，添加或刪除紅黑樹中的結(jié)點(diǎn)之后，紅黑樹的結(jié)構(gòu)就發(fā)生了變化，可能不滿足上面三條性質(zhì)，也就不再是一顆紅黑樹了，而是一顆普通的樹。而通過旋轉(zhuǎn)和變色，可以使這顆樹重新成為紅黑樹。簡單點(diǎn)說，旋轉(zhuǎn)和變色的目的是讓樹保持紅黑樹的特性。
京公網(wǎng)安備 11010802030320號