源碼分析大綱

• 數(shù)據(jù)結(jié)構(gòu)解析
• 紅黑樹試下原理刨析

數(shù)據(jù)結(jié)構(gòu)解析

1.紅黑樹

紅黑樹圖形

1.1 紅黑樹概念

紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹羽圃，
紅黑樹和AVL樹類似，都是在進(jìn)行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能切心。它雖然是復(fù)雜的，但它的最壞情況運(yùn)行時間也是非常良好的，并且在實(shí)踐中是高效的： 它可以在O(log n)時間內(nèi)做查找绽昏，插入和刪除协屡，這里的n 是樹中元素的數(shù)目。它與AVL樹之間的區(qū)別:AVL樹必須通過多次旋轉(zhuǎn)后達(dá)到平衡而涉，而紅黑樹可以通過旋轉(zhuǎn)或者變色從而保持平衡著瓶。

1.2 紅黑樹的特性

1. 節(jié)點(diǎn)為黑色或紅色
2. 根節(jié)點(diǎn)為黑色
3. 每個葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL） [注意：這里葉子節(jié)點(diǎn)，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)啼县！]
4. 每個紅色節(jié)點(diǎn)的兩個孩子節(jié)點(diǎn)都是黑色（保證從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點(diǎn)
5. 從任一節(jié)點(diǎn)到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)（保證了紅黑樹從根到葉子的最長路徑不會超過最短路徑的兩倍）

紅黑樹圖片

1.3 紅黑樹保持平衡方式(旋轉(zhuǎn)材原、變色)

左旋轉(zhuǎn)

左旋圖

以1為節(jié)點(diǎn)進(jìn)行左旋，1往下3節(jié)點(diǎn)往上走季眷，3節(jié)點(diǎn)的左節(jié)點(diǎn)變成1余蟹，3的原來左節(jié)點(diǎn)掛到1的右節(jié)點(diǎn)上，形成左旋子刮。

右旋

右旋圖

以3節(jié)點(diǎn)為中心進(jìn)行右旋威酒，3節(jié)點(diǎn)往下走，1節(jié)點(diǎn)提上挺峡，1節(jié)點(diǎn)的右節(jié)點(diǎn)變?yōu)?節(jié)點(diǎn)葵孤，1節(jié)點(diǎn)的原先右節(jié)點(diǎn)掛到3節(jié)點(diǎn)的右節(jié)點(diǎn)上，旋轉(zhuǎn)完畢橱赠。

變色
安裝紅黑樹五條規(guī)定進(jìn)行操作尤仍。

1.4 紅黑樹的插入(當(dāng)前節(jié)點(diǎn)默認(rèn)為紅色)

• 1. 當(dāng)前節(jié)點(diǎn)的插入點(diǎn)為根節(jié)點(diǎn)的時候，對插入節(jié)點(diǎn)進(jìn)行變色處理狭姨。

     
     
     根節(jié)點(diǎn)

• 2.當(dāng)前節(jié)點(diǎn)插入點(diǎn)為黑色的情況直接插入宰啦。

  
  
  image.png

• 3.當(dāng)前節(jié)點(diǎn)的插入點(diǎn)為紅色，并且它的兄弟節(jié)點(diǎn)也為紅色的時候饼拍，插入點(diǎn)赡模，和兄弟節(jié)點(diǎn)變?yōu)楹谏迦朦c(diǎn)的父節(jié)點(diǎn)變?yōu)榧t色师抄，再以插入點(diǎn)的父節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)漓柑，進(jìn)行下一輪的判斷。(I為當(dāng)前節(jié)點(diǎn)司澎，P為插入點(diǎn)欺缘，PP為父節(jié)點(diǎn)，S為叔叔節(jié)點(diǎn))

  
  
  叔紅情況判斷

• 4. 當(dāng)前節(jié)點(diǎn)的插入點(diǎn)為紅色挤安，并且他的兄弟節(jié)點(diǎn)為黑色或者不存在谚殊，把插入點(diǎn)變黑色，插入點(diǎn)的父節(jié)點(diǎn)變?yōu)榧t色蛤铜，如果當(dāng)前點(diǎn)在插入的左子樹嫩絮，以插入點(diǎn)的父節(jié)點(diǎn)為中心丛肢，進(jìn)行右旋轉(zhuǎn)，如果當(dāng)前點(diǎn)在插入點(diǎn)的右子樹剿干，以插入點(diǎn)的父節(jié)點(diǎn)為中心蜂怎，進(jìn)行左旋轉(zhuǎn)。進(jìn)而平衡置尔。

     
     
     叔為黑或者為空情況
     
     
     叔為黑或者為空情況

