性質(zhì)
紅黑樹(shù)的結(jié)點(diǎn)都是紅色或者黑色
根結(jié)點(diǎn)是黑色
所有葉子都是黑色（這里的葉子結(jié)點(diǎn)是空結(jié)點(diǎn)）
每個(gè)紅色結(jié)點(diǎn)必須有兩個(gè)黑色的子結(jié)點(diǎn)
從任何一個(gè)節(jié)點(diǎn)到其每個(gè)葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色結(jié)點(diǎn)
性質(zhì)1和性質(zhì)3總是能夠保持著；
性質(zhì)4只有在這些情況下才會(huì)發(fā)生作用：
增加紅色結(jié)點(diǎn)
將黑色結(jié)點(diǎn)重新繪制成紅色結(jié)點(diǎn)
旋轉(zhuǎn)
性質(zhì)5在這些情況下才會(huì)發(fā)生作用：
增加黑色結(jié)點(diǎn)
將紅色結(jié)點(diǎn)重新繪制黑色結(jié)點(diǎn)
旋轉(zhuǎn)
舉例：
插入
用BST的方法將結(jié)點(diǎn)插入，將該結(jié)點(diǎn)標(biāo)記為紅色的（因?yàn)槿绻麡?biāo)記為黑色，則會(huì)導(dǎo)致根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑會(huì)多出一個(gè)黑結(jié)點(diǎn)，無(wú)法滿足性質(zhì)5，而且不容易進(jìn)行調(diào)整），插入的情況包括下面幾種：
插入到一個(gè)空的樹(shù)，插入結(jié)點(diǎn)則為根結(jié)點(diǎn)，只需要將紅色結(jié)點(diǎn)重新轉(zhuǎn)染成黑色結(jié)點(diǎn)來(lái)滿足性質(zhì)2；
新結(jié)點(diǎn)的父結(jié)點(diǎn)為黑色，滿足所有條件；
新結(jié)點(diǎn)的父結(jié)點(diǎn)為紅色，因?yàn)樾再|(zhì)2和性質(zhì)4，所以樹(shù)必然有祖父結(jié)點(diǎn)，則又包括以下的情況：
新插入結(jié)點(diǎn)為父親結(jié)點(diǎn)的左子結(jié)點(diǎn)，那么就構(gòu)成了一個(gè)左左的情況，在之前平衡樹(shù)中提到過(guò)，如果要將其進(jìn)行平衡，則需要對(duì)父結(jié)點(diǎn)進(jìn)行一次單右旋轉(zhuǎn)，形成一個(gè)父親結(jié)點(diǎn)為相對(duì)根結(jié)點(diǎn)，子結(jié)點(diǎn)和祖父結(jié)點(diǎn)為子結(jié)點(diǎn)的樹(shù)，同時(shí)將父親結(jié)點(diǎn)的紅色改為黑色，祖父結(jié)點(diǎn)更改為紅色，這下之前無(wú)法滿足的性質(zhì)4和性質(zhì)5就滿足了；
新插入結(jié)點(diǎn)為父親結(jié)點(diǎn)的右子結(jié)點(diǎn)，那么就會(huì)構(gòu)成一個(gè)左右的情況，在之前的平衡樹(shù)也提到過(guò)要進(jìn)行一次雙旋轉(zhuǎn)，先對(duì)新結(jié)點(diǎn)進(jìn)行一次單左旋轉(zhuǎn)，變成了左左的結(jié)構(gòu)，再進(jìn)行一次單右旋轉(zhuǎn)，從而達(dá)到滿足所有性質(zhì)；
父親結(jié)點(diǎn)和叔父結(jié)點(diǎn)均為紅色，顯然無(wú)法滿足性質(zhì)4，則將父親結(jié)點(diǎn)和叔父結(jié)點(diǎn)繪制成黑色，祖父結(jié)點(diǎn)設(shè)置成紅色，但是仍然無(wú)法滿足情況，比如考慮到祖父結(jié)點(diǎn)可能是根結(jié)點(diǎn)，則無(wú)法滿足性質(zhì)2，或者祖父結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色的，則無(wú)法滿足性質(zhì)4，這時(shí)需要將祖父結(jié)點(diǎn)作為新的結(jié)點(diǎn)來(lái)看待進(jìn)行各種情況的判斷，涉及到對(duì)祖父結(jié)點(diǎn)的遞歸；
父親結(jié)點(diǎn)為紅色同時(shí)叔父結(jié)點(diǎn)為黑色或者從缺，這里又分為
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動(dòng)安全 [無(wú)線安全]玩轉(zhuǎn)無(wú)線電——不安全的藍(lán)牙鎖 2017-07-26
- 消息隊(duì)列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標(biāo)分割】 2017-07-26
- 詞向量-LRWE模型-更好地識(shí)別反義詞同義詞 2017-07-26
- 從棧不平衡問(wèn)題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實(shí)現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動(dòng)安全 Android端惡意鎖屏勒索應(yīng)用分析 2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來(lái)看看(二) 2017-07-26
學(xué)習(xí)是年輕人改變自己的最好方式