圖片源自網(wǎng)絡(luò)，侵刪
介紹
紅黑樹是一種自平衡二叉查找樹，原先被稱作平衡二叉B樹（symmetric binary B-trees）后來更名為紅黑樹（Red-Black Tree）。
與其他二叉查找樹類似，都是在插入和刪除操作時(shí)通過調(diào)整樹的結(jié)構(gòu)來保持二叉查找樹的平衡。相比于AVL樹，他沒有那么嚴(yán)格，所以在插入和刪除時(shí)，調(diào)整樹的結(jié)構(gòu)這種操作相對來說較少，所以擁有不錯的性能。
性質(zhì)
一個樹要是紅黑樹則必須滿足以下五點(diǎn)性質(zhì)。
- 樹的節(jié)點(diǎn)顏色非黑即紅。
- 根節(jié)點(diǎn)是黑色。
- 把空節(jié)點(diǎn)認(rèn)為是黑色葉子節(jié)點(diǎn)。
- 每個紅色節(jié)點(diǎn)的兩個子節(jié)點(diǎn)都是黑色。
- 任一節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑中，他們包含的黑色節(jié)點(diǎn)數(shù)相同。
操作
-
查找
由于紅黑樹同時(shí)也是二叉查找樹，所以查找操作與二叉查找樹一致。從根節(jié)點(diǎn)進(jìn)入，查找的值比當(dāng)前節(jié)點(diǎn)小，則查其左子樹;查找的值比當(dāng)前節(jié)點(diǎn)大，則查詢其右子樹;相等則查詢成功。
-
插入
插入新節(jié)點(diǎn)時(shí)，通常將這個節(jié)點(diǎn)標(biāo)記為紅色。（因?yàn)槿绻切鹿?jié)點(diǎn)是黑色的話，肯定會破壞紅黑樹的性質(zhì)5，而紅色則不一定會破壞）
紅黑樹插入時(shí)可能會導(dǎo)致樹不滿足紅黑樹的性質(zhì)，此時(shí)我們要通過一些操作來對樹進(jìn)行調(diào)整從而使他再次成為紅黑樹。調(diào)整方式有以下三種。
-
變色
紅色變黑色，黑色變紅色。
-
左旋
將當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)變?yōu)楫?dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)的左子樹變?yōu)楫?dāng)前節(jié)點(diǎn)的右子樹。具體如下圖：
8NqI6f.gif -
右旋
將當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)變成當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)的右子樹變?yōu)楫?dāng)前節(jié)點(diǎn)的左子樹。具體如下圖：
8Nqvpq.gif
插入則有如下幾種情形：
-
當(dāng)前樹為空
為了滿足性質(zhì)2,此時(shí)我們只需要新建一個節(jié)點(diǎn)，將他的顏色設(shè)為黑色，作為根節(jié)點(diǎn)即可。
-
插入點(diǎn)已存在
直接更新節(jié)點(diǎn)
-
插入點(diǎn)的父節(jié)點(diǎn)為黑色
不會影響黑色完美平衡，仍然滿足紅黑樹所有性質(zhì)，直接插入即可
-
插入點(diǎn)的父節(jié)點(diǎn)為紅色
-
父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為紅色
此時(shí)違背了紅黑樹的性質(zhì)4,此時(shí)我們應(yīng)當(dāng)采用變色策略，將祖父節(jié)點(diǎn)變?yōu)榧t色，父節(jié)點(diǎn)和父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)變?yōu)楹谏?，然后再將?dāng)前節(jié)點(diǎn)設(shè)為祖父節(jié)點(diǎn)，進(jìn)行下一步處理。（當(dāng)父親節(jié)點(diǎn)和父親節(jié)點(diǎn)的兄弟節(jié)點(diǎn)都是紅色的時(shí)候改變祖父，父，父的兄弟的顏色不會破壞黑色平衡，所以可以這么做）
8NjPHS.png -
父節(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)（LL雙紅）
祖父節(jié)點(diǎn)變紅，父節(jié)點(diǎn)變黑，然后對祖父節(jié)點(diǎn)進(jìn)行右旋
8Uk538.png -
父節(jié)點(diǎn)為祖父節(jié)點(diǎn)的左節(jié)點(diǎn)并且當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的左節(jié)點(diǎn)（LR雙紅）
先對父節(jié)點(diǎn)進(jìn)行左旋操作，然后就會變成LL雙紅，然后在進(jìn)行LL雙紅操作
8UAA4x.png -
父節(jié)點(diǎn)為祖父節(jié)點(diǎn)的右節(jié)點(diǎn)并且當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的右節(jié)點(diǎn)（RR雙紅）
祖父節(jié)點(diǎn)變紅，父節(jié)點(diǎn)變黑，然后對祖父節(jié)點(diǎn)進(jìn)行左旋
8UVMtI.png -
父節(jié)點(diǎn)為祖父節(jié)點(diǎn)的右節(jié)點(diǎn)并且當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的左節(jié)點(diǎn)（RL雙紅）
對父節(jié)點(diǎn)進(jìn)行右旋操作，然后就會變成RR雙紅，然后再進(jìn)行RR雙紅操作
8UV536.png
-
-
-
-
刪除
//TODO
