在《構(gòu)建兒童數(shù)據(jù)的二叉樹》中渗稍，本號(hào)曾經(jīng)寫過平衡二叉樹在存儲(chǔ)大量數(shù)據(jù)的應(yīng)用得湘。但是失都，平衡二叉樹雖然美觀，其插入刪除修改需要涉及的旋轉(zhuǎn)過程很耗費(fèi)時(shí)間涌乳，例如刪除結(jié)點(diǎn)時(shí)需要對(duì)結(jié)點(diǎn)到根結(jié)點(diǎn)的整個(gè)路徑進(jìn)行向上遞歸的旋轉(zhuǎn)，此時(shí)需要消耗log2(n)的時(shí)間燕锥。因此對(duì)于數(shù)據(jù)量大于1000的情況，平衡二叉樹的時(shí)間劣勢(shì)會(huì)非常明顯淌友。

當(dāng)統(tǒng)計(jì)的數(shù)據(jù)的數(shù)目越來(lái)越大且需要大量更替時(shí)，平衡二叉樹旋轉(zhuǎn)的時(shí)間浪費(fèi)會(huì)越來(lái)越顯著骇陈，圖一來(lái)自新禾融媒體工作室

因此震庭，人們根據(jù)平衡二叉樹旋轉(zhuǎn)消耗時(shí)間長(zhǎng)等缺點(diǎn)，把它改進(jìn)為紅黑樹你雌。并對(duì)紅黑樹進(jìn)行以下定義：

1器联、每個(gè)結(jié)點(diǎn)只能是紅色和黑色的。

2婿崭、根結(jié)點(diǎn)為黑色拨拓。

3、NIL結(jié)點(diǎn)為黑色氓栈。

4渣磷、紅色結(jié)點(diǎn)的孩子都為黑色。

5授瘦、從任一結(jié)點(diǎn)到NIL葉子結(jié)點(diǎn)的所有簡(jiǎn)單路徑都經(jīng)過相同數(shù)量的黑色結(jié)點(diǎn)醋界。

與平衡二叉樹相比，紅黑樹的插入和刪除后的調(diào)整更加復(fù)雜提完，情況也更加多形纺。并且需要定義NIL結(jié)點(diǎn)為黑色的，且雙親徒欣、左右孩子都是自己的結(jié)點(diǎn)作為輔助逐样，同時(shí)，規(guī)定根結(jié)點(diǎn)的雙親和葉子結(jié)點(diǎn)的左右孩子都是NIL結(jié)點(diǎn)打肝。

想象一下初夏數(shù)之不盡的蓮霧果實(shí)脂新，紅與黑被定義為淺色或深色的果實(shí)

對(duì)于紅黑樹的插入，根據(jù)定義5粗梭，新插入的結(jié)點(diǎn)必然是紅色的戏羽。在尋找到插入的位置之后，需要對(duì)插入之后的情況進(jìn)行以下調(diào)整：

當(dāng)插入的結(jié)點(diǎn)的雙親為黑色時(shí)楼吃，無(wú)需調(diào)整始花，直接插入。

當(dāng)插入的結(jié)點(diǎn)的雙親為紅色時(shí)孩锡，由于違反了定義4酷宵、5，需要通過下列6種情況以保持其性質(zhì)躬窜。這6種情況可以分為插入結(jié)點(diǎn)在左子樹和插入結(jié)點(diǎn)在右子樹的各3種情況浇垦。

以下只討論插入結(jié)點(diǎn)在左子樹的3種情況，另外3種情況為這3種情況的左右對(duì)換荣挨。

為討論方便男韧，以下定義插入結(jié)點(diǎn)為N結(jié)點(diǎn)朴摊，雙親結(jié)點(diǎn)為P結(jié)點(diǎn)，雙親的雙親（祖親）為G結(jié)點(diǎn)此虑，祖親在雙親之外的孩子結(jié)點(diǎn)（旁親）為U結(jié)點(diǎn)甚纲。

