紅黑樹（red black tree） 是一種自平衡二叉查找樹，是在計算機科學中用到的一種資料結構，典型的用途是實作關聯數組。它是在1972年由rudolf bayer發明的，當時被稱為平衡二叉b樹（symmetric binary b-trees）。紅黑樹和avl樹類似，都是在進行插入和删除操作時通過特定操作保持二叉查找樹的平衡，進而獲得較高的查找性能。
二叉查找樹（binary search tree，簡稱bst）是一棵二叉樹，它的左子節點的值比父節點的值要小，右節點的值要比父節點的值大。它的高度決定了它的查找效率。
在理想的情況下，二叉查找樹增删查改的時間複雜度為o(logn)（其中n為節點數），最壞的情況下為o(n)。當它的高度為logn+1時，我們就說二叉查找樹是平衡的。
常見的bst:
說明：當bst查找的時候，先與目前節點進行比較，直到目前節點指針為空或者查找到對應的節點，程式查找結束。
如果相等的話就傳回目前節點；
如果少于目前節點則繼續查找目前節點的左節點；
如果大于目前節點則繼續查找目前節點的右節點。
插入操作先通過循環查找到待插入的節點的父節點，和查找父節點的邏輯一樣，都是比大小，小的往左，大的往右。找到父節點後，對比父節點，小的就插入到父節點的左節點，大就插入到父節點的右節點上。
删除操作的步驟如下：
查找到要删除的節點。
如果待删除的節點是葉子節點，則直接删除。
如果待删除的節點不是葉子節點，則先找到待删除節點的中序周遊的後繼節點，用該後繼節點的值替換待删除的節點的值，然後删除後繼節點。
bst存在的主要問題是，數在插入的時候會導緻樹傾斜，不同的插入順序會導緻樹的高度不一樣，而樹的高度直接的影響了樹的查找效率。理想的高度是logn，最壞的情況是所有的節點都在一條斜線上，這樣的樹的高度為n。
基于bst存在的問題，一種新的樹——平衡二叉查找樹(balanced bst)産生了。平衡樹在插入和删除的時候，會通過旋轉操作将高度保持在logn。其中兩款具有代表性的平衡樹分别為avl樹和紅黑樹。avl樹由于實作比較複雜，而且插入和删除性能差，在實際環境下的應用不如紅黑樹。
紅黑樹（red-black tree，以下簡稱rbtree）的實際應用非常廣泛，比如linux核心中的完全公平排程器、高精度計時器、ext3檔案系統等等，各種語言的函數庫如java的treemap和treeset，c++ stl的map、multimap、multiset等。
rbtree也是函數式語言中最常用的持久資料結構之一，在計算幾何中也有重要作用。值得一提的是，java 8中hashmap的實作也因為用rbtree取代連結清單，性能有所提升。
rbtree的定義如下:
任何一個節點都有顔色，黑色或者紅色
根節點是黑色的
父子節點之間不能出現兩個連續的紅節點
任何一個節點向下周遊到其子孫的葉子節點，所經過的黑節點個數必須相等
空節點被認為是黑色的
用資料結構表示如下：
rbtree在理論上還是一棵bst樹，但是它在對bst的插入和删除操作時會維持樹的平衡，即保證樹的高度在[logn,logn+1]（理論上，極端的情況下可以出現rbtree的高度達到2*logn，但實際上很難遇到）。這樣rbtree的查找時間複雜度始終保持在o(logn)進而接近于理想的bst。rbtree的删除和插入操作的時間複雜度也是o(logn)。rbtree的查找操作就是bst的查找操作。
旋轉操作(rotate)的目的是使節點顔色符合定義，讓rbtree的高度達到平衡。
rotate分為left-rotate（左旋）和right-rotate（右旋），區分左旋和右旋的方法是：待旋轉的節點從左邊上升到父節點就是右旋，待旋轉的節點從右邊上升到父節點就是左旋。
rbtree的查找操作和bst的查找操作是一樣的。
rbtree的插入與bst的插入方式是一緻的，隻不過是在插入過後，可能會導緻樹的不平衡，這時就需要對樹進行旋轉操作和顔色修複（在這裡簡稱插入修複），使得它符合rbtree的定義。
新插入的節點是紅色的，插入修複操作如果遇到父節點的顔色為黑則修複操作結束。也就是說，隻有在父節點為紅色節點的時候是需要插入修複操作的。
插入修複操作分為以下的三種情況，而且新插入的節點的父節點都是紅色的：
叔叔節點也為紅色。
叔叔節點為空，且祖父節點、父節點和新節點處于一條斜線上。
叔叔節點為空，且祖父節點、父節點和新節點不處于一條斜線上。
case 1的操作是将父節點和叔叔節點與祖父節點的顔色互換，這樣就符合了rbtree的定義。即維持了高度的平衡，修複後顔色也符合rbtree定義的第三條和第四條。下圖中，操作完成後a節點變成了新的節點。如果a節點的父節點不是黑色的話，則繼續做修複操作。
case 2的操作是将b節點進行右旋操作，并且和父節點a互換顔色。通過該修複操作rbtree的高度和顔色都符合紅黑樹的定義。如果b和c節點都是右節點的話，隻要将操作變成左旋就可以了。
case 3的操作是将c節點進行左旋，這樣就從case 3轉換成case 2了，然後針對case 2進行操作處理就行了。case 2操作做了一個右旋操作和顔色互換來達到目的。如果樹的結構是下圖的鏡像結構，則隻需要将對應的左旋變成右旋，右旋變成左旋即可。
插入後的修複操作是一個向root節點回溯的操作，一旦牽涉的節點都符合了紅黑樹的定義，修複操作結束。之是以會向上回溯是由于case 1操作會将父節點，叔叔節點和祖父節點進行換顔色，有可能會導緻祖父節點不平衡(紅黑樹定義3)。這個時候需要對祖父節點為起點進行調節（向上回溯）。
祖父節點調節後如果還是遇到它的祖父顔色問題，操作就會繼續向上回溯，直到root節點為止，根據定義root節點永遠是黑色的。在向上的追溯的過程中，針對插入的3中情況進行調節。直到符合紅黑樹的定義為止。直到牽涉的節點都符合了紅黑樹的定義，修複操作結束。
删除操作首先需要做的也是bst的删除操作，删除操作會删除對應的節點，如果是葉子節點就直接删除，如果是非葉子節點，會用對應的中序周遊的後繼節點來頂替要删除節點的位置。删除後就需要做删除修複操作，使的樹符合紅黑樹的定義，符合定義的紅黑樹高度是平衡的。
删除修複操作在遇到被删除的節點是紅色節點或者到達root節點時，修複操作完畢。
删除修複操作是針對删除黑色節點才有的，當黑色節點被删除後會讓整個樹不符合rbtree的定義的第四條。需要做的處理是從兄弟節點上借調黑色的節點過來，如果兄弟節點沒有黑節點可以借調的話，就隻能往上追溯，将每一級的黑節點數減去一個，使得整棵樹符合紅黑樹的定義。
删除操作的總體思想是從兄弟節點借調黑色節點使樹保持局部的平衡，如果局部的平衡達到了，就看整體的樹是否是平衡的，如果不平衡就接着向上追溯調整。
删除修複操作分為四種情況(删除黑節點後)：
待删除的節點的兄弟節點是紅色的節點。
待删除的節點的兄弟節點是黑色的節點，且兄弟節點的子節點都是黑色的。
待調整的節點的兄弟節點是黑色的節點，且兄弟節點的左子節點是紅色的，右節點是黑色的(兄弟節點在右邊)，如果兄弟節點在左邊的話，就是兄弟節點的右子節點是紅色的，左節點是黑色的。
待調整的節點的兄弟節點是黑色的節點，且右子節點是是紅色的(兄弟節點在右邊)，如果兄弟節點在左邊，則就是對應的就是左節點是紅色的。
由于兄弟節點是紅色節點的時候，無法借調黑節點，是以需要将兄弟節點提升到父節點，由于兄弟節點是紅色的，根據rbtree的定義，兄弟節點的子節點是黑色的，就可以從它的子節點借調了。
case 1這樣轉換之後就會變成後面的case 2，case 3，或者case 4進行處理了。上升操作需要對c做一個左旋操作，如果是鏡像結構的樹隻需要做對應的右旋操作即可。
之是以要做case 1操作是因為兄弟節點是紅色的，無法借到一個黑節點來填補删除的黑節點。
case 2的删除操作是由于兄弟節點可以消除一個黑色節點，因為兄弟節點和兄弟節點的子節點都是黑色的，是以可以将兄弟節點變紅，這樣就可以保證樹的局部的顔色符合定義了。這個時候需要将父節點a變成新的節點，繼續向上調整，直到整顆樹的顔色符合rbtree的定義為止。
case 2這種情況下之是以要将兄弟節點變紅，是因為如果把兄弟節點借調過來，會導緻兄弟的結構不符合rbtree的定義，這樣的情況下隻能是将兄弟節點也變成紅色來達到顔色的平衡。當将兄弟節點也變紅之後，達到了局部的平衡了，但是對于祖父節點來說是不符合定義4的。這樣就需要回溯到父節點，接着進行修複操作。
case 3的删除操作是一個中間步驟，它的目的是将左邊的紅色節點借調過來，這樣就可以轉換成case 4狀态了，在case 4狀态下可以将d，e節點都階段過來，通過将兩個節點變成黑色來保證紅黑樹的整體平衡。
之是以說case-3是一個中間狀态，是因為根據紅黑樹的定義來說，下圖并不是平衡的，他是通過case 2操作完後向上回溯出現的狀态。之是以會出現case 3和後面的case 4的情況，是因為可以通過借用侄子節點的紅色，變成黑色來符合紅黑樹定義4.
case 4的操作是真正的節點借調操作，通過将兄弟節點以及兄弟節點的右節點借調過來，并将兄弟節點的右子節點變成紅色來達到借調兩個黑節點的目的，這樣的話，整棵樹還是符合rbtree的定義的。
case 4這種情況的發生隻有在待删除的節點的兄弟節點為黑，且子節點不全部為黑，才有可能借調到兩個節點來做黑節點使用，進而保持整棵樹都符合紅黑樹的定義。
紅黑樹的删除操作是最複雜的操作，複雜的地方就在于當删除了黑色節點的時候，如何從兄弟節點去借調節點，以保證樹的顔色符合定義。由于紅色的兄弟節點是沒法借調出黑節點的，這樣隻能通過選擇操作讓他上升到父節點，而由于它是紅節點，是以它的子節點就是黑的，可以借調。
對于兄弟節點是黑色節點的可以分成3種情況來處理，當是以的兄弟節點的子節點都是黑色節點時，可以直接将兄弟節點變紅，這樣局部的紅黑樹顔色是符合定義的。但是整顆樹不一定是符合紅黑樹定義的，需要往上追溯繼續調整。
對于兄弟節點的子節點為左紅右黑或者 (全部為紅，右紅左黑)這兩種情況，可以先将前面的情況通過選擇轉換為後一種情況，在後一種情況下，因為兄弟節點為黑，兄弟節點的右節點為紅，可以借調出兩個節點出來做黑節點，這樣就可以保證删除了黑節點，整棵樹還是符合紅黑樹的定義的，因為黑色節點的個數沒有改變。
紅黑樹的删除操作是遇到删除的節點為紅色，或者追溯調整到了root節點，這時删除的修複操作完畢。
輸出的結果：
d(b)
b(b d le) g(r d ri)
a(r b le) e(b g le) h(b g ri)
f(r e ri)
括号左邊表示元素的内容。括号内的第一個元素表示顔色，b表示black，r表示red；第二個元素表示父元素的值；第三個元素表示左右，le表示在父元素的左邊。ri表示在父元素的右邊。
第一個元素d是root節點，由于它沒有父節點，是以括号内隻有一個元素。
作為平衡二叉查找樹裡面衆多的實作之一，紅黑樹無疑是最簡潔、實作最為簡單的。紅黑樹通過引入顔色的概念，通過顔色這個限制條件的使用來保持樹的高度平衡。作為平衡二叉查找樹，旋轉是一個必不可少的操作。通過旋轉可以降低樹的高度，在紅黑樹裡面還可以轉換顔色。
紅黑樹裡面的插入和删除的操作比較難了解，這時要注意記住一點：操作之前紅黑樹是平衡的，顔色是符合定義的。在操作的時候就需要向兄弟節點、父節點、侄子節點借調和互換顔色，要達到這個目的，就需要不斷的進行旋轉。是以紅黑樹的插入删除操作需要不停的旋轉，一旦借調了别的節點，删除和插入的節點就會達到局部的平衡（局部符合紅黑樹的定義），但是被借調的節點就不會平衡了，這時就需要以被借調的節點為起點繼續進行調整，直到整棵樹都是平衡的。在整個修複的過程中，插入具體的分為3種情況，删除分為4種情況。
整個紅黑樹的查找，插入和删除都是o(logn)的，原因就是整個紅黑樹的高度是logn，查找從根到葉，走過的路徑是樹的高度，删除和插入操作是從葉到根的，是以經過的路徑都是logn。