紅黑樹（Red Black Tree） 是壹種自平衡二叉查找樹，是在計算機科學中用到的壹種數據結構，典型的用途是實現關聯數組。
紅黑樹的原理是通過進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而實現關聯數組，存儲有序的數據。它是壹種自平衡二叉查找樹，是在計算機科學中用到的壹種數據結構，其典型的用途就是實現關聯數組。
紅黑樹是壹種特定類型的二叉樹，它是在計算機科學中用來組織數據比如數字的塊的壹種結構。若壹棵二叉查找樹是紅黑樹，則它的任壹子樹必為紅黑樹。
而由於每壹顆紅黑樹都是壹顆二叉排序樹，因此，在對紅黑樹進行查找時，可以采用運用於普通二叉排序樹上的查找算法，在查找過程中不需要顏色信息。
行為特征：
紅黑樹是每個節點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。在二叉查找樹強制壹般要求以外，對於任何有效的紅黑樹我們增加了如下的額外要求：
性質1、節點是紅色或黑色。
性質2、根節點是黑色。
性質3、所有葉子都是黑色。（葉子是NUIL節點）。
性質4、每個紅色節點的兩個子節點都是黑色。（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點）。
性質5、從任壹節點到其每個葉子的所有路徑都包含相同數目的黑色節點。