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，則節點被視為left-heavy；如果其平衡因子為 1，則節點被視為right-heavy。