情況1：結(jié)點(diǎn)的旁親為紅色。此時(shí)只需要把雙親和旁親變黑色朦前，祖親變紅色介杆，并迭代調(diào)整插入結(jié)點(diǎn)的祖親結(jié)點(diǎn)直到根結(jié)點(diǎn)。

情況2：結(jié)點(diǎn)的旁親為黑色韭寸，且插入結(jié)點(diǎn)為雙親的右孩子春哨。此時(shí)需要對(duì)雙親進(jìn)行左旋（關(guān)于左旋、右旋詳見《構(gòu)建兒童數(shù)據(jù)的二叉樹》恩伺，不再贅述）赴背，至此進(jìn)入情況3。

情況3：結(jié)點(diǎn)的旁親為黑色晶渠，且插入結(jié)點(diǎn)為雙親的左孩子凰荚。此時(shí)需要把雙親結(jié)點(diǎn)變?yōu)楹谏嬗H結(jié)點(diǎn)變?yōu)榧t色乱陡，并對(duì)祖親結(jié)點(diǎn)進(jìn)行右旋。

對(duì)于紅黑樹的刪除仪壮，和平衡二叉樹的刪除基本一樣憨颠。當(dāng)刪除的是葉子結(jié)點(diǎn)時(shí)，葉子結(jié)點(diǎn)用NIL結(jié)點(diǎn)頂替积锅，當(dāng)刪除的是只有一個(gè)孩子的結(jié)點(diǎn)時(shí)爽彤，用其孩子頂替，當(dāng)刪除的結(jié)點(diǎn)有兩個(gè)孩子時(shí)缚陷，用右子樹的最左邊結(jié)點(diǎn)（或左子樹的最右邊結(jié)點(diǎn)）頂替适篙。刪除根結(jié)點(diǎn)時(shí)，用NIL結(jié)點(diǎn)頂替根結(jié)點(diǎn)自身箫爷。

不同在于嚷节，刪除的過程中需對(duì)被刪除的結(jié)點(diǎn)進(jìn)行判斷并調(diào)整。

當(dāng)被刪除的結(jié)點(diǎn)為紅色時(shí)虎锚，無(wú)需調(diào)整硫痰，直接刪除。

當(dāng)被刪除的結(jié)點(diǎn)為黑色時(shí)窜护，由于違反了定義5效斑，需要通過下列8種情況以保持其性質(zhì)。這8種情況可以分為被刪除的是左孩子還是右孩子的各4種情況柱徙。

和插入一樣缓屠，以下只討論被刪除的是左孩子的4種情況奇昙，另外4種情況為這4種情況的左右對(duì)換。

為討論方便敌完，以下定義被刪除結(jié)點(diǎn)為D結(jié)點(diǎn)储耐，被刪除結(jié)點(diǎn)的同胞結(jié)點(diǎn)為S結(jié)點(diǎn)，同胞結(jié)點(diǎn)的左孩子（左侄親）為L(zhǎng)結(jié)點(diǎn)蠢挡，同胞結(jié)點(diǎn)的右孩子（右侄親）為R結(jié)點(diǎn)弧岳。

另外，下列圖中結(jié)點(diǎn)如果為黑圈套紅圈（或紅圈套黑圈）的业踏，說明結(jié)點(diǎn)可為紅色或黑色禽炬，其內(nèi)圈和外圈的顏色變化為結(jié)點(diǎn)顏色不同基礎(chǔ)下顏色的變化。

情況1：結(jié)點(diǎn)的同胞為紅色勤家。此時(shí)需要把同胞結(jié)點(diǎn)變黑色腹尖，雙親結(jié)點(diǎn)變紅色，并對(duì)雙親結(jié)點(diǎn)左旋伐脖。

情況2：結(jié)點(diǎn)的同胞為黑色热幔，且兩個(gè)侄親結(jié)點(diǎn)均為黑色。此時(shí)把同胞結(jié)點(diǎn)變紅色讼庇，然后迭代向雙親方向調(diào)整绎巨。

