平衡樹（AVL tree）

引入

• 之前學習的樹，都不是平衡的，查找時需要一個一個往內比較，一個結點只儲存一個值，數據量存儲較大，樹的深度會非常的深，導致數據查詢時效率會十分的低，本次學習的平衡樹就能解決這個問題

定義

• 平衡樹，即AVL tree，命名來源于第一種該類型樹的兩個發明者Adelson-Velsky 和 Landis，有時也叫Balanced tree，平衡樹是一種能自我保持“平衡”的二叉搜索樹，在一顆平衡樹中，兩顆子樹之間的高度差最多不超過1，當他們之間的高度差超過1時，它就會自動重新平衡樹的高度以恢復這種性質

平衡樹的一些特性

• 查詢、插入和刪除在最壞情況和平均情況下都是花費O(log n)的時間，相對于一般的二叉樹，降低了樹的高度，提高了查詢、插入、刪除等效率
• 插入和刪除可能需要對應部分的子樹做一次或多次的旋轉動作(后續紅黑樹中將會介紹到旋轉的定義)

下面介紹和實現一種平衡查找樹2-3查找樹

2-3查找樹

2-3查找樹介紹

• 定義：2-3查找樹是一種結點能儲存最多兩個元素最少一個元素的平衡樹，儲存1個元素的結點擁有2條子樹邊，稱之為2-結點，儲存2個元素的結點擁有三條子樹邊，稱之為3-結點
• 2-結點：含有一個鍵(及其對應的值)和兩條鏈,左鏈接指向2-3樹中的鍵都小于該結點,右鏈接指向的2-3樹中的鍵都大于該結點。
• 3-結點：含有兩個鍵(及其對應的值)和三條鏈,左鏈接指向的2-3樹中的鍵都小于該結點,中鏈接指向的2 3樹中的鍵都位于該結點的兩個鍵之間,右鏈接指向的2-3樹中的鍵都大于該結點。
  
  一棵完全平衡的2-3樹具有以下性質:

任意空鏈接到根結點的路徑長度都是相等的。

4-結點變換為3-結點時,樹的高度不會發生變化,只賄當根結點是臨時的4-結點,分解根結點時,樹高+1。

2-3樹與普通二叉查找樹最大的區別在于,普通的二叉查找樹是自頂向下生長,而2-3樹是自底向上生長。

2-3查找樹的查找過程介紹

實現2-3查找樹的查找過程跟二叉樹的查找過程幾乎是一樣的：

2-3查找樹的不同情況下的插入過程：

向2-結點插入新鍵：

向一顆只含3-結點的查找樹插入新鍵

向一顆父結點為2-結點的3-結點插入新鍵

向一個父結點為3-結點的3-結點中插入新鍵

分解根結點

在插入過程中，只要遇到含有四個子結點連接邊的結點，就要對其進行平衡操作，以使其保持2-3的平衡定義

直接實現2-3樹比較復雜,因為:

• 需要處理不同的結點類型,非常繁瑣;
• 要多次比較操作來將結點下移;
• 需要_上移來拆分4結點;
• 拆分4結點的情況有很多種;

這里暫時不進行實現，但是需要對2-3樹的思想著重進行理解，2-3查找樹實現起來比較復雜，在某些情況插入后的平衡操作可能會使得效率降低。但是2-3查找樹作為一種比較重要的概念和思路對于我們后面即將要講到的紅黑樹、B-樹和B+樹非常重要。

總結

以上是生活随笔為你收集整理的数据结构之平衡树：2-3查找树的介绍——16的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。