樹、二叉樹、AVL樹，B樹基礎學習

一、樹的基本概念

樹是一種資料結構，它是由n（n>1）個有限節點組成的一個具有層次關系的集合。

樹的基本概念

1、雙親：若有一個結點有子樹，那麼該結點就稱為子樹根的“雙親”。

2、孩子結點：子樹的根稱為改子樹雙親結點的“孩子結點”。

3、兄弟結點：有相同的雙親的結點稱為“兄弟結點”。

4、結點的度：結點擁有的子樹的數目。

5、葉子結點：度為0的結點。

6、分支結點：度不為0的結點

6、樹的度：數中結點的最大的度

7、層次：根節點層次為1，其餘節點的層次等于該節點的雙親節點的層次+1.

8、樹的高度：數中結點的最大層次

9：森林：0個或多個不想交的樹的組成。對森林加上一個根，森林即成為樹；删去根，樹即成為森林。

二、二叉樹的基本概念

定義：二叉樹是每個結點最多有兩個子樹的樹的結構。通常子樹被稱作“左子樹”和“右子樹”。

二叉樹特點

由二叉樹定義以及圖示分析得出二叉樹有以下特點：

• 每個結點最多有兩顆子樹，是以二叉樹中不存在度大于2的結點。
• 左子樹和右子樹是有順序的，次序不能任意颠倒。
• 即使樹中某結點隻有一棵子樹，也要區分它是左子樹還是右子樹。

二叉樹性質