情況3：結(jié)點(diǎn)的同胞為黑色，右侄親為黑色且左侄親為紅色蠕啄。此時(shí)把同胞變紅色场勤，左侄親變黑色并對(duì)同胞結(jié)點(diǎn)右旋。至此進(jìn)入情況4歼跟。

情況4：結(jié)點(diǎn)的同胞為黑色和媳，右侄親為紅色。此時(shí)先把雙親的顏色作為同胞的顏色哈街，之后把雙親變黑色留瞳，右侄親變黑色，之后對(duì)雙親結(jié)點(diǎn)進(jìn)行左旋骚秦，最后把結(jié)點(diǎn)返回到根結(jié)點(diǎn)她倘。

當(dāng)被刪除的對(duì)應(yīng)結(jié)點(diǎn)不是根結(jié)點(diǎn)且結(jié)點(diǎn)為黑色時(shí)，循環(huán)上述操作在刪除的最后作箍，需要設(shè)置根結(jié)點(diǎn)總為黑色帝牡。

由于平衡二叉樹最大高度為

，小于紅黑樹的最大高度

蒙揣，所以在最壞的情況下靶溜，平衡二叉樹在遍歷或搜索的時(shí)間會(huì)略小于紅黑樹。但兩者的差別不大，當(dāng)數(shù)據(jù)足夠多時(shí)罩息，平衡二叉樹和紅黑樹的樹高都會(huì)趨向于理想狀態(tài)嗤详，即

。

平衡二叉樹的美觀性瓷炮，體現(xiàn)在層次的均勻上葱色，但這種均勻是要付出旋轉(zhuǎn)的代價(jià)的

而由于紅黑樹在刪除時(shí)最多只需要3次旋轉(zhuǎn)即可保持其性質(zhì)，但平衡二叉樹最多需要log2(n)次娘香，因此在大量插入刪除苍狰，體現(xiàn)在需要大量更替數(shù)據(jù)的情況下，紅黑樹的優(yōu)勢(shì)將更加顯現(xiàn)出來(lái)烘绽，并抵消不完美平衡的不足淋昭。

紅黑樹在結(jié)構(gòu)上像梅樹、橘子樹和榕樹安接，不完全平衡翔忽，但插入刪除修改的時(shí)間更少

在現(xiàn)實(shí)當(dāng)中，紅黑樹在計(jì)算機(jī)科學(xué)領(lǐng)域的應(yīng)用很廣盏檐。例如Java中的TreeSet歇式，TreeMap就是紅黑樹的應(yīng)用，并且紅黑樹log2(n)的時(shí)間復(fù)雜度使得它在數(shù)據(jù)量很大時(shí)胡野，可以充當(dāng)鏈表的作用材失。

對(duì)于現(xiàn)實(shí)世界中像一個(gè)區(qū)域內(nèi)所有的兒童的數(shù)據(jù)，一個(gè)網(wǎng)頁(yè)的站內(nèi)搜索功能等查找功能相對(duì)更多的情況硫豆，平衡二叉樹可有利于提高運(yùn)行的效率龙巨。而像一個(gè)景點(diǎn)內(nèi)部的人的信息存儲(chǔ)，大量用戶爭(zhēng)奪一個(gè)直播的貸款等需要大量數(shù)據(jù)插入刪除的的情況够庙，紅黑樹的效率會(huì)更高恭应。

這兩種應(yīng)用類似圖書館的文獻(xiàn)資料管理或旅游點(diǎn)的進(jìn)出流量

但隨著數(shù)據(jù)量的增長(zhǎng)抄邀，紅黑樹的優(yōu)勢(shì)會(huì)漸漸顯著耘眨，這也是紅黑樹比平衡二叉樹應(yīng)用更廣的原因。

參考資料

https://blog.csdn.net/l_o_s/article/details/105703296

https://blog.csdn.net/v_JULY_v/article/details/6124989

https://blog.csdn.net/v_JULY_v/article/details/6109153

https://blog.csdn.net/v_JULY_v/article/details/6285620