Python數據結構——AVL樹的基本概念

jiekechoo 發布于2019-07-24 18:26 / 634人閱讀

摘要：我們知道，當樹變得不平衡時和操作會使二叉搜索樹的性能降低到。樹實現抽象數據類型就像一個普通的二叉搜索樹，唯一不同的是這棵樹的工作方式。我們通過比較每個節點的左右子樹的高度完成比較。

平衡二叉搜索樹

在上一節中我們討論了建立一個二叉搜索樹。我們知道，當樹變得不平衡時get和put操作會使二叉搜索樹的性能降低到O(n)。在這一節中我們將看到一種特殊的二叉搜索樹，它可以自動進行調整，以確保樹隨時都保持平衡。這種樹被稱為AVL樹，命名源于其發明者：G.M. Adelson-Velskii 和 E.M. Landis。

AVL樹實現抽象數據類型Map就像一個普通的二叉搜索樹，唯一不同的是這棵樹的工作方式。為實現我們的AVL樹我們需要在樹中的每個節點加入一個平衡因子并跟蹤其變化情況。我們通過比較每個節點的左右子樹的高度完成比較。更正式地講，我們定義一個節點的平衡因子為左子樹和右子樹的高度之差。

$$balanceFactor = height(leftSubTree) - height(rightSubTree)$$

利用以上對平衡因子的定義，如果平衡因子大于零，我們稱子樹“左重”(left-heavy)。如果平衡因子小于零，那么子樹“右重”(right-heavy)。如果平衡因子為零，則樹是完全平衡的。為實現AVL樹，目的是得到一棵平衡的樹，我們定義平衡因子如果是 -1，0 或 1，那么這棵樹是平衡的。一旦樹中節點的平衡因子超出了這個范圍，我們需要有一個把樹恢復平衡的過程。圖 1 是一個不平衡的“右重”樹的例子，其中每個節點都標注了平衡因子。

圖 1：一棵標注了平衡因子的不平衡的右重樹

AVL樹性能

在我們繼續進行之前讓我們看看引入這個新的平衡因子的結果。我們的要求是，確保樹上的平衡因子始終為 -1，0 或 1。我們可以通過對鍵的操作得到更好的時間復雜度。首先，我們要思考如何利用這個平衡條件去改變最壞情況下的樹。有兩種可能性需要考慮，左重樹和右重樹。如果我們考慮樹的高度為 0，1，2 和 3，圖 2 舉出了在新規則下可能出現的最不平衡的左重樹的例子。

圖 2：最壞情況下的左重AVL樹

讓我們看看樹上的節點的總數。我們看到一棵高度為 0 的樹有 1 個節點，一個高度為 1 的樹有 1 + 1 = 2 個節點，一個高度為 2 的樹有 1 + 1 + 2 = 4 個節點，一棵高度為 3 的樹有 1 + 2 + 4 = 7 個節點。概括起來，高度為h的樹的節點數（N_h）為：

$$N_h = 1 + N_{h-1} + N_{h-2}$$

可能你很熟悉這個公式，因為它和斐波那契序列非常相似。我們可以利用這個公式通過樹中的節點的數目推導出一個AVL樹的高度。在我們的印象中，斐波那契數列與斐波那契數的關系為：

$$F_0 = 0
F_1 = 1
F_i = F_{i-1} + F_{i-2} text{ for all } i ge 2$$

數學中一個重要的結果是，隨著斐波那契序列的數字越來越大，F_i / F_i?1 越來越接近于黃金比例 Φ：

$$Φ = frac{1 + sqrt{5}}{2}$$

如果你想看到上式的推導過程你可以查閱相關的數學資料。我們簡單地將這個方程 F_i 近似為：

$$F_i =Φ^i/sqrt{5}$$

如果利用這種近似我們可以將 N_h 的方程改寫為：

$$N_h = F_{h+2} - 1, h ge 1$$

通過黃金比例近似代替斐波那契數列的項我們可以得到：

$$N_h = frac{Φ^{h+2}}{sqrt{5}} - 1$$

如果我們整理這些方程的項，并且兩邊都以 2 為底取對數，然后求解h，則可以導出：

$$log{N_h+1} = (H+2)log{Φ} - frac{1}{2} log{5}
h = frac{log{N_h+1} - 2 log{Φ} + frac{1}{2} log{5}}{log{Φ}}
h = 1.44 log{N_h}$$

這個推導過程告訴我們，在任何時候我們的AVL樹的高度等于樹中節點數以 2 為底的對數的常數（1.44）倍。這對我們搜索AVL樹來說是好消息因為它限制了搜索的復雜度到O(logN)。

GPU云服務器云服務器基本概念短信產品基本概念機器學習基本概念超融合架構基本概念

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/37752.html

Python數據結構——AVL樹的實現

摘要：一旦子樹平衡因子為零，那么父節點的平衡因子不會發生改變。新根的父節點將成為舊根的父節點。因為其他操作都是移動整個子樹，被移動的子樹內的節點的平衡因子不受旋轉的影響。讓表示以為根節點的子樹的高度。既然，我們已經證明，保持 AVL 樹的平衡將會使性能得到很大的提升，那我們看看如何在程序中向樹插入一個新的鍵值。因為所有的新鍵是作為葉節點插入樹的，而新葉子的平衡因子為零，所以我們對新插入的節...

Pink 2019-07-31 12:22 評論0 收藏0
學習JavaScript數據結構與算法 — AVL樹

摘要：可以看到，一次左單旋將右側子樹的高度減小了，而左側子樹的高度增加了。如圖，對進行右單旋，需要左子樹的右子樹的高度小于等于左子樹的高度，否則不能達到平衡的效果，只是把不平衡性從左邊轉移到了右邊。 AVL樹普通二叉搜索樹可能出現一條分支有多層，而其他分支卻只有幾層的情況，如圖1所示，這會導致添加、移除和搜索樹具有性能問題。因此提出了自平衡二叉樹的概念，AVL樹（阿德爾森-維爾斯和蘭迪斯樹...

impig33 2019-08-21 11:31 評論0 收藏0
AVL樹的Java實現

摘要：容忍不平衡紅黑樹的思路的核心是增大了可容忍的高度差，從而實現既保證查詢效率，也保證了插入和刪除后調整平衡的效率。紅黑樹的查詢效率是略低于樹的，但是紅黑樹通過犧牲了少許查詢效率，使插入刪除后的調整效率達到了常數級別。定義 Wikipedia - AVL樹在計算機科學中，AVL樹是最早被發明的自平衡二叉查找樹。在AVL樹中，任一節點對應的兩棵子樹的最大高度差為1，因此它也被稱為高度平衡...

leejan97 2019-08-16 17:13 評論0 收藏0