AVL樹

AVL 樹是平衡二元搜尋樹。這篇文章介紹了二元搜尋樹。二元樹的搜尋、插入和刪除時間取決於樹的高度。在最壞的情況下，高度為 O(n)。如果一棵樹完全平衡——即完全二元樹——它的高度是log n。我們能維持一棵完美平衡的樹嗎？是的，但這樣做的成本會很高。妥協的辦法是維持一個平衡良好的樹－－也就是說，每個節點的兩個子樹的高度大致相同。

AVL 樹 非常平衡。 AVL 樹於 1962 年由兩位俄羅斯電腦科學家 G. M. Adelson-Velsky 和 ​​E. M. Landis 發明（因此稱為 AVL）。在 AVL 樹中，每個節點的兩個子樹的高度差為 0 或 1。可以證明AVL樹的最大高度為O(log n)。

在 AVL 樹中插入或刪除元素的過程與常規二元搜尋樹相同，只是在插入或刪除操作後可能需要重新平衡樹。節點的平衡因子是其右子樹的高度減去其左子樹的高度。若節點的平衡因子為 -1、0 或 1，則稱該節點為 平衡。若節點的平衡因子為-1，則節點被視為左重，如果其平衡因子為+1，則視為右重 .

以上是AVL樹的詳細內容。更多資訊請關注PHP中文網其他相關文章！