一、簡單介紹

　　紅黑樹是一種特定類型的二叉樹，它是在計算機科學中用來組織數據比如數字的塊的一種結構。若一棵二叉查找樹是紅黑樹，則它的任一子樹必為紅黑樹。而由于每一顆紅黑樹都是一顆二叉排序樹，因此，在對紅黑樹進行查找時，可以采用運用于普通二叉排序樹上的查找算法，在查找過程中不需要顏色信息。

　　二、行為特征

　　紅黑樹是每個節點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:

　　性質1. 節點是紅色或黑色。

　　性質2. 根節點是黑色。

　　性質3.所有葉子都是黑色。（葉子是NUIL節點）

　　性質4. 每個紅色節點的兩個子節點都是黑色。（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點）

　　性質5.從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

　　三、紅黑樹和AVL樹

　　紅黑樹和AVL樹的區別在于它使用顏色來標識結點的高度，它所追求的是局部平衡而不是AVL樹中的非常嚴格的平衡。學過數據結構的人應該都已經領教過AVL樹的復雜，但AVL樹的復雜比起紅黑樹來說簡直是小巫見大巫，紅黑樹才是真正的變態級數據結構。