AVL樹，全名Adelson-Velsky和Landis樹，是一種自平衡二叉查找樹。在AVL樹中，任何節點的兩個子樹的高度最大差異為一，這樣保證了樹的平衡性，從而改進了二叉查找樹在最壞情況下的時間複雜度。這種結構是由蘇聯的科學家G. M. Adelson-Velsky和E. M. Landis於1962年首次提出的。
AVL樹的主要操作包括插入、查找和刪除，每次操作後樹都會進行自我調整以保持平衡。為了維持平衡，AVL樹可能會進行旋轉操作，主要有四種類型的旋轉：左旋、右旋、左右旋和右左旋。這些旋轉操作有助於在保持二叉查找樹的所有操作優勢的同時，降低操作的時間複雜度，使其在最壞的情況下依然能維持對數時間性能。
這種平衡機制使AVL樹成為在需要頻繁查找的應用中非常有用的數據結構，特別是在數據集大且動態變化的環境中。
阿摩線上測驗
登入