• 在二叉樹的第i層上最多有2i-1 個節點 。（i>=1）
• 二叉樹中如果深度為k,那麼最多有2k-1個節點。(k>=1）
• n0=n2+1 n0表示度數為0的節點數，n2表示度數為2的節點數。
• 在完全二叉樹中，具有n個節點的完全二叉樹的最小深度為[log2n]+1，其中[log2n]是向下取整。
• 若對含 n 個結點的完全二叉樹從上到下且從左至右進行 1 至 n 的編号，則對完全二叉樹中任意一個編号為 i 的結點有如下特性：

(1) 若 i=1，則該結點是二叉樹的根，無雙親, 否則，編号為 [i/2] 的結點為其雙親結點;
(2) 若 2i>n，則該結點無左孩子， 否則，編号為 2i 的結點為其左孩子結點；
(3) 若 2i+1>n，則該結點無右孩子結點， 否則，編号為2i+1 的結點為其右孩子結點。
           

斜樹

斜樹：所有的結點都隻有左子樹的二叉樹叫左斜樹。所有結點都是隻有右子樹的二叉樹叫右斜樹。這兩者統稱為斜樹。

滿二叉樹

滿二叉樹：在一棵二叉樹中。如果所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹。

滿二叉樹的特點有：

1）葉子隻能出現在最下一層。出現在其它層就不可能達成平衡。

2）非葉子結點的度一定是2。

3）在同樣深度的二叉樹中，滿二叉樹的結點個數最多，葉子數最多。

完全二叉樹

完全二叉樹：對一顆具有n個結點的二叉樹按層編号，如果編号為i(1<=i<=n)的結點與同樣深度的滿二叉樹中編号為i的結點在二叉樹中位置完全相同，則這棵二叉樹稱為完全二叉樹。

特點：

1）葉子結點隻能出現在最下層和次下層。

2）最下層的葉子結點集中在樹的左部。

3）倒數第二層若存在葉子結點，一定在右部連續位置。

4）如果結點度為1，則該結點隻有左孩子，即沒有右子樹。

5）同樣結點數目的二叉樹，完全二叉樹深度最小。

注：滿二叉樹一定是完全二叉樹，但反過來不一定成立。

二叉樹的周遊

1、先序周遊：

對于每一個結點都有：

（1）先通路根節點。

（2）再通路左子樹。

（3）後通路右子樹。

2、中序周遊

對于每一個結點都有：

（1）先通路左子樹。

（2）再通路根節點。

（3）後通路右子樹。

3、後序周遊

對于每一個結點都有

（1）先通路左子樹。

（2）再通路右子樹。

（3）後通路根結點。

二叉搜尋樹

定義

二叉搜尋樹又稱二叉查找樹，亦稱為二叉排序樹。設x為二叉查找樹中的一個節點，x節點包含關鍵字key，節點x的key值記為key[x]。如果y是x的左子樹中的一個節點，則key[y] <= key[x]；如果y是x的右子樹的一個節點，則key[y] >= key[x]。

性質

（1）若左子樹不空，則左子樹上所有節點的值均小于它的根節點的值；

（2）若右子樹不空，則右子樹上所有節點的值均大于它的根節點的值；

（3）左、右子樹也分别為二叉搜尋樹；

如圖為一顆二叉搜尋樹：

節點結構

二叉樹的節點結構通常包含三部分，其中有：左孩子的指針，右孩子指針以及資料域。節點的圖示如下：

建立二叉搜尋樹

現有序列：A = {61, 87, 59, 47, 35, 73, 51, 98, 37, 93}。根據此序列構造二叉搜尋樹過程如下：

（1）i = 0，A[0] = 61，節點61作為根節點；

（2）i = 1，A[1] = 87，87 > 61，且節點61右孩子為空，故81為61節點的右孩子；

（3）i = 2，A[2] = 59，59 < 61，且節點61左孩子為空，故59為61節點的左孩子；

（4）i = 3，A[3] = 47，47 < 59，且節點59左孩子為空，故47為59節點的左孩子；

（5）i = 4，A[4] = 35，35 < 47，且節點47左孩子為空，故35為47節點的左孩子；

（6）i = 5，A[5] = 73，73 < 87，且節點87左孩子為空，故73為87節點的左孩子；

（7）i = 6，A[6] = 51，47 < 51，且節點47右孩子為空，故51為47節點的右孩子；

（8）i = 7，A[7] = 98，98 < 87，且節點87右孩子為空，故98為87節點的右孩子；

（9）i = 8，A[8] = 93，93 < 98，且節點98左孩子為空，故93為98節點的左孩子；

建立完畢後如圖中的二叉搜尋樹：

查找

查找流程：

  （1）如果樹是空的，則查找結束，無比對。

  （2）如果被查找的值和節點的值相等，查找成功。

  （3）如果被查找的值小于節點的值，遞歸查找左子樹，

  （4）如果被查找的值大于節點的值，遞歸查找右子樹，

插入

插入流程：

（1）先檢測該元素是否在樹中已經存在。如果已經存在，則不進行插入；

（2）若元素不存在，則進行查找過程，并将元素插入在查找結束的位置。

删除

（1）删除節點為葉子節點

  删除葉子節點的方式最為簡單，隻需查找到該節點，直接删除即可。例如删除圖中的葉子節點37、節點51、節點60、節點73和節點93的方式是相同的。

（2） 删除的節點隻有左子樹

  删除的節點若隻有左子樹，将節點的左子樹替代該節點位置。例如：删除圖中的98節點：

（3）删除的節點隻有右子樹

  删除的節點若隻有右子樹，将節點的右子樹替代該節點位置。這種情況與删除左子樹處理方式類似，不再贅述。

（4） 删除的節點既有左子樹又有右子樹。

  若删除的節點既有左子樹又有右子樹，這種節點删除過程相對複雜。其流程如下：

 （1）周遊待删除節點的左子樹，找到其左子樹中的最大節點，即删除節點的前驅節點；

 （2）将最大節點代替被删除節點；

 （3）删除左子樹中的最大節點；

 （4）左子樹中待删除最大節點一定為葉子節點或者僅有左子樹。按照之前情形删除即可。

注：同樣可以使用删除節點的右子樹中最小節點，即後繼節點代替删除節點，此流程與使用前驅節點類似。

平衡二叉樹

定義

平衡二叉樹定義(AVL)：它或者是一顆空樹，或者具有以下性質的二叉排序樹：它的左子樹和右子樹的深度之差(平衡因子)的絕對值不超過1，且它的左子樹和右子樹都是一顆平衡二叉樹。

一棵AVL樹有如下必要條件:

1. 條件一：它必須是二叉查找樹。
2. 條件二：每個節點的左子樹和右子樹的高度差至多為1。

圖一中左邊二叉樹的節點45的左孩子46比45大，不滿足二叉搜尋樹的條件，是以它也不是一棵平衡二叉樹。

右邊二叉樹滿足二叉搜尋樹的條件，同時它滿足條件二，是以它是一棵平衡二叉樹。

左邊二叉樹的節點45左子樹高度2，右子樹高度0，左右子樹高度差為2-0=2，不滿足條件二；

右邊二叉樹的節點均滿足左右子樹高度差至多為1，同時它滿足二叉搜尋樹的要求，是以它是一棵平衡二叉樹。

注：AVL樹的查找、插入、删除操作在平均和最壞的情況下都是O（logn），這得益于它時刻維護着二叉樹的平衡。

AVL樹相關概念

平衡因子：将二叉樹上節點的左子樹高度減去右子樹高度的值稱為該節點的平衡因子BF(Balance Factor)。

最小不平衡子樹：距離插入節點最近的，且平衡因子的絕對值大于1的節點為根的子樹.

在圖三中，左邊二叉樹的節點45的BF = 1，插入節點43後，節點45的BF = 2。節點45是距離插入點43最近的BF不在[-1,1]範圍内的節點，是以以節點45為根的子樹為最小不平衡子樹。

AVL樹的平衡調整

整個實作過程是通過在一棵平衡二叉樹中依次插入元素(按照二叉排序樹的方式)，若出現不平衡，則要根據新插入的結點與最低不平衡結點的位置關系進行相應的調整。分為LL型、RR型、LR型和RL型4種類型，各調整方法如下(下面用A表示最低不平衡結點)：

1. LL型調整：

由于在A的左孩子(L)的左子樹(L)上插入新結點，使原來平衡二叉樹變得不平衡，此時A的平衡因子由1增至2。下面圖1是LL型的最簡單形式。顯然，按照大小關系，結點B應作為新的根結點，其餘兩個節點分别作為左右孩子節點才能平衡，A結點就好像是繞結點B順時針旋轉一樣。

LL型調整的一般形式如下圖2所示，表示在A的左孩子B的左子樹BL(不一定為空)中插入結點(圖中陰影部分所示)而導緻不平衡( h 表示子樹的深度)。這種情況調整如下：①将A的左孩子B提升為新的根結點；②将原來的根結點A降為B的右孩子；③各子樹按大小關系連接配接(BL和AR不變，BR調整為A的左子樹)。

2.RR型調整：

由于在A的右孩子®的右子樹®上插入新結點，使原來平衡二叉樹變得不平衡，此時A的平衡因子由-1變為-2。圖3是RR型的最簡單形式。顯然，按照大小關系，結點B應作為新的根結點，其餘兩個節點分别作為左右孩子節點才能平衡，A結點就好像是繞結點B逆時針旋轉一樣。

RR型調整的一般形式如下圖4所示，表示在A的右孩子B的右子樹BR(不一定為空)中插入結點(圖中陰影部分所示)而導緻不平衡( h 表示子樹的深度)。這種情況調整如下：

• 将A的右孩子B提升為新的根結點
• 将原來的根結點A降為B的左孩子
• 各子樹按大小關系連接配接(AL和BR不變，BL調整為A的右子樹)。

  

  3. LR型調整

由于在A的左孩子(L)的右子樹®上插入新結點，使原來平衡二叉樹變得不平衡，此時A的平衡因子由1變為2。圖5是LR型的最簡單形式。顯然，按照大小關系，結點C應作為新的根結點，其餘兩個節點分别作為左右孩子節點才能平衡。

LR型調整的一般形式如下圖6所示，表示在A的左孩子B的右子樹(根結點為C，不一定為空)中插入結點(圖中兩個陰影部分之一)而導緻不平衡( h 表示子樹的深度)。這種情況調整如下：①将B的左孩子C提升為新的根結點；②将原來的根結點A降為C的右孩子；③各子樹按大小關系連接配接(BL和AR不變，CL和CR分别調整為B的右子樹和A的左子樹)。

4. RL型調整：

由于在A的右孩子®的左子樹(L)上插入新結點，使原來平衡二叉樹變得不平衡，此時A的平衡因子由-1變為-2。圖7是RL型的最簡單形式。顯然，按照大小關系，結點C應作為新的根結點，其餘兩個節點分别作為左右孩子節點才能平衡。

RL型調整的一般形式如下圖8所示，表示在A的右孩子B的左子樹(根結點為C，不一定為空)中插入結點(圖中兩個陰影部分之一)而導緻不平衡( h 表示子樹的深度)。這種情況調整如下：①将B的左孩子C提升為新的根結點；②将原來的根結點A降為C的左孩子；③各子樹按大小關系連接配接(AL和BR不變，CL和CR分别調整為A的右子樹和B的左子樹)。

平衡二叉樹實作的執行個體

選取一組資料分别為2，1，0，3，4，5，6，9，8，7的10個結點來構造平衡二叉樹。

• 首先資料為2的結點作為根結點插入，接着插入1，仍是平衡的，再插入0是，2的平衡因子變為2，此時出現了不平衡，是以需要進行調整，最低不平衡結點為2，屬于LL型，調整過程如圖1所示。

  

• 接着插入3，是平衡的，再插入4，此時出現了不平衡，結點 1 和 2 的平衡因子都為

  -2，結點2為最低不平衡結點，屬于RR型，調整過程如圖2所示

  

• 接着插入5，此時結點 1 的平衡因子為 -2，導緻不平衡，結點1為最低不平衡結點，屬于RR型，調整如圖3所示。

  

• 接着插入6，此時結點4的平衡因子為 -2，導緻不平衡，結點4為最低不平衡結點，屬于RR型，調整如圖4所示。

  

• 接着插入9，是平衡的，再插入8，此時結點 3、5、6 的平衡因子都為 -2，導緻不平衡，結點6為最低不平衡結點，屬于RL型，調整如圖5所示。

  

• 插入7，此時結點3、5的平衡因子為 -2，導緻不平衡，最低不平衡結點為5，屬于RL型，調整如圖6所示。

  

B（B-）樹

B-樹，即為B樹。因為B樹的原英文名稱為B-tree，而國内很多人喜歡把B-tree譯作B-樹，其實，這是個非常不好的直譯，很容易讓人産生誤解。如人們可能會以為B-樹是一種樹，而B樹又是一種樹。而事實上是，B-tree就是指的B樹，目前了解B的意思為平衡。

　　B樹的出現是為了彌合不同的存儲級别之間的通路速度上的巨大差異，實作高效的 I/O。平衡二叉樹的查找效率是非常高的，并可以通過降低樹的深度來提高查找的效率。但是當資料量非常大，樹的存儲的元素數量是有限的，這樣會導緻二叉查找樹結構由于樹的深度過大而造成磁盤I/O讀寫過于頻繁，進而導緻查詢效率低下。另外資料量過大會導緻記憶體空間不夠容納平衡二叉樹所有結點的情況。B樹是解決這個問題的很好的結構

概念

　　首先，B樹不要和二叉樹混淆，在計算機科學中，B樹是一種自平衡樹資料結構，它維護有序資料并允許以對數時間進行搜尋，順序通路，插入和删除。B樹是二叉搜尋樹的一般化，因為節點可以有兩個以上的子節點。[1]與其他自平衡二進制搜尋樹不同，B樹非常适合讀取和寫入相對較大的資料塊（如CD光牒）的存儲系統。它通常用于資料庫和檔案系統。

定義

B樹是一種平衡的多分樹，通常我們說m階的B樹，它必須滿足如下條件：

• 每個節點最多隻有m個子節點。
• 每個非葉子節點（除了根）具有至少⌈ m/2⌉子節點。
• 如果根不是葉節點，則根至少有兩個子節點。
• 具有k個子節點的非葉節點包含k -1個鍵。
• 所有葉子都出現在同一水準，沒有任何資訊（高度一緻）。

什麼是B樹的階 ？

B樹中一個節點的子節點數目的最大值，用m表示，假如最大值為10，則為10階，如圖

所有節點中，節點【13,16,19】擁有的子節點數目最多，四個子節點（灰色節點），是以可以定義上面的圖檔為4階B樹。

什麼是根節點 ？

節點【10】即為根節點，特征：根節點擁有的子節點數量的上限和内部節點相同，如果根節點不是樹中唯一節點的話，至少有倆個子節點（不然就變成單支了）。在m階B樹中（根節點非樹中唯一節點），那麼有關系式2<= M <=m，M為子節點數量；包含的元素數量 1<= K <=m-1,K為元素數量。

什麼是葉子節點？

節點【1,2】、節點【11,12】等最後一層都為葉子節點，葉子節點對元素的數量有相同的限制，但是沒有子節點，也沒有指向子節點的指針。特征：在m階B樹中葉子節點的元素符合（m/2）-1<= K <=m-1。

B樹的插入

B樹的插入是指插入一條記錄，如果B樹已存在需要插入的鍵值時，用新的值替換舊的值；若B樹不存在這個值時，則是在葉子結點進行插入操作。

對高度為h的m階B樹，新結點一般插第h層。通過檢索可以确定關鍵碼應插入的位置，

1）若該結點中關鍵碼個數小于m-1，則直接插入就可

2）若該結點中關鍵碼個數等于m-1，則将引起結點的分裂，以中間的關鍵碼為界将結點一分為二，産生了一個新的結點，并将中間關鍵碼插入到父結點中；

重複上述過程，最壞情況一直分裂到根結點， 建立一個新的根結點，整個B樹就增加一層。

舉例如下：

》〉》〉下面以5階B樹舉例，根據B樹的定義，結點最多有4個值，最少有2個值。

序列（39，22，97，41，53，13，21，40，30，27，33，36，24，34，35，26，17，28，29，31，32）

a）在空樹插入39，此時就有一個值，根結點也是葉子結點

b）繼續插入22，97和41值，根結點變為4個值，符合要求

c）插入53值

插入之後發現超過結點最多隻有4個值，是以要以中間值進行分開，分開後目前結點要指向父結點，分裂之後，發現符合要求

d）插入13，21，40，同樣造成分裂，

e）緊接着插入30，27，33，36，24，34，35

f）将26再次插入進去

發現有5個值，超過B樹的定義，需要以27為中心分裂，27進軍父結點

發現父結點也超過4個，再次分裂

g）最後插入17，28，29，31，32的記錄

B樹的删除

B樹删除：首先要查找該值是否在B樹中存在，如果存在，判斷該元素是否存在左右孩子結點，如果有，則上移孩子結點中的相近結點（左孩子最右邊的結點或者有孩子最左邊的結點）到父結點中，然後根據移動之後的情況；如果沒有，進行直接删除；如果不存在對應的值，則删除失敗。

1）如果目前要删除的值位于非葉子結點，則用後繼值覆寫要删除的值，再用後繼值所在的分支删除該後繼值。（該後繼值必須位于葉子結點上）

2）該結點值個數不小于Math.ceil(m/2)-1（取上線函數），結束删除操作，否則下一步

3）如果兄弟結點值個數大于Math.ceil(m/2)-1，則父結點中下移到該結點，兄弟的一個值上移，删除操作結束。

将父結點的key下移與目前的結點和他的兄弟姐妹結點key合并，形成一個新的結點，

有些結點可能有左兄弟，也有右兄弟，我們可以任意選擇一個兄弟結點即可。

》〉》〉下面以5階B樹舉例進行删除，根據B樹的定義，結點最多有4個值，最少有2個值。

a）原始狀态

b）在上面的B樹删除21，删除之後結點個數大于等于2，是以删除結束

c）删除27之後為

27處于非葉子結點，用27的後繼替換。也即是28替換27，然後在右孩子結點删除28，如上。

發現删除，目前葉子結點的記錄的個數已經小于2，而兄弟結點中有3個記錄我們可以從兄弟結點中借取一個key，父結點中的28就下移，兄弟結點中的26就上移,删除結束，結果如下

d）删除32

删除之後發現，目前結點中有key，而兄弟都有兩個key，是以隻能讓父結點的30下移到和孩子一起合并，成為新的結點，并指向父結點，經拆封發現符合要求

哈夫曼樹

哈夫曼樹的構造

注意：哈夫曼樹并不唯一，但帶權路徑長度一定是相同的。

（1）8個結點的權值大小如下：

（2）從19，21，2，3，6，7，10，32中選擇兩個權小結點。選中2，3。同時算出這兩個結點的和5。

（3）從19，21，6，7，10，32，5中選出兩個權小結點。選中5，6。同時計算出它們的和11。

（4）從19，21，7，10，32，11中選出兩個權小結點。選中7，10。同時計算出它們的和17。

（BTW：這時選出的兩個數字都不是已經構造好的二叉樹裡面的結點，是以要另外開一棵二叉樹；或者說，如果兩個數的和正好是下一步的兩個最小數的其中的一個，那麼這個樹直接往上生長就可以了，如果這兩個數的和比較大，不是下一步的兩個最小數的其中一個，那麼就并列生長。）

（5）從19，21，32，11，17中選出兩個權小結點。選中11，17。同時計算出它們的和28。

（6）從19，21，32，28中選出兩個權小結點。選中19，21。同時計算出它們的和40。另起一顆二叉樹。

（7）從32，28， 40中選出兩個權小結點。選中28，32。同時計算出它們的和60。

（8）從 40， 60中選出兩個權小結點。選中40，60。同時計算出它們的和100。 好了，此時哈夫曼樹已經建構好了。