1.5紅黑樹刪除問題分析杠步。

• 1.如果刪除的的為根節(jié)點(diǎn)。

  
  
  刪除根節(jié)點(diǎn)

• 2.如果刪除節(jié)點(diǎn)為紅節(jié)點(diǎn)榜轿，并且只有左節(jié)點(diǎn)幽歼，或者只有右節(jié)點(diǎn)，使用左節(jié)點(diǎn)谬盐，或者右節(jié)點(diǎn)代替當(dāng)前刪除節(jié)點(diǎn)甸私。并且把左節(jié)點(diǎn)或者右節(jié)點(diǎn)變?yōu)楹谏Ｖ苯觿h除節(jié)點(diǎn)飞傀。

  
  
  有一個子類

• 3.如果刪除節(jié)點(diǎn)為黑色皇型，并且只有左節(jié)點(diǎn)，或者只有右節(jié)點(diǎn)砸烦，直接使用下面的節(jié)點(diǎn)代替刪除點(diǎn)弃鸦，不用進(jìn)行變色操作。

  
  
  image.png

• 4. 刪除節(jié)點(diǎn)幢痘，既有左子樹寡键，又有右子樹的情況，直接獲取它的后繼節(jié)點(diǎn)代替當(dāng)前節(jié)點(diǎn)雪隧，變?yōu)閯h除后繼節(jié)點(diǎn)方法。后繼節(jié)點(diǎn)只有兩種情況员舵，沒有節(jié)點(diǎn)脑沿，或者為只有右節(jié)點(diǎn)。

     
     
     刪除節(jié)點(diǎn)兩點(diǎn)情況

• 4.1 當(dāng)只有右節(jié)點(diǎn)的時候規(guī)則轉(zhuǎn)換為2和3的規(guī)則马僻。

• 4.2 當(dāng)沒有節(jié)點(diǎn)的時候庄拇，如果節(jié)點(diǎn)為紅色，直接進(jìn)行刪除韭邓。

  
  
  沒有節(jié)點(diǎn)的情況

• 4.3 當(dāng)沒有左節(jié)點(diǎn)且沒有右節(jié)點(diǎn)的情況措近，并且顏色為黑色，如果他的兄弟節(jié)點(diǎn)為黑色女淑。

• 4.3.1 如果兄弟節(jié)點(diǎn)沒有左子樹瞭郑，并且沒有右子樹，把兄弟節(jié)點(diǎn)變?yōu)榧t色鸭你，如果父節(jié)點(diǎn)為紅色屈张，把父親節(jié)點(diǎn)變?yōu)楹谏苋ǎh(huán)平衡結(jié)束， 如果父親節(jié)點(diǎn)為黑色阁谆，刪除當(dāng)前子樹節(jié)點(diǎn)后碳抄，當(dāng)前節(jié)點(diǎn)會少一個黑節(jié)點(diǎn)，再以當(dāng)前父類節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)進(jìn)行下一次循環(huán)判斷场绿，直到平衡(注意:通過畫圖的剖效，下一次循環(huán)不會再進(jìn)入4.3.1而會進(jìn)入4.3.2或者為root節(jié)點(diǎn)。從而實(shí)現(xiàn)平衡)(treemap刪除循環(huán)邏輯)**
  

  第一種情況
  
  
  第二種循環(huán)的情況

• 4.3.1 如果兄弟節(jié)點(diǎn)為黑色焰盗，有右子樹璧尸，把右子樹設(shè)置為黑色，兄弟節(jié)點(diǎn)的顏色與父節(jié)點(diǎn)交換姨谷，把父節(jié)點(diǎn)設(shè)置為黑色逗宁，以兄弟節(jié)點(diǎn)進(jìn)行左旋，這樣梦湘，左邊節(jié)點(diǎn)比右邊節(jié)點(diǎn)多出一個黑節(jié)點(diǎn)瞎颗，刪除多余的那個節(jié)點(diǎn)，保持了紅黑樹平衡
  

  兄弟節(jié)點(diǎn)有值情況展示
  
  
  兄弟節(jié)點(diǎn)有值情況展示

• 4.3.2 **如果兄弟節(jié)點(diǎn)為紅色捌议，把兄弟節(jié)點(diǎn)變?yōu)楹谏甙危腹?jié)點(diǎn)變?yōu)榧t色，以兄弟節(jié)點(diǎn)進(jìn)行左旋瓣颅，得到4.3.1的情況倦逐，以4.3.1的情況繼續(xù)進(jìn)行操作。

  
  
  兄弟節(jié)點(diǎn)為紅色情況