一、如何定義一棵"紅黑樹"？
? ? 顧名思義，紅黑樹中的節(jié)點(diǎn)，一類被標(biāo)記為黑色，一類標(biāo)記為紅色。除此之外，一課紅黑樹還需要滿足這樣幾個(gè)要求：
? ? 1.根節(jié)點(diǎn)是黑色的；
? ? 2.每個(gè)葉子節(jié)點(diǎn)都是黑色的的空節(jié)點(diǎn)（NIL)，也就是說，葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)；
? ? 3.作保相鄰的節(jié)點(diǎn)都不能同時(shí)為紅色，也就是說，紅色節(jié)點(diǎn)是被黑色節(jié)點(diǎn)隔開的；
? ? 4.每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到達(dá)其可達(dá)葉子節(jié)點(diǎn)的所有路徑，都包含數(shù)目相同的黑色節(jié)點(diǎn)；
二、紅黑樹與AVL樹相比有什么優(yōu)勢(shì)？
? ? ?AVL樹是一種高度平衡的二叉樹，所以查找效率非常高，但是，有利就有弊，AVL樹為維持這種高度的平衡，就要付出更多的代價(jià)。每插入刪除就要付出更多的代價(jià)。每次插入、刪除都要做調(diào)整，就比較復(fù)雜、耗時(shí)。所以對(duì)于有頻繁的插入、刪除操作的數(shù)據(jù)集合，使用AVL樹的代價(jià)就有點(diǎn)高了。
? ? 紅黑樹也是一種平衡二叉查找樹。紅黑樹只是做到了近似平衡，但不是嚴(yán)格的平衡，所以在維護(hù)平衡的成本上，要比AVL樹要低。所以，紅黑樹的插入、刪除、查找各種操作性能都比較穩(wěn)定。
三、實(shí)現(xiàn)紅黑樹的插入、刪除需要平衡調(diào)整 ??
? ? 當(dāng)在插入、刪除節(jié)點(diǎn)的過程中，紅黑樹的第三、第四點(diǎn)要求可能會(huì)被破壞，而“平衡調(diào)整”，實(shí)際上就是要把被破壞的第三、第四點(diǎn)恢復(fù)過來。
? ? 在平衡調(diào)整包含兩種基礎(chǔ)的操作：左右旋轉(zhuǎn)和改變顏色
????左旋（rotate left)：圍繞某個(gè)節(jié)點(diǎn)的左旋；
? ? 右旋（rotate right)：圍繞某個(gè)節(jié)點(diǎn)的右旋；
? ? 關(guān)于紅黑樹的調(diào)整，在網(wǎng)上有很多資料，其中紅黑樹很有關(guān)聯(lián)的2-3-4樹，這里有相關(guān)的解釋，看了之后會(huì)有更深的理解：https://www.cnblogs.com/tiancai/p/9072813.html
? ? 不過網(wǎng)上有很多內(nèi)容看不懂，特別是在插入、刪除的節(jié)點(diǎn)的顏色標(biāo)記 紅黑、黑黑，紅-黑黑...?讓人難以理解。
????下面寫一個(gè)插入的案例，用圖的方式以幫助理解；根據(jù)紅黑樹的4個(gè)要求來進(jìn)行調(diào)整，這樣思路不會(huì)跑偏。
? ? ? ?1、往紅黑樹中插入數(shù)據(jù)16，默認(rèn)插入的顏色是紅色，這里為什么是紅色？如果為黑色，當(dāng)你連續(xù)插入，會(huì)影響要求4；紅色可以通過調(diào)整成為標(biāo)準(zhǔn)的紅黑樹；
? ? 2、如上圖1右圖，當(dāng)我們插入16之后很明顯就不符合要求3，這時(shí)我們我們可以看到把只要把9，12?跟11的顏色對(duì)換，就不會(huì)影響它們下面的節(jié)點(diǎn)了；
? ? ? ? 我們知道調(diào)整平衡可以用左右旋轉(zhuǎn)和改變顏色，為什么要先改變顏色？因?yàn)楦淖冾伾粫?huì)對(duì)樹的結(jié)構(gòu)造成變換，這樣剛好這時(shí)有人在查詢的時(shí)候跟之前一樣!?所以我們建議先用改變顏色能不能解決，不能的話再用左右旋轉(zhuǎn)。
? ? 3、如上圖2左圖，我們可以看到11，19都是紅色，很明顯不符合要求3；我們發(fā)現(xiàn)改變11或19的顏色都會(huì)不符合要求4，這時(shí)改變顏色沒有用了，那就用旋轉(zhuǎn)，我們把節(jié)點(diǎn)11右旋轉(zhuǎn)，右旋轉(zhuǎn)之后見圖2右圖，我們發(fā)現(xiàn)這時(shí)已經(jīng)符合要求4了，但是11，19這兩個(gè)節(jié)點(diǎn)不符合要求3，改變11，19的顏色也不符合要求4，我們?cè)侔?1左旋轉(zhuǎn)。這時(shí)看圖2右圖我們發(fā)現(xiàn)這個(gè)樹已經(jīng)變成極不平衡了；
? ? ? ? ? ?紅黑樹有根節(jié)點(diǎn)黑色這一要求，所以我們?cè)谟眯D(zhuǎn)的時(shí)候只要把當(dāng)前節(jié)點(diǎn)往上走總會(huì)有解決的時(shí)候。
? ? 4、如圖4，我們把11節(jié)點(diǎn)旋轉(zhuǎn)之后，發(fā)現(xiàn)只要改變8，11的顏色，就可以讓整個(gè)插入的操作經(jīng)過調(diào)整又變成紅黑樹了。
? ? 總結(jié)：經(jīng)過上面插入的案例，我們發(fā)現(xiàn)通過改變顏色和左右旋轉(zhuǎn)就可以完成對(duì)紅黑樹的調(diào)整，這只是一種情況的操作，我看有些資料關(guān)于紅黑樹的更新（插入和刪除）有分好幾種情況，分別要怎么去調(diào)整，其實(shí)都可以這樣去總結(jié)出來的。
