紅黑樹的概述：
紅黑樹本質(zhì)上是一種二叉查找樹，但它在二叉查找樹的基礎(chǔ)上額外添加了一個標記（顏色），同時具有一定的規(guī)則。這些規(guī)則使紅黑樹保證了一種平衡，插入、刪除、查找的最壞時間復雜度都為 O(logn)。
紅黑樹的性質(zhì)：
1、每個節(jié)點要么是紅色，要么是黑色；
2、根節(jié)點永遠是黑色的；
3、所有的葉節(jié)點都是是黑色的（注意這里說葉子節(jié)點其實是上圖中的 NIL 節(jié)點）；
4、每個紅色節(jié)點的兩個子節(jié)點一定都是黑色；
5、從任一節(jié)點到其子樹中每個葉子節(jié)點的路徑都包含相同數(shù)量的黑色節(jié)點。
紅黑樹的旋轉(zhuǎn)
左旋：將一個向右傾斜的紅色鏈接旋轉(zhuǎn)為向左鏈接。對比操作前后，可以看出，該操作實際上是將紅線鏈接的兩個節(jié)點中的一個較大的節(jié)點移動到根節(jié)點上。
右旋：與左旋剛好相反，這里就不贅述了，直接看圖。
紅黑樹的插入與調(diào)整
因為要滿足紅黑樹的這五條性質(zhì)，如果我們插入的是黑色節(jié)點，那就違反了性質(zhì)五，需要進行大規(guī)模調(diào)整；如果我們插入的是紅色節(jié)點，那就只有在要插入節(jié)點的父節(jié)點也是紅色的時候違反性質(zhì)四或者當插入的節(jié)點是根節(jié)點時，違反性質(zhì)二，所以，我們把要插入的節(jié)點的顏色變成紅色。
不需要調(diào)整的情況：
1、當插入的節(jié)點是根節(jié)點時，直接涂黑即可；
2、當要插入的節(jié)點的父節(jié)點是黑色的時候，這個時候插入一個紅色的節(jié)點并沒有對這五個性質(zhì)產(chǎn)生破壞。所以直接插入不用在進行調(diào)整操作。
需要調(diào)整的情況：即插入節(jié)點的父結(jié)點也是紅色。
因為左右對稱的緣故，在此只討論父結(jié)點位于祖父節(jié)點的左支的情況（N 為插入節(jié)點）：
1、叔叔節(jié)點是紅色
這時候只進行換色操作：將父結(jié)點和叔叔節(jié)點涂成黑色，祖父節(jié)點涂成紅色。
2、叔叔節(jié)點是黑色，插入節(jié)點位于父節(jié)點的右支
這時候需要將父結(jié)點當成新的插入節(jié)點，并以他為支點進行左旋操作，進入情況3 。
3、叔叔節(jié)點是黑色，插入節(jié)點位于父結(jié)點的左支
這時候需要先進行換色操作：將父結(jié)點涂成黑色，祖父節(jié)點涂成紅色；然后進行右旋操作。
紅黑樹的刪除與調(diào)整
如果被刪除結(jié)點有孩子，則需要選一個合適的孩子節(jié)點作為新的根節(jié)點，稱為當前節(jié)點。
1、只有左孩子或只有右孩子，則讓該孩子作為當前節(jié)點替代被刪除結(jié)點；
2、左右孩子均存在，則用被刪除結(jié)點的中序后繼結(jié)點作為當前節(jié)點替代被刪除結(jié)點。
注意：替代只是值的互換，顏色不變。
即：當前節(jié)點是黑色，被刪除結(jié)點是紅色。替換后，當前節(jié)點位于被刪除結(jié)點的位置，是紅色；被刪除結(jié)點位于當前節(jié)點原來的位置，是黑色。
不需要調(diào)整的情況：
1、被刪除結(jié)點的是紅色的；
2、被刪除結(jié)點只有一個孩子，用孩子的值替換被刪除節(jié)點，刪除孩子結(jié)點。
需要調(diào)整的情況：（被刪除節(jié)點為黑色）
因為左右對稱的緣故，在此只討論父結(jié)點位于祖父節(jié)點的左支的情況：
1、兄弟節(jié)點為紅色
這時候需要互換父結(jié)點和兄弟節(jié)點的顏色，并進行左旋操作。
2、兄弟節(jié)點為黑色，且其左右孩子也為黑色
將兄弟節(jié)點涂成紅色，再將父結(jié)點當成新的被刪除結(jié)點（只是當成，并不刪除）進行一次調(diào)整（右圖中少了根節(jié)點的左孩子被刪除元素）。
3、兄弟節(jié)點為黑色，且其左孩子為紅色
先換色：左孩子涂成黑色，兄弟節(jié)點涂成紅色；再以兄弟節(jié)點為支點右旋。變成情況4 。
4、兄弟節(jié)點為黑色，且其右孩子為紅色
先換色：父結(jié)點的顏色賦給兄弟節(jié)點，父結(jié)點涂成黑色，兄弟節(jié)點的右孩子涂成黑色；再左旋（右圖中a 的左孩子是被刪除元素）。
紅黑樹的查找
與二叉排序樹的查找一樣：從根節(jié)點出發(fā)，待找值較大時往右子樹方向查找，待找值較小時往左子樹方向查找，直到找到匹配的結(jié)點。若找不到則查找失敗。
紅黑樹的應(yīng)用
Epoll 實現(xiàn)、Java集合中的 TreeSet 和 TreeMap、C++ STL 中的 set、map，以及 Linux 虛擬內(nèi)存的管理，都是通過紅黑樹去實現(xiàn)的。
在平時也可以應(yīng)用于各種管理系統(tǒng)的查找算法中，借此提高效率。
在線生成紅黑樹
看完本教程，如果你還不太能清楚的寫出紅黑樹的構(gòu)造過程，那么，這一個網(wǎng)站將能很好地幫助到你。它不僅支持手動輸入結(jié)點值，也能隨機生成結(jié)點，更重要的是，該網(wǎng)站把每一次插入、刪除的調(diào)整步驟都展現(xiàn)了出來。趕緊試試吧！
在線生成紅黑樹（含變形步驟）
更多內(nèi)容請移步微信公眾號 “ 暗星涌動 ”
