一、紅黑樹與普通的平衡二叉樹的區(qū)別
1、平衡二叉樹通過(guò)保持任一節(jié)點(diǎn)左、右子樹高度差的絕對(duì)值不超過(guò)1來(lái)維持二叉樹的平衡;而紅黑樹是根據(jù)查找路徑上黑色節(jié)點(diǎn)的個(gè)數(shù)以及紅、黑節(jié)點(diǎn)之間的聯(lián)系來(lái)維持二叉樹的平衡。
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)致在頻繁的插入、修改中造成的效率問(wèn)題;紅黑樹在執(zhí)行插入修改的操作時(shí)會(huì)發(fā)生旋轉(zhuǎn)與變色(紅變黑,或者黑變紅)以確保沒(méi)有一條路徑會(huì)比其它路徑長(zhǎng)出兩倍。
3、總體來(lái)說(shuō),在插入或者刪除節(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ì)值不超過(guò)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ì)值不超過(guò)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ù)量較小,看不出與平衡二叉樹的明顯差別)。