柚子快報邀請碼778899分享：數(shù)據(jù)結構 二叉樹的分類

http://yzkb.51969.com/

二叉樹是最常見的樹，二叉樹的每個節(jié)點最多只有兩個子節(jié)點

二叉樹的分類

?完全二叉樹

?指二叉樹的所有節(jié)點按照從左往右填充

就像這樣：

?滿二叉樹

是一種完全二叉樹，當完全二叉樹每個層次都被填滿時，就是滿二叉樹

例如上圖中的最后一棵樹

堆?

堆是一種帶有特定排序的完全二叉樹，所有節(jié)點大于他的所有子節(jié)點（大根堆），所有節(jié)點小于他的所有子節(jié)點（小根堆）

二叉搜索樹

二叉搜索樹跟大/小根堆相似，堆只要求節(jié)點大于（小于）子節(jié)

而二叉搜索樹要求 左節(jié)點 > 節(jié)點 > 右節(jié)點

平衡二叉樹

平衡二叉樹是二叉搜索樹的一種改進形式，指將樹盡可能變“扁”，因為當用搜索樹搜索數(shù)字的時候，如果遇到十分不平衡（左/右子樹遠大于另一個）的樹的話，會出現(xiàn)查找的時間不理想的情況，所以需要讓左右子樹盡可能一樣高。

平衡二叉搜索樹

指將二叉搜索樹用平衡樹改進，讓二叉搜索樹在增刪查改時能讓左右子樹盡可能一樣高

AVL樹（自平衡二叉搜索樹）

自動版的平衡二叉樹，能夠在增加/刪除元素時，自動通過左旋，右旋，時他重新平衡

黑紅樹

大部分人這輩子都不會在工作中自己去實現(xiàn)一顆紅黑樹，因為其十分復雜，而且STL等庫中封裝了黑紅樹，所以只需要知道其原理即可。

黑紅樹并不嚴格平衡，他的左右子樹層數(shù)差距可能很大?，但是他仍然屬于平衡搜索二叉樹

在需要大量數(shù)據(jù)操作時，AVL樹的時間復雜度會非常高，而黑紅樹就是適用于大量查詢，插入，刪除的數(shù)據(jù)結構，相當于升級版AVL樹，在項目中常使用黑紅樹，用AVL樹很少，黑紅樹可以代替AVL樹

黑紅樹有以下幾條性質(zhì)：

---------------------------------------------------------------------------------------------------------------------------------

1.節(jié)點顏色：每個節(jié)點要么是紅色，要么是黑色。

2.根節(jié)點顏色：根節(jié)點是黑色。

3.葉子節(jié)點顏色：每個葉子節(jié)點（NIL節(jié)點，空節(jié)點）是黑色的。這里葉子節(jié)點指的是樹尾端空(NIL或NULL)的節(jié)點。

4.紅色節(jié)點：如果一個節(jié)點是紅色的，則它的兩個子節(jié)點都是黑色的，且從根節(jié)點到葉子節(jié)點的所有路徑上不能有 2 個連續(xù)的紅色節(jié)點

5.黑高平衡：從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點。這個特性確保了紅黑樹的高度大致保持在log(n)的級別。

---------------------------------------------------------------------------------------------------------------------------------

黑紅樹插入：

黑紅樹插入節(jié)點默認為紅色

?黑紅樹刪除：

刪除節(jié)點無子節(jié)點：

刪除節(jié)點有一個子節(jié)點：

?

刪除節(jié)點有兩個子節(jié)點

樹的旋轉(zhuǎn)：

?旋轉(zhuǎn)相關內(nèi)容取自：AVL樹的旋轉(zhuǎn)圖解和簡單實現(xiàn)

旋轉(zhuǎn) 在每一次插入數(shù)值之后，樹的平衡性都可能被破壞，這時可以通過一個簡單的操作來矯正平衡–旋轉(zhuǎn)。

