在了解紅黑樹之前，先要了解二叉查找數，又叫二叉樹。二叉樹顧名思義，是一種每個節點最多有兩個子節點都樹，同時遵循 左節點的值<父節點的值<右節點的值 這樣的規律，如下圖所示
它是一種查找次數小于等于樹高的資料結構。如圖中樹有4層，即樹高為4，當我們需要查找8時，經過的路線是這樣的：
1、8<9，往左查找
2、8>5，往右查找
3、8>7，往右查找
4、8=8，找到結果
總共查找4次，等于樹高。這棵樹不管怎麼找，查找次數總是小于等于樹高。
二叉樹的插入同樣遵循上述規則，會一步一步對比，進而找到插入的位置，可以想象上圖中的8不存在，而是需要插入一個8，結果與上述路線一緻。
二叉樹的删除會涉及到無子節點和有子節點兩種情況，無子節點直接删除即可，有子節點會需要用左邊最大值或右邊最小值替換目前删除節點，具體不細聊。
當二叉樹插入數值不均衡時，會出現樹結構的變形與查找性能的損耗，比如現在二叉樹有8，9，12三個值，然後需要插入7，6，5，4，3這五個值時，産生的結構如下圖所示。
樹高會不合理的增高，查找效率也無法得到保證。紅黑樹就是為了解決這種情況而誕生的。
紅黑樹又稱為自平衡二叉樹，它符合二叉樹的規則同時比它的規則更加的複雜，具體規則如下：
1、所有節點都是紅色或黑色
2、根節點為黑色
3、所有葉子都是黑色(NIL節點)
4、每個紅色節點必須有兩個黑色的子節點。（不能有兩個連續的紅色節點。）
5、從任一節點到其每個葉子的所有簡單路徑(不要回退)都包含相同數目的黑色節點。
具體樣子如下圖所示：
解釋一下幾個規則的含義：
1，2很好了解，節點都是紅和黑，根節點是黑色的。
3所有葉子都是黑色的，葉子與葉子節點是兩個概念，葉子不是一個節點，可以了解為沒有數值的空節點，也就是圖中的NIL。
4也很好了解，紅色節點的子節點都是黑色的，這就保證了沒有兩個連續的紅色節點。
5稍微解釋一下，簡單路徑就是說一次到底，不要回退，葉子就是NIL，比如從8這個節點出發，不管是去1下面的葉子，11下面的葉子，還是6下面的葉子，都是經過一個黑色節點，從任何節點出發都是一樣的規則，經過相同數量的黑色節點。
以上5個規則，加上二叉樹的規則，就組成了紅黑樹這一極具特點的樹型資料結構。
紅黑樹的查找與二叉樹類似，都是查找次數小于等于樹高，但紅黑樹由于平衡的規則會使樹高相對平衡，不會出現某條路徑遠遠大于其他路徑的情況。
紅黑樹的插入較為複雜，有時為了維持規則需要做結構的調整，常用的調整手段是改變顔色、左旋轉和右旋轉。由于規則5，如果插入的值為黑色節點，會導緻黑色節點數量很難相同，是以預設每次插入的值都為紅色節點。和二叉樹一樣，通過對比找到插入的位置，預設插入一個紅色節點的數值，這裡會分為很多情況，大概列舉如下：
1、插入位置為根節點(第一個值)，紅色變成黑色即可。
2、插入位置父節點為黑色節點，直接插入一個紅色節點即可。此時1，2，3規則都不會違背，由于父節點為黑色，4也沒有違背。由于插入的是紅色節點，5也沒有違背，是以紅黑樹不需要做調整，直接插入即可。
3、插入位置父節點與父節點的同級節點(下稱叔父節點)均為紅色節點，需要改變父節點和叔父節點的顔色為黑色，同時将父節點的父節點(下稱祖父節點)改變為紅色。如果祖父節點為根節點或祖父節點的父節點也為紅色，需要進一步變化。可以了解為把祖父節點帶入這個方法邏輯中，類比為插入祖父節點，進而判斷祖父節點需要如何變化。
4、插入位置父節點為紅色，叔父節點為黑色或者空節點，同時新增節點是其父節點的右子節點而父節點又是其父節點的左子節點時，需要使用到左旋轉，如圖所示。N為插入的節點，P為它的父節點。左轉換逆時針旋轉P節點與它的兩個子節點，同時将N節點下的2節點給到P節點。兩個紅色一起違反規則4，可再将N節點變更為黑色。
5、插入位置父節點為紅色，叔父節點為黑色或者空節點，同時新增節點是其父節點的左子節點而父節點又是其父節點的左子節點時，需要使用到右旋轉，如圖所示。N為插入的節點，P為它的父節點，G為P的父節點。右轉換順時針旋轉N,P,G三個節點，同時将P節點下的3節點給到G節點。再改變P和G的顔色即可。
6、插入位置父節點是其父節點的右子節點時，與上述4，5情況完全相反，即隻要将4和5中的所有左換成右，所有右換成左，就是這種插入情況的處理方法。
紅黑樹的删除同樣複雜，删除的節點有各種各樣的情況，但我們可以統一類化為删除的節點隻有一個子節點的情況。如果删除的節點有兩個子節點，與二叉樹類似，紅黑樹也是需要找到左子樹中的最大值或右子樹中的最小值，将數值做替換，等于删除的是左子樹中的最大值或右子樹中的最小值，這個值一定不會有兩個子節點，而隻是數值的替換，顔色保持不變，是以不會破壞規則。如果删除的節點沒有子節點，可以将一個空節點當成它的子節點。是以我們隻需要考慮删除的節點隻有一個子節點的情況。
1、删除節點為紅色的情況。删除節點為紅色，根據規則4，它的兒子一定是黑色，此時隻要删除目前節點即可，它的兒子是黑色，是以不會破壞規則3和4，同時路徑中隻是缺少了一個紅色的節點，也不會破壞規則5.
2、删除的節點為黑色，它的兒子是紅色的情況。這種情況也很簡單，将目前節點删除，将它的兒子從紅色改變成黑色即可。
3、删除的節點為黑色，它的兒子也是黑色的情況。這種情況比較複雜，暫時不介紹了，可看維基百科對紅黑樹的介紹。
。