1、紅黑樹是什麼？紅黑樹（英語：Red–black tree）是一種自平衡二叉查找樹，是在計算機科學中用到的一種資料結構，典型的用途是實作關聯數組。它是在1972年由魯道夫·貝爾發明的，他稱之為"對稱二叉B樹"，它現代的名字是在Leo J. Guibas和Robert Sedgewick于1978年寫的一篇論文中獲得的。它是複雜的，但它的操作有着良好的最壞情況運作時間，并且在實踐中是高效的：它可以在{\displaystyle {\text{O}}(\log n)}時間内做查找，插入和删除，這裡的{\displaystyle n}
是樹中元素的數目。紅黑樹相對于AVL樹來說，犧牲了部分平衡性以換取插入/删除操作時少量的旋轉操作，整體來說性能要優于AVL樹。紅黑樹是每個節點都帶有顔色屬性的二叉查找樹，顔色為紅色或黑色。
##################################################
###################################################################################################
###################################################################################################
###########################################################################################
2、紅黑樹性質：
（1）每個結點要麼是紅的要麼是黑的。
（2）根結點是黑的。
（3）每個葉結點（葉結點即指樹尾端NIL指針或NULL結點）都是黑的。
（4）如果一個結點是紅的，那麼它的兩個兒子都是黑的。 從每個根到節點的路徑上不會有兩個連續的紅色節點，但黑色節點是可以連續的。
（5）對于任意結點而言，其到葉結點樹尾端NIL指針的每條路徑都包含相同數目的黑結點。
總結：首先全局地看這棵樹是不是隻有紅黑兩種顔色；然後看這棵樹的首尾是否全部都是黑色；再看所有的紅色節點的左右子節點是否全是黑色；最後看任何節點到葉節點的所有路徑是否包含相同數量的黑色節點。
3、為什麼從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長？這些性質確定了紅黑樹的關鍵特性，結果是這個樹大緻上是平衡的。因為操作比如插入、删除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。為什麼這些性質確定了這個結果？注意到性質4導緻了路徑不能有兩個毗連的紅色節點就足夠了。最短的可能路徑都是黑色節點，最長的可能路徑有交替的紅色和黑色節點。因為根據性質5所有最長的路徑都有相同數目的黑色節點，這就表明了沒有路徑能多于任何其他路徑的兩倍長。那麼對于從一個節點到其葉子節點的一條最長的路徑一定是紅黑交錯的，那麼最短路徑一定是純黑色的節點。
4、為什麼使用"nil葉子"或"空（null）葉子"？在很多樹資料結構的表示中，一個節點有可能隻有一個子節點，而葉子節點包含資料。用這種範例表示紅黑樹是可能的，但是這會改變一些性質并使算法複雜。為此，本文中我們使用"nil葉子"或"空（null）葉子"。這些節點在繪圖中經常被省略，導緻了這些樹好像同上述原則相沖突，而實際上不是這樣。與此有關的結論是所有節點都有兩個子節點，盡管其中的一個或兩個可能是空葉子。顯然這裡的葉子節點不是平常我們所說的葉子節點，如圖示有NIL的為葉子節點，為什麼不按正常出牌，因為按一般的葉子節點也行，但會使算法更複雜；
5、一棵含有x個節點的紅黑樹的高度f(x)滿足不等關系：f(x) <= 2log(x+1)。
下面通過"數學歸納法"開始論證高度為h的紅黑樹，它的包含的内節點個數至少為 2bh(x)-1個"。
(01) 當樹的高度h=0時，
内節點個數是0，bh(x) 為0，2bh(x)-1 也為 0。顯然，原命題成立。
(02) 當h>0，且樹的高度為 h-1 時，它包含的節點個數至少為 2bh(x)-1-1。這個是根據(01)推斷出來的！
下面，由樹的高度為 h-1 的已知條件推出“樹的高度為 h 時，它所包含的節點樹為 2bh(x)-1”。
當樹的高度為 h 時，對于節點x(x為根節點)，其黑高度為bh(x)。 對于節點x的左右子樹，它們黑高度為 bh(x) 或者 bh(x)-1。
根據(02)的已知條件，我們已知 "x的左右子樹，即高度為 h-1 的節點，它包含的節點至少為 2bh(x)-1-1 個"；
是以，節點x所包含的節點至少為 ( 2bh(x)-1-1 ) + ( 2bh(x)-1-1 ) + 1 = 2^bh(x)-1。即節點x所包含的節點至少為 2bh(x)-1。
是以，原命題成立。
由(01)、(02)得出，"高度為h的紅黑樹，它的包含的内節點個數至少為 2^bh(x)-1個"。
是以，“一棵含有n個節點的紅黑樹的高度至多為2log(n+1)”。
6、判斷紅黑樹。概念與性質總是抽象的，那麼如何加深印象呢？那就是給出各種樹，讓你來判斷這些樹是不是紅黑樹。不滿足紅黑樹的任意一條規則就可以判斷它不是紅黑樹，而判斷是紅黑樹則需要滿足所有紅黑樹性質才能判斷它是紅黑樹。