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

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

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

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

什么樣的數(shù)據(jù)結(jié)構(gòu)稱為紅黑樹

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

性質(zhì)：

每個(gè)節(jié)點(diǎn)是紅色或者黑色；

根節(jié)點(diǎn)是黑色；

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

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

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

延伸閱讀：

二、什么是平衡二叉樹

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

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