一、簡單介紹
紅黑樹是一種特定型別的二叉樹，它是在計算機科學中用來組織資料比如數字的塊的一種結構。若一棵二叉查詢樹是紅黑樹，則它的任一子樹必為紅黑樹。而由於每一顆紅黑樹都是一顆二叉排序樹，因此，在對紅黑樹進行查詢時，可以採用運用於普通二叉排序樹上的查詢演算法，在查詢過程中不需要顏色資訊。
二、行為特徵
紅黑樹是每個節點都帶有顏色屬性的二叉查詢樹，顏色或紅色或黑色。在二叉查詢樹強制一般要求以外，對於任何有效的紅黑樹我們增加了如下的額外要求:
性質1. 節點是紅色或黑色。
性質2. 根節點是黑色。
性質3.所有葉子都是黑色。（葉子是NUIL節點）
性質4. 每個紅色節點的兩個子節點都是黑色。（從每個葉子到根的所有路徑上不能有兩個連續的'紅色節點）
性質5.從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
三、紅黑樹和AVL樹
紅黑樹和AVL樹的區別在於它使用顏色來標識結點的高度，它所追求的是區域性平衡而不是AVL樹中的非常嚴格的平衡。學過資料結構的人應該都已經領教過AVL樹的複雜，但AVL樹的複雜比起紅黑樹來說簡直是小巫見大巫，紅黑樹才是真正的變態級資料結構。