說(shuō)道紅黑樹(shù)先講什么是二叉樹(shù)

　　二叉樹(shù)簡(jiǎn)單來(lái)說(shuō)就是 每一個(gè)節(jié)上可以關(guān)聯(lián)倆個(gè)子節(jié)點(diǎn)

　　大概就是這樣子：

　　紅黑樹(shù)

　　紅黑樹(shù)是一種特殊的二叉查找樹(shù)。紅黑樹(shù)的每個(gè)結(jié)點(diǎn)上都有存儲(chǔ)位表示結(jié)點(diǎn)的顏色，可以是紅(Red)或黑(Black)。

　　紅黑樹(shù)的每個(gè)結(jié)點(diǎn)是黑色或者紅色。當(dāng)是不管怎么樣他的根結(jié)點(diǎn)是黑色。每個(gè)葉子結(jié)點(diǎn)(葉子結(jié)點(diǎn)代表終結(jié)、結(jié)尾的節(jié)點(diǎn))也是黑色 [注意：這里葉子結(jié)點(diǎn)，是指為空(NIL或NULL)的葉子結(jié)點(diǎn)!]。

　　如果一個(gè)結(jié)點(diǎn)是紅色的，則它的子結(jié)點(diǎn)必須是黑色的。

　　每個(gè)結(jié)點(diǎn)到葉子結(jié)點(diǎn)NIL所經(jīng)過(guò)的黑色結(jié)點(diǎn)的個(gè)數(shù)一樣的。[確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍，所以紅黑樹(shù)是相對(duì)接近平衡的二叉樹(shù)的!]

　　紅黑樹(shù)的基本操作是添加、刪除。在對(duì)紅黑樹(shù)進(jìn)行添加或刪除之后，都會(huì)用到旋轉(zhuǎn)方法。為什么呢?道理很簡(jiǎn)單，添加或刪除紅黑樹(shù)中的結(jié)點(diǎn)之后，紅黑樹(shù)的結(jié)構(gòu)就發(fā)生了變化，可能不滿足上面三條性質(zhì)，也就不再是一顆紅黑樹(shù)了，而是一顆普通的樹(shù)。而通過(guò)旋轉(zhuǎn)和變色，可以使這顆樹(shù)重新成為紅黑樹(shù)。簡(jiǎn)單點(diǎn)說(shuō)，旋轉(zhuǎn)和變色的目的是讓樹(shù)保持紅黑樹(shù)的特性。