一、紅黑樹的定義
【百度百科】紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹，是在計算機科學中用到的一種資料結構，典型的用途是實作關聯數組。
它是在1972年由Rudolf Bayer發明的，當時被稱為平衡二叉B樹（symmetric binary B-trees）。後來，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的“紅黑樹”。
紅黑樹和AVL樹類似，都是在進行插入和删除操作時通過特定操作保持二叉查找樹的平衡，進而獲得較高的查找性能。
它雖然是複雜的，但它的最壞情況運作時間也是非常良好的，并且在實踐中是高效的： 它可以在O(log n)時間内做查找，插入和删除，這裡的n 是樹中元素的數目。
二、紅黑樹的特點
- 每個結點要麼是紅的要麼是黑的。（紅或黑）
- 根結點是黑的。（根黑）
- 每個葉結點（葉結點即指樹尾端NIL指針或NULL結點）都是黑的。 （葉黑）
- 如果一個結點是紅的，那麼它的兩個兒子都是黑的，不存在兩個連續的紅色節點。（紅子黑）
- 對于任意結點而言，其到葉結點樹尾端NIL指針的每條路徑都包含相同數目的黑結點。（路徑下黑相同）
這五條性質限制了紅黑樹，才能保證紅黑樹的自平衡，最長路徑不超過最短路徑的兩倍。可以通過數學證明來證明，紅黑樹可以将查找删除維持在對數時間内。
當我們進行插入或者删除操作時，就會對平衡造成破壞，這時候需要對樹進行調整，進而重新達到平衡。所作的一切操作都是為了調整樹使之符合這五條性質。
三、紅黑樹的操作方式
繼續來深刻了解，這個很重要，在插入和删除時，紅黑樹的結構可能會出現不平衡的情況，此時，紅-黑樹主要通過三種方式對平衡進行修正，改變節點顔色、左旋和右旋。
本文不對具體的插入和删除步驟進行推導了，因為這樣的文章很多，我們隻講原理，這樣可能會更有意思一點。
四、紅黑樹的應用
紅黑樹的應用比較廣泛，主要是用它來存儲有序的資料，效率非常之高。
紅黑樹的查找、插入和删除時間複雜度都為O(log2N)，額外的開銷是每個節點的存儲空間都稍微增加了一點，因為一個存儲紅黑樹節點的顔色變量。插入和删除的時間要增加一個常數因子，因為要進行旋轉，平均一次插入大約需要一次旋轉，是以插入的時間複雜度還是O(log2N),(時間複雜度的計算要省略常數)，但實際上比普通的二叉樹是要慢的。
大多數應用中，查找的次數比插入和删除的次數多，是以應用紅黑樹取代普通的二叉搜尋樹總體上不會有太多的時間開銷。而且紅黑樹的優點是對于有序資料的操作不會慢到O(N)的時間複雜度。
例如，Java集合中的TreeSet和TreeMap以及JDK1.8以後的HashMap在當個節點中連結清單長度大于8時都會用到。C++ STL中的set、map，以及Linux虛拟記憶體的管理，都是通過紅黑樹去實作的。
五、總結
- 紅黑樹的實作其實是一個2、3、4樹，隻是将雙節點或者三節點用紅色進行了标示，如果你将紅色節點放到和它父元素相同的高度，并把它和父元素看做是一個元素，你就會發現，變成了一個高度為lgN的二叉樹，這個2.3.4樹對紅黑樹很有啟發意義。
- 上面的步驟其實可以不用死記硬背，是可以推導出來的，因為我們是把一個平衡但通過插入或者删除破壞了平衡的紅黑樹再次平衡，同過旋轉讓位，改變紅黑顔色，使之符合那五條基本性質。比如遇到删除操作情況四的時候，我們可以把那個删除元素去除，發現左邊比右邊少一個黑元素，這個時候，怎麼辦，我們發現兄弟節點的子元素有一個紅元素，操作這個不會影響那五條性質，是以我們通過變換顔色，旋轉，即可讓左右兩邊的的黑色數目一樣。
- 旋轉操作的目的是出讓一個元素到另外的地方并且符合二叉樹左小右大的性質，交換顔色的目的是為了保持紅黑樹的那五條性質。
- 要時刻記得 ，一切的操作都是為了保持那五條性質。
- 一定要嘗試着自己推導一下插入删除規則，不然經常忘，是睡一覺起來再看就有點懵逼的那種忘。
- https://www.h3399.cn/201809/619925.html