紅黑樹（R-B樹，對稱二叉B樹）

1.概念

（1）它是一棵BST樹

（2）節點是紅色或黑色的（或者0,1）

（3）根是黑色（黑色代表穩定，如果一棵樹根都不穩了，就很容易倒掉了）

（4）所有葉子都是黑色（這裡的葉子節點指的是空節點）

（5）每個紅色節點必須有兩個黑色的子節點（紅色節點之間一定不能相連）

（6）從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點（13到6的葉子包含一個黑色節點，13到22的葉子包含一個黑色節點）

紅節點是一種不穩定的節點，在紅節點下面插入節點，一定會造成紅黑樹的失衡，俗稱“一點就炸”，在黑節點下面插入節點，依然可以保持平衡。