• 樹

  • 樹是一種非線性的存儲結(jié)構(gòu)。是一種一對多的形式。只有一個根節(jié)點，不會形成環(huán)路。
  • 節(jié)點的度是節(jié)點擁有子樹的數(shù)量。
  • 樹是層次結(jié)構(gòu)，樹的深度是他最大的層數(shù)。
  • 滿二叉樹，完全二叉樹。及其性質(zhì)。
  • 二叉樹的前、中、后序遍歷，用遞歸和循環(huán)；兩種方式（后面詳細(xì)補(bǔ)充！）

---

• BST樹（Binary Search Tree）二叉搜索樹

  ?二叉搜索樹，又稱二叉排序樹、二叉查找樹。左子樹小于根，右子樹大于根節(jié)點。且左右子樹都是二叉搜索樹。
  ?二叉搜索樹用于在樹中查找元素，由于是排序的，平均查找效率為O(logN)。
  
  • 插入
    ?二叉排序樹的插入操作是以查找為基礎(chǔ)的。當(dāng)樹中不存在關(guān)鍵字等于key的結(jié)點時才插入。新插入的結(jié)點一定是葉子結(jié)點，并且是查找不成功時查找路徑上訪問的最后一個結(jié)點的左孩子或右孩子結(jié)點。創(chuàng)建就是循環(huán)插入。
    ?算法以遞歸形式完成。TreeNode* InsertBinaryTree(TreeNode* root, const int& val) {if (root == NULL){ root = new TreeNode(val); //根節(jié)點為空，插入，返回。return root;}else {if (val <= root->data) //小于等于根節(jié)點，遞歸插入左子樹root->lchild = SortBinaryTree(root->lchild, val);else //大于根節(jié)點，遞歸插入右子樹root->rchild = SortBinaryTree(root->rchild, val);}return root; }
  • 刪除節(jié)點
• 如果刪除的節(jié)點沒有左右節(jié)點，則直接刪除即可；
• 如果只有左孩子或右孩子，則用左右子樹代替這個節(jié)點即可；
• 如果有左右孩子，則情況復(fù)雜一些。假如要刪除78這個節(jié)點，我們在左子樹中找到最大的節(jié)點，換到78處即可。最大的則是左子樹中一直往右查找。這個最大的節(jié)點一定沒有右子樹，因為右子樹比他大，但可能會有左子樹，左子樹還需接到他的前驅(qū)節(jié)點上去。則這樣又會有兩種情況，一種是圖中這種，最大的是從70開始往右找找到的75，則75的左子樹接到70的右子樹位置；另一種假如沒有75，則是70最大，70替換78后，70的左節(jié)點接到70的左邊。
  
  void delete_Node2(BSTree &p) {BSTree q,s; if(!p->lchild) //由于這個if在前面，所以左右子樹均為空的情況會在這里處理 { //如果左子樹為空，則只需重接其右子樹q = p;p = p->rchild ;free(q);}else if(!p->rchild){ //如果右子樹為空，則只需重接其左子樹q = p;p = p->lchild;free(q);}else{ //如果左右子樹都不為空，采取修改左子樹的方法，也可以修改右子樹，方法類似q = p;s = p->lchild; //取待刪節(jié)點的左節(jié)點while(s->rchild) { //找到中序遍歷時會得到的直接前驅(qū) q = s;s = s->rchild;}//用s來替換待刪節(jié)點pp->data = s->data; //根據(jù)情況，將s的左子樹重接到q上if(p != q)q->rchild = s->lchild; //接到前驅(qū)節(jié)點的右子樹elseq->lchild =s->lchild; //接到被刪除節(jié)點位置的左子樹free(s);} }

---

• AVL樹-二叉平衡樹

  ?二叉平衡樹的平衡條件是樹的左右子樹的深度差不大于1。且左右子樹也是平衡的。
  ?優(yōu)點是左右高度均衡，二叉平衡查找樹的效率高（假如二叉排序樹往一邊倒，則查找效率趨于O(n) ）。
  ?二叉平衡查找樹的插入較為麻煩，因為插入的元素可能會破壞樹的平衡。有LL、LR、RL、RR四種不同情況。通過旋轉(zhuǎn)，使得重新平衡。
  ?LL與RR類似，如下圖。
  
  LR與RL類似，如下圖。
  

---

• 紅黑樹

  ?紅黑樹是一種平衡二叉查找樹，查找、插入效率都較高。而紅黑樹之所以難是難在它是自平衡的二叉查找樹，在進(jìn)行插入和刪除等可能會破壞樹的平衡的操作時，需要重新自處理達(dá)到平衡狀態(tài)。
  ?AVL樹是強(qiáng)平衡，插入時要做多次旋轉(zhuǎn)操作。紅黑是弱平衡的，用非嚴(yán)格的平衡來換取增刪節(jié)點時候旋轉(zhuǎn)次數(shù)的降低，其在在增加或刪除節(jié)點時，旋轉(zhuǎn)操作要比AVL樹更少；因此當(dāng)搜索的次數(shù)遠(yuǎn)遠(yuǎn)大于插入和刪除，則選擇AVL樹，如果搜索，插入刪除次數(shù)幾乎差不多，應(yīng)該選擇RB樹。
  ?紅黑樹雖然是復(fù)雜的，但在最壞情況運行時間也是非常良好的，并且在實踐中是高效的，其可以在O(logn)時間內(nèi)做查找、插入和刪除。
  ?在面試的時候考的應(yīng)該不多，面試官一般不會讓寫紅黑樹的代碼，最多會讓介紹下紅黑樹的原理，因此了解下在紅黑樹的插入和刪除時，樹旋轉(zhuǎn)操作是很重要的！
• 紅黑樹定義和性質(zhì)
  1：每個節(jié)點要么是黑色，要么是紅色。
  2：根節(jié)點是黑色。
  3：每個葉子節(jié)點是黑色（NIL，葉節(jié)點不含值，只有顏色）。
  4：每個紅色結(jié)點的兩個子結(jié)點一定都是黑色。
  ??推論：紅色節(jié)點的父節(jié)點是黑色
  5：任意一結(jié)點到每個葉子結(jié)點的路徑都包含數(shù)量相同的黑結(jié)點。
  ??推論：如果一個結(jié)點存在黑子結(jié)點，那么該結(jié)點肯定有兩個子結(jié)點
  
  ? 上圖是一顆紅黑樹。紅黑樹并不是一個完美平衡二叉查找樹，從圖可以看到，根結(jié)點P的左子樹顯然比右子樹高，但左子樹和右子樹的黑結(jié)點的層數(shù)是相等的。所以我們叫紅黑樹這種平衡為黑色完美平衡。

---

• B樹、B+樹、B*樹

  ?B樹，英文是B-tree，是一種平衡多路樹，不叫B減樹，就是B樹。
  ?B樹是一種多路樹。因為他的子節(jié)點不止2個，可以是多個。
  ?B樹是一種平衡樹。不僅平衡，B樹的要求更高，要求左右子樹高度相同，也就是說，根節(jié)點到每個葉子節(jié)點的距離都相同。

  • 基本概念：

    • ceil(x)，這是一個向上取整的函數(shù)，比如ceil(1.1)=2。注意這不是四舍五入，而且是得到比參數(shù)大的那個整數(shù)。
    • B樹可以用階數(shù)來定義，階數(shù)代表了B樹的節(jié)點最多可以擁有的子節(jié)點數(shù)，后面用m來代表B樹的階數(shù)。

  • M階B樹的特性：

  • 每個結(jié)點至多擁有m棵子樹；
  • 根結(jié)點至少擁有兩顆子樹（存在子樹的情況下）；
  • 除了根結(jié)點以外，其余每個分支結(jié)點至少擁有 m/2 棵子樹；
  • 所有的葉結(jié)點都在同一層上（所以左右子樹高度一樣）；
  • 有 k 棵子樹的分支結(jié)點則存在 k-1 個關(guān)鍵碼，關(guān)鍵碼按照遞增次序進(jìn)行排列；
    關(guān)鍵字?jǐn)?shù)量需要滿足ceil(m/2)-1 <= n <= m-1；關(guān)鍵碼大小在兩個分支節(jié)點之間，且要大于左邊子樹的關(guān)鍵碼，小于右邊子樹的關(guān)鍵碼。

  下圖是一個3階的B樹：
  

  • B樹的查找
    ?B樹的是一個M階查找樹，根二階查找樹類似，只不過每個節(jié)點中可能不止一個數(shù)字。

  • B樹的節(jié)點添加
    參考這個blog：B樹的添加

    • 新結(jié)點一般插在最下面一層，通過搜索找到對應(yīng)的結(jié)點進(jìn)行插入，那么根據(jù)即將插入的結(jié)點的數(shù)量又分為下面幾種情況。
    • 如果該結(jié)點的關(guān)鍵字個數(shù)沒有到達(dá)m-1個，那么直接插入即可；
    • 如果該結(jié)點的關(guān)鍵字個數(shù)已經(jīng)到達(dá)了m-1個，那么根據(jù)B樹的性質(zhì)顯然無法滿足，需要將其進(jìn)行分裂。分裂的規(guī)則是該結(jié)點分成兩半，將中間的關(guān)鍵字進(jìn)行提升，加入到父親結(jié)點中，但是這又可能存在父親結(jié)點也滿員的情況，則不得不向上進(jìn)行回溯，甚至是要對根結(jié)點進(jìn)行分裂，那么整棵樹都加了一層。

  • B+樹

• B+樹的非葉子節(jié)點不記錄數(shù)據(jù)本身，只記錄引用的連接。基于此特點，B+樹在非葉子節(jié)點的文件會非常小。葉子節(jié)點會包含所有的關(guān)鍵字。

• B+樹每個葉子節(jié)點都有指向相鄰的下一個兄弟葉子節(jié)點的指針。基于此特點，B+樹在范圍查詢上的效率比B樹高了很多。

• 這條區(qū)別是有爭議的，有人說B+樹的節(jié)點中關(guān)鍵字和子節(jié)點個數(shù)相同，也有人說B+樹和B樹一樣關(guān)鍵字比子節(jié)點少一個。

如果我們認(rèn)為上述第三條中關(guān)鍵字和子節(jié)點個數(shù)是相同的，那B+樹就是這樣的：

?向B+樹中添加關(guān)鍵字時，也存在節(jié)點分裂的情況，在節(jié)點分裂時，會生成一個新的節(jié)點，把原節(jié)點中一半的元素復(fù)制到新節(jié)點，在父節(jié)點中添加指向新節(jié)點的關(guān)鍵字和指針。

---

• 哈夫曼樹

  ?簡單說帶權(quán)路徑長度WPL(Weighted Path Length of Tree)最小的二叉樹

  ?樹的路徑長度是從樹根到樹中每一結(jié)點的路徑長度之和。在結(jié)點數(shù)目相同的二叉樹中，完全二叉樹的路徑長度最短。

  ?結(jié)點的權(quán)：在一些應(yīng)用中，賦予樹中結(jié)點的一個有某種意義的實數(shù)。

  ?結(jié)點的帶權(quán)路徑長度：結(jié)點到樹根之間的路徑長度與該結(jié)點上權(quán)的乘積。

  ?樹的帶權(quán)路徑長度 (Weighted Path Length of Tree)：定義為樹中所有葉結(jié)點的帶權(quán)路徑長度之和。樹的帶權(quán)路徑長度亦稱為樹的代價。

  哈夫曼樹定義：假設(shè)有 n 個權(quán)值[W1,W2,….WN]，構(gòu)造有 n 個葉子的二叉樹，每個葉子的權(quán)值是 n 個權(quán)值之一，這樣的二叉樹可以構(gòu)造很多個，其中必有一個是帶權(quán)路徑長度最小的，這棵二叉樹就稱為最優(yōu)二叉樹或哈夫曼樹。
  用途：哈夫曼編碼是最優(yōu)前綴碼， 因此可用于加密解密。還可以文件壓縮解壓。
  構(gòu)造：參考https://blog.csdn.net/qq_33990383/article/details/53073825。

---

總結(jié)

以上是生活随笔為你收集整理的阿龙的学习笔记---3.26---常用的各种树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。