簡介
紅黑樹是一種特定類型的二叉樹，它是在計算機科學中用來組織數據比如數字的塊的一種結構。
紅黑樹是一種平衡二叉查找樹的變體，它的左右子樹高差有可能大于 1，所以紅黑樹不是嚴格意義上的平衡二叉樹（AVL），但 對之進行平衡的代價較低， 其平均統計性能要強于 AVL 。
由于每一棵紅黑樹都是一顆二叉排序樹，因此，在對紅黑樹進行查找時，可以采用運用于普通二叉排序樹上的查找算法，在查找過程中不需要顔色信息。
數據結構
它的統計性能要好于平衡二叉樹(有些書籍根據作者姓名，Adelson-Velskii和Landis，将其稱為AVL-樹)，因此，紅黑樹在很多地方都有應用。在C++STL中，很多部分(包括set,multiset,map,multimap)應用了紅黑樹的變體(SGISTL中的紅黑樹有一些變化，這些修改提供了更好的性能，以及對set操作的支持)。其他平衡樹還有：AVL，SBT，伸展樹，TREAP等等。
樹的旋轉
當在對紅黑樹進行插入和删除等操作時，對樹做了修改，那麼可能會違背紅黑樹的性質。
為了保持紅黑樹的性質，可以通過對樹進行旋轉，即修改樹種某些結點的顔色及指針結構，以達到對紅黑樹進行插入、删除結點等操作時，紅黑樹依然能保持它特有的性質（五點性質）。
性質
紅黑樹是每個節點都帶有顔色屬性的二叉查找樹，顔色或紅色或黑色。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:性質1.節點是紅色或黑色性質2.根節點是黑色。性質3每個葉節點（NIL節點，空節點）是黑色的。性質4每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)。性質5.從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
這些約束強制了紅黑樹的關鍵性質:從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結果是這個樹大緻上是平衡的。因為操作比如插入、删除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。
要知道為什麼這些特性确保了這個結果，注意到性質4導緻了路徑不能有兩個毗連的紅色節點就足夠了。最短的可能路徑都是黑色節點，最長的可能路徑有交替的紅色和黑色節點。因為根據性質5所有最長的路徑都有相同數目的黑色節點，這就表明了沒有路徑能多于任何其他路徑的兩倍長。
在很多樹數據結構的表示中，一個節點有可能隻有一個子節點，而葉子節點不包含數據。用這種範例表示紅黑樹是可能的，但是這會改變一些屬性并使算法複雜。為此，本文中我們使用"nil葉子"或"空(null)葉子"，如上圖所示，它不包含數據而隻充當樹在此結束的指示。這些節點在繪圖中經常被省略，導緻了這些樹好象同上述原則相矛盾，而實際上不是這樣。與此有關的結論是所有節點都有兩個子節點，盡管其中的一個或兩個可能是空葉子。
術語
紅黑樹是一種特定類型的二叉樹，它是在計算機科學中用來組織數據比如數字的塊的一種結構。所有數據塊都存儲在節點中。這些節點中的某一個節點總是擔當起始位置的功能，它不是任何節點的兒子，我們稱之為根節點或根。它有最多兩個"兒子"，都是它連接到的其他節點。所有這些兒子都可以有自己的兒子，以此類推。這樣根節點就有了把它連接到在樹中任何其他節點的路徑。
如果一個節點沒有兒子，我們稱之為葉子節點，因為在直覺上它是在樹的邊緣上。子樹是從特定節點可以延伸到的樹的某一部分，其自身被當作一個樹。在紅黑樹中，葉子被假定為null或空。
由于紅黑樹也是二叉查找樹，它們當中每一個節點的比較值都必須大于或等于在它的左子樹中的所有節點，并且小于或等于在它的右子樹中的所有節點。這确保紅黑樹運作時能夠快速的在樹中查找給定的值。
用途
紅黑樹和AVL樹一樣都對插入時間、删除時間和查找時間提供了最好可能的最壞情況擔保。這不隻是使它們在時間敏感的應用如即時應用(real time application)中有價值，而且使它們有在提供最壞情況擔保的其他數據結構中作為建造闆塊的價值；例如，在計算幾何中使用的很多數據結構都可以基于紅黑樹。
紅黑樹在函數式編程中也特别有用，在這裡它們是最常用的持久數據結構之一，它們用來構造關聯數組和集合，在突變之後它們能保持為以前的版本。除了O(logn)的時間之外，紅黑樹的持久版本對每次插入或删除需要O(logn)的空間。
紅黑樹是2-3-4樹的一種等同。換句話說，對于每個2-3-4樹，都存在至少一個數據元素是同樣次序的紅黑樹。在2-3-4樹上的插入和删除操作也等同于在紅黑樹中顔色翻轉和旋轉。這使得2-3-4樹成為理解紅黑樹背後的邏輯的重要工具，這也是很多介紹算法的教科書在紅黑樹之前介紹2-3-4樹的原因，盡管2-3-4樹在實踐中不經常使用。
操作
在紅黑樹上隻讀操作不需要對用于二叉查找樹的操作做出修改，因為它也是二叉查找樹。但是，在插入和删除之後，紅黑屬性可能變得違規。恢複紅黑屬性需要少量(O(log n))的顔色變更(這在實踐中是非常快速的)并且不超過三次樹旋轉(對于插入是兩次)。這允許插入和删除保持為O(log n)次，但是它導緻了非常複雜的操作。
數據結構簡述
它的統計性能要好于平衡二叉樹（有些書籍根據作者姓名，Adelson-Velskii和Landis，将其稱為AVL-樹），因此，紅黑樹在很多地方都有應用。目前，基于擁有上述特性，紅黑樹已廣泛應用Linux 的進程管理、内存管理，設備驅動及虛拟内存跟蹤等一系列場景中。其他平衡樹還有：AVL，SBT，伸展樹，TREAP等等。
