紅黑樹(shù)必須滿(mǎn)足下面的五個(gè)的性質(zhì)：
性質(zhì)1.節(jié)點(diǎn)是紅色或黑色。
性質(zhì)2.根節(jié)點(diǎn)是黑色雷猪。
性質(zhì)3.每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（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)制了紅黑樹(shù)的關(guān)鍵性質(zhì):?從根到葉子的最長(zhǎng)的可能路徑不多于最短的可能路徑的兩倍長(zhǎng)射沟。結(jié)果是這個(gè)樹(shù)大致上是平衡的。因?yàn)椴僮鞅热绮迦胗刖场h除和查找某個(gè)值的最壞情況時(shí)間都要求與樹(shù)的高度成比例验夯，這個(gè)在高度上的理論上限允許紅黑樹(shù)在最壞情況下都是高效的，而不同于普通的二叉查找樹(shù)摔刁。
旋轉(zhuǎn)和顏色變化規(guī)則
1挥转、添加的節(jié)點(diǎn)必須為紅色
2、變色的情況：當(dāng)前結(jié)點(diǎn)的父親是紅色簸搞，且它的叔結(jié)點(diǎn)也是紅色：
2.1?把父節(jié)點(diǎn)設(shè)置為黑色
2.2?把叔節(jié)點(diǎn)設(shè)置為黑色
2.3?把祖父節(jié)點(diǎn)設(shè)置為紅色
2.4?把當(dāng)前指針定義到祖父節(jié)點(diǎn)扁位，設(shè)為當(dāng)前要操作的
3、左旋的情況：當(dāng)前父節(jié)點(diǎn)是紅色趁俊，叔節(jié)點(diǎn)是黑色域仇，且當(dāng)前的節(jié)點(diǎn)是右子樹(shù)。
3.1?以父節(jié)點(diǎn)作為左旋寺擂。
4暇务、右旋的情況：當(dāng)前父節(jié)點(diǎn)是紅色，叔節(jié)點(diǎn)是黑色怔软，且當(dāng)前的節(jié)點(diǎn)是左子樹(shù)垦细。
4.1?把父節(jié)點(diǎn)變成黑色
4.2?把祖父節(jié)點(diǎn)變?yōu)榧t色
4.3?以祖父節(jié)點(diǎn)右旋轉(zhuǎn)
平衡二叉樹(shù)(AVL)的性質(zhì)?
它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)挡逼。這個(gè)方案很好的解決了二叉查找樹(shù)退化成鏈表的問(wèn)題括改，把插入，查找家坎，刪除的時(shí)間復(fù)雜度最好情況和最壞情況都維持在O(logN)嘱能。但是頻繁旋轉(zhuǎn)會(huì)使插入和刪除犧牲掉O(logN)左右的時(shí)間吝梅，不過(guò)相對(duì)二叉查找樹(shù)來(lái)說(shuō)，時(shí)間上穩(wěn)定了很多惹骂。
區(qū)別：?
1苏携、紅黑樹(shù)放棄了追求完全平衡，追求大致平衡对粪，在與平衡二叉樹(shù)的時(shí)間復(fù)雜度相差不大的情況下右冻，保證每次插入最多只需要三次旋轉(zhuǎn)就能達(dá)到平衡，實(shí)現(xiàn)起來(lái)也更為簡(jiǎn)單著拭。
2纱扭、平衡二叉樹(shù)追求絕對(duì)平衡，條件比較苛刻茫死，實(shí)現(xiàn)起來(lái)比較麻煩跪但，每次插入新節(jié)點(diǎn)之后需要旋轉(zhuǎn)的次數(shù)不能預(yù)知。