旋轉(zhuǎn)的目的就是減少高度，通過降低整棵樹的高度來平衡。哪邊的樹高，就把那邊的樹向上旋轉(zhuǎn)。

通過旋轉(zhuǎn)可以降低高度。

所謂的左旋和右旋都是以子樹為原點的：如b是a的子樹，那么旋轉(zhuǎn)就圍繞b來進行。 如果b是a的左子樹，那么就圍繞b將a向右旋轉(zhuǎn)，看著就像是a直接掉下來了，掉成了b的右子樹。 如果b是a的右子樹，那么就圍繞b將a向左旋轉(zhuǎn)，看著就像是a直接掉下來了，掉成了b的左子樹。 插入節(jié)點時分四種情況，四種情況對應的旋轉(zhuǎn)方法是不同的：

例如對于被破壞平衡的節(jié)點 a 來說：

1.LL 右旋轉(zhuǎn)

就拿最簡單的舉例了。

一個簡單的AVL樹：

這時是平衡的，如果在插入一個元素3，就會變成下面這樣，破壞平衡：

被破壞了平衡首先要找到是哪個樹被破壞了平衡，然后調(diào)整這個樹。然后繼續(xù)往上一個一個的調(diào)整。

既然是被新插入的節(jié)點3破壞的，那么不平衡的樹一定在從新插入的節(jié)點3到根節(jié)點8的路徑上。找離新插入的節(jié)點最近的不平衡的樹進行調(diào)整，上圖中就是7.

節(jié)點7的左子樹 高度為1，右子樹為空，高度為-1 ，不平衡。根據(jù)表格要進行右旋轉(zhuǎn)。

先把7這顆不平衡的樹挑出來：

這棵樹是最近的不平衡的樹，7的左子樹5高度為1，右子樹為空，所以右子樹高度是-1.兩者的高度差達到了2，超過了1.

因為左子樹5的高度更高，所以要把左子樹5向上提一下，這時旋轉(zhuǎn)就很明顯了，抓著5向上一提，7就掉到5的右邊了，成了5的右子樹。

這個過程就是右旋：

這時繼續(xù)往上找，發(fā)現(xiàn)每個節(jié)點都符合了平衡條件，所以整棵樹就變成了AVL樹。

那如果節(jié)點5本來就有了右子樹呢？照樣右旋轉(zhuǎn)，只要把原來5的右子樹變成旋轉(zhuǎn)后的7的左子樹就行了。因為5的右子樹肯定比5大，但是也肯定比7小的：

其實上面最后旋轉(zhuǎn)成的樹是下面這樣的：

這棵樹的根節(jié)點是不平衡的，還需要使用后面的雙旋轉(zhuǎn)來調(diào)整。

使用LR先左旋后右旋調(diào)整后是這樣的，具體方法看后面的：

2. RR 左旋轉(zhuǎn)

在右子樹的右子樹上插入節(jié)點破壞的平衡需要左旋轉(zhuǎn)來矯正。

左旋轉(zhuǎn)和右旋轉(zhuǎn)類似，都是單旋轉(zhuǎn)，給個流程圖。

3. LR 先左旋再右旋

如果在第一個例子中插入的不是3，而是6，就成了下面的樣子，依然說破壞了平衡

被破壞平衡的樹依然是7，但是這次就不能通過一次旋轉(zhuǎn)解決了，咋轉(zhuǎn)都不行。

要從6開始到7進行先左旋再右旋才可以矯正平衡：

4. RL 先右旋再左旋

當破壞平衡的節(jié)點是這個樹的右子樹的左子樹時，要進行先右旋轉(zhuǎn)再左旋轉(zhuǎn)來矯正。

同樣是從破壞平衡的那個節(jié)點開始旋轉(zhuǎn)，先右旋轉(zhuǎn)后左旋轉(zhuǎn)：

柚子快報邀請碼778899分享：數(shù)據(jù)結構 二叉樹的分類

http://yzkb.51969.com/

文章來源