紅黑樹是一種自平衡二叉查找樹。它是在1972年由Rudolf Bayer發明的，當時被稱為平衡二叉B樹（symmetric binary B-trees），在1978年被Leo J. Guibas和Robert Sedgewick改稱為“紅黑樹”。
紅黑樹的特點如下：每個節點非紅即黑。黑色決定平衡，紅色不決定平衡。這對應了2至3樹中一個節點內可以存放1至2個節點。根節點總是黑色的。每個葉子節點都是黑色的空節點（NIL節點）。這里指的是紅黑樹都會有一個空的葉子節點，是紅黑樹自己的規則。如果節點是紅色的，則它的子節點必須是黑色的（反之不一定）。通常這條規則也叫不會有連續的紅色節點。一個節點最多臨時會有3個節點，中間是黑色節點，左右是紅色節點。從根節點到葉節點或空子節點的每條路徑，必須包含相同數目的黑色節點（即相同的黑色高度）。每一層都只是有一個節點貢獻了樹高決定平衡性，也就是對應紅黑樹中的黑色節點。
在Java集合框架中，很多部分（HashMap，TreeMap，TreeSet 等）都有紅黑樹的應用。
數據結構
它的統計性能要好于平衡二叉樹(有些書籍根據作者姓名，Adelson-Velskii和Landis，將其稱為AVL-樹)，因此，紅黑樹在很多地方都有應用。在C++ STL中，很多部分(包括set, multiset,map, multimap)應用了紅黑樹的變體(SGI STL中的紅黑樹有一些變化，這些修改提供了更好的性能，以及對set操作的支持)。其他平衡樹還有：AVL，SBT，伸展樹，TREAP 等等。
樹的旋轉
當我們在對紅黑樹進行插入和刪除等操作時，對樹做了修改，那么可能會違背紅黑樹的性質。
為了保持紅黑樹的性質，我們可以通過對樹進行旋轉，即修改樹中某些結點的顏色及指針結構，以達到對紅黑樹進行插入、刪除結點等操作時，紅黑樹依然能保持它特有的性質（五點性質）。
1.結點插入算法
插入過程首先是根據一般二叉查找樹的插入步驟，把新結點 插入到 某個葉結點的位置上，然后將 z 著 為紅色。為了保證紅黑樹的性質能繼續保 持，再對有關結點重點著色并旋轉，其插入算法如下：
RB-INSERT (T,z) {
1 按二叉查找樹的插入步驟將結點 z 插入到 T 中；
2 color[z]=紅色；
3 while(z 不是根結點 &&color[z->parent]= =RED) {Insert-Fixup(T,z);}
對上述算法分析，如果新插入的是黑色結點，那么它所在的路徑上就多出一個黑色的結點，所以新插入的結點一定要設成紅 色。但是如果 z 的父結點也是紅色，這就違反了每個紅色結點的兩個子結點都黑色的性質。
2.結點刪除算法
與紅黑樹的的插入算法一樣，對一個結點的刪除算法要花 O(log n)時間，只是刪 除算法略微復雜些，刪除算法如下：
RB-DELETE(T,z) {
1 if (z 的左右子結點均為NIL)
2 { NIL 結點代替 z 的位置； delete(z); }
3 else if (z 有一個子結點為 NIL)
4 {z 的非 NIL 子結點代替 z 的位置；delete(z); }
5 else
6 {將紅黑樹中序遍歷中 z 的后繼結點 s 的值賦給 z; delete(s); }
7 if (刪除的結點是黑色的) Delete-Fixup(T,x); /*x 指向代替刪除結點的結點 */ }
對以上算法分析，若刪除的結點是紅色，則不做任何操作，紅黑樹的任何屬性都不會被破壞；若刪除的結點是黑色的，顯然它所 在的路徑上就少一個黑色結點，紅黑樹的性質就被破壞了，這時執行一個 Delete-Fixup（）來修補這棵樹。一個結點被刪除之后，一定 有一個它的結點代替了它的位置，即使是葉結點被刪除后，也會有一個空結點來代替它的位置。設指針 x 指向這個代替位置的結點，同時引入指向 x 兄弟的指針 w，這里均假設 x 是 x->parent 的左子結點，則 w 是 x->parent 的右子結點，如果實際遇到相反的情 況，只要把所有操作中的左、右 互反一下就可以了。
性質
紅黑樹是每個節點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求：
性質1. 節點是紅色或黑色。
性質2. 根節點是黑色。
性質3. 每個葉節點（NIL節點，空節點）是黑色的。
性質4. 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
性質5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
這些約束強制了紅黑樹的關鍵性質：從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。
要知道為什么這些特性確保了這個結果，注意到性質4導致了路徑不能有兩個毗連的紅色節點就足夠了。最短的可能路徑都是黑色節點，最長的可能路徑有交替的紅色和黑色節點。因為根據性質5所有最長的路徑都有相同數目的黑色節點，這就表明了沒有路徑能多于任何其他路徑的兩倍長。
在很多樹數據結構的表示中，一個節點有可能只有一個子節點，而葉子節點不包含數據。用這種范例表示紅黑樹是可能的，但是這會改變一些屬性并使算法復雜。為此，本文中我們使用 "nil 葉子" 或"空(null)葉子"，它不包含數據而只充當樹在此結束的指示。這些節點在繪圖中經常被省略，導致了這些樹好象同上述原則相矛盾，而實際上不是這樣。與此有關的結論是所有節點都有兩個子節點，盡管其中的一個或兩個可能是空葉子。
術語
紅黑樹是一種特定類型的二叉樹，它是在計算機科學中用來組織數據比如數字的塊的一種結構。所有數據塊都存儲在節點中。這些節點中的某一個節點總是擔當起始位置的功能，它不是任何節點的兒子，我們稱之為根節點或根。它有最多兩個"兒子"，都是它連接到的其他節點。所有這些兒子都可以有自己的兒子，以此類推。這樣根節點就有了把它連接到在樹中任何其他節點的路徑。
如果一個節點沒有兒子，我們稱之為葉子節點，因為在直覺上它是在樹的邊緣上。子樹是從特定節點可以延伸到的樹的某一部分，其自身被當作一個樹。在紅黑樹中，葉子被假定為 null 或空。
由于紅黑樹也是二叉查找樹，它們當中每一個節點的比較值都必須大于或等于在它的左子樹中的所有節點，并且小于或等于在它的右子樹中的所有節點。這確保紅黑樹運作時能夠快速的在樹中查找給定的值。
用途
1.Linux非實時任務調度中的應用
Linux 的穩定內核版本在 2． 6． 24 之后，使用了新的調度程序 CFS，所有非實時可運行進程都以虛擬運行時間為 key 值掛在一棵紅黑樹上。以完成更公平高效地調度所有任務。CFS 棄用 active /expired 數組和動態計算優先級，不再跟蹤任務的睡眠時間和區別是否交互任務，并且在調度中采用基于時間計算鍵值的紅黑樹來選取下一個任務，根據所有任務占用 CPU 時間的狀態來確定調度任務優先級。
32 位 Linux 內核虛擬地址空間劃分 0 － 3G 為用戶空間，3 － 4G 內核空間，因此每個進程可以使用 4GB的虛擬空間。同時，Linux 定義了虛擬存儲區域( VMA) 以便于更好地表示進程所使用的虛擬空間。每個 VMA是某個進程的一段連續虛擬空間，其中的單元具有相同的特征，所有的虛擬區域按照地址排序由指針鏈接為一個鏈表。當發生缺頁中斷時搜索 VMA 到指定區域時，則需要頻繁操作，因此選用了紅黑樹以減少查找時間。
3.檢測樹的平衡性上的應用
紅黑樹是一種自平衡二叉搜索樹，它的每個結點都被“著色”為紅色或者黑色，這些結點的顏色被用來檢測樹的平衡性。紅黑樹作為嵌入式數據庫中的索引機制，可以獲得更好的性能，對于SQLite數據庫，可以采用紅黑樹實現索引機制的優化。
操作
在紅黑樹上只讀操作不需要對用于二叉查找樹的操作做出修改，因為它也是二叉查找樹。但是，在插入和刪除之后，紅黑可能會變得變得違規。恢復紅黑屬性需要少量(O(log n))的顏色變更(這在實踐中是非常快速的)并且不超過三次樹旋轉(對于插入是兩次)。這允許插入和刪除保持為 O(log n) 次，但是它導致了非常復雜的操作。
參考資料 >
紅黑樹.JavaGuide.2024-01-20
深入理解紅黑樹.iangeli.com.2024-01-20