平衡二叉樹,紅黑樹

1、紅黑樹和平衡二叉樹的主要區(qū)別如下： 平衡性的追求：- 紅黑樹：追求的是大致平衡，不嚴(yán)格要求每個節(jié)點(diǎn)的左右子樹高度差不超過1。紅黑樹通過顏色和一規(guī)則來保證樹的平衡性。- 平衡二叉樹：追求的是絕對平衡，要求每個節(jié)點(diǎn)的左右子樹高度差不超過1。

2、紅黑樹是一種自平衡二叉搜索樹，其性質(zhì)包括每個節(jié)點(diǎn)的顏色只能為紅色或黑色，根節(jié)點(diǎn)為黑色，每個葉子節(jié)點(diǎn)（NULL節(jié)點(diǎn)）均為黑色，對于每個節(jié)點(diǎn)，其子節(jié)點(diǎn)的紅色節(jié)點(diǎn)數(shù)量不超過一個，從任一節(jié)點(diǎn)到其每個葉子節(jié)點(diǎn)的所有路徑上黑節(jié)點(diǎn)數(shù)量相同，保證了樹的高度平衡。平衡二叉樹調(diào)節(jié)：通過旋轉(zhuǎn)操作調(diào)整樹的平衡。

3、平衡二叉樹追求絕對平衡，條件比較苛刻，實(shí)現(xiàn)起來比較麻煩，每次插入新節(jié)點(diǎn)之后需要旋轉(zhuǎn)的次數(shù)不能預(yù)知。紅黑樹：是一種自平衡二叉查找樹，是在計算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實(shí)現(xiàn)關(guān)聯(lián)數(shù)組。紅黑樹是在1972年被發(fā)明，當(dāng)時被稱為平衡二叉B樹。

紅黑樹介紹及旋轉(zhuǎn)詳解

1、紅黑樹的基本操作包括添加、刪除，而為了保證樹的平衡性，這兩個操作后都會用到旋轉(zhuǎn)方法。旋轉(zhuǎn)包括左旋和右旋，目的是讓樹保持紅黑樹的特性。左旋和右旋的偽代碼分別如下：左旋轉(zhuǎn)和右旋轉(zhuǎn)的動態(tài)圖與靜態(tài)圖分別展示了旋轉(zhuǎn)前后的狀態(tài)。

2、紅黑樹可以進(jìn)行旋轉(zhuǎn)、增加節(jié)點(diǎn)、刪除節(jié)點(diǎn)的功能。旋轉(zhuǎn)操作分為左旋和右旋。左旋指原父結(jié)點(diǎn)的右葉子節(jié)點(diǎn)成為新的父結(jié)點(diǎn)，而原父結(jié)點(diǎn)成為新父結(jié)點(diǎn)的左葉子節(jié)點(diǎn)。左旋時，因為節(jié)點(diǎn)之間指針發(fā)生了變動，原右葉子節(jié)點(diǎn)的左子樹的位置被原父結(jié)點(diǎn)占據(jù)，必須為它尋找一個新的父結(jié)點(diǎn)。

3、插入的是紅色（因為紅黑樹的性質(zhì)中有一條，根節(jié)點(diǎn)到任意葉子節(jié)點(diǎn)的黑色節(jié)點(diǎn)相同，插入紅色降低調(diào)整概率）①當(dāng)父節(jié)點(diǎn)是黑色，沒有問題，直接插入，不會破壞平衡。