一、紅黑樹與普通的平衡二叉樹的區(qū)別

1、平衡二叉樹通過保持任一節(jié)點左、右子樹高度差的絕對值不超過1來維持二叉樹的平衡；而紅黑樹是根據查找路徑上黑色節(jié)點的個數以及紅、黑節(jié)點之間的聯系來維持二叉樹的平衡。

2、平衡二叉樹在插入或者刪除節(jié)點時為了保證左右子樹的高度差會進行旋轉，這一個旋轉根據數據的不同旋轉的復雜度也會不一樣，所以在插入或者刪除平衡二叉樹的節(jié)點時，旋轉的次數不可知，這也導致在頻繁的插入、修改中造成的效率問題；紅黑樹在執(zhí)行插入修改的操作時會發(fā)生旋轉與變色（紅變黑，或者黑變紅）以確保沒有一條路徑會比其它路徑長出兩倍。

3、總體來說，在插入或者刪除節(jié)點時，紅黑樹旋轉的次數比平衡二叉樹少，因此在插入與刪除操作比較頻繁的情況下，選用紅黑樹。

什么樣的數據結構稱為紅黑樹

紅黑樹（Red Black Tree）是一種自平衡的二叉查找樹，它與平衡二叉樹相同的地方在于都是為了維護查找樹的平衡而構建的數據結構，它的主要特征是在二叉查找樹的每個節(jié)點上添加了一個屬性表示顏色，顏色有兩種，紅與黑。

性質：

每個節(jié)點是紅色或者黑色；

根節(jié)點是黑色；

所有葉子節(jié)點都是黑色（葉子是NIL節(jié)點，也稱為外節(jié)點）;

每個紅色節(jié)點的子節(jié)點都是黑色（從每個葉子節(jié)點到根節(jié)點的所有路徑上不能有兩個連續(xù)的紅色節(jié)點）；

從紅黑樹的任一節(jié)點到其每個葉子節(jié)點的所有路徑都包含相同數目的黑色節(jié)點（包含黑色節(jié)點的數目稱為該節(jié)點的黑高度）。

延伸閱讀：

二、什么是平衡二叉樹

平衡二叉樹（Balanced Binary Tree）的定義是這樣的——空樹，或者任一節(jié)點左、右子樹高度差的絕對值不超過1，稱為平衡二叉樹。

比如，我們將1,2,3,4,5,6,7,8這幾個節(jié)點以5,3,1,4,2,7,6,8的順序插入構造查找二叉樹，這棵樹就是一個平衡二叉樹，它的根節(jié)點高度為3，平均查找長度為(1*1+ 2*2 + 4*3 + 1*4)/8 = 2.625,，并且它的任一節(jié)點左、右子樹高度差的絕對值不超過1。而如果按照6,4,3,5,2,1,7,8的順序插入構造查找二叉樹，這棵樹也不能稱為平衡二叉樹，因為它的根節(jié)點的左子樹高度為4，而右子樹的高度為2，相差大于1；而對于4這一個節(jié)點，它的左子樹高度為3，右子樹的高度為1，相差也大于1。而這棵樹的平均查找長度為（1*1 + 2*2 + 3*3 + 4*1 + 5*1）/ 8 = 2.875（這里數據量較小，看不出與平衡二叉樹的明顯差別）。