AVL樹是根據它的發明者G.M. Adelson-Velsky和E.M. Landis命名的。它是最先發明的自平衡二叉查找樹，也被稱為高度平衡樹。相比于"二叉查找樹"，它的特點是：AVL樹中任何節點的兩個子樹的高度最大差别為1。它是一種高度平衡的二叉排序樹。高度平衡？意思是說，要麼它是一棵空樹，要麼它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。
将二叉樹上結點的左子樹深度減去右子樹深度的值稱為平衡因子BF，那麼平衡二叉樹上的所有結點的平衡因子隻可能是-1、0和1。隻要二叉樹上有一個結點的平衡因子的絕對值大于1，則該二叉樹就是不平衡的。
平衡二叉樹的前提是它是一棵二叉排序樹。
距離插入結點最近的，且平衡因子的絕對值大于1的結點為根的子樹，稱為最小不平衡子樹。如下圖所示，當插入結點37時，距離它最近的平衡因子的絕對值超過1的結點是58。
1、平衡二叉樹實作原理
平衡二叉樹建構的基本思想就是在建構二叉排序樹的過程中，每當插入一個結點時，先檢查是否因插入而破壞了樹的平衡性，若是，則找出最小不平衡子樹。在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各結點之間的連結關系，進行相應的旋轉，使之成為新的平衡子樹。
下面講解一個平衡二叉樹建構過程的例子。現在又a[10] = {3, 2, 1, 4, 5, 6, 7, 10, 9,
8}需要建構二叉排序樹。在沒有學習平衡二叉樹之前，根據二叉排序樹的特性，通常會将它建構成如下左圖。雖然完全符合二叉排序樹的定義，但是對這樣高度達到8的二叉樹來說，查找是非常不利的。是以，更加期望建構出如下右圖的樣子，高度為4的二叉排序樹，這樣才可以提供高效的查找效率。
現在來看看如何将一個數組構成出如上右圖的樹結構。
對于數組a的前兩位3和2，很正常地建構，到了第個數“1”時，發現此時根結點“3”的平衡因子變成了2，此時整棵樹都成了最小不平衡子樹，需要進行調整，如下圖圖1（結點左上角數字為平衡因子BF值）。因為BF為正，是以将整個樹進行右旋（順時針），此時結點2成了根結點，3成了2的右孩子，這樣三個結點的BF值均為0，非常的平衡，如下圖圖2所示。
然後再增加結點4，平衡因子沒有改變，如上圖圖3。增加結點5時，結點3的BF值為-2，說明要旋轉了。由于BF是負值，對這棵最小平衡子樹進行左旋（逆時針旋轉），如下圖圖4，此時整個樹又達到了平衡。
繼續增加結點6時，發現根結點2的BF值變成了-2，如下圖圖6所示。是以對根結點進行了左旋，注意此時本來結點3是結點3的左孩子，由于旋轉後需要滿足二叉排序樹特性，是以它成了結點2的右孩子，如圖7所示。
增加結點7，同樣的左旋轉，使得整棵樹達到平衡，如下圖8和9所示。
當增加結點10時，結構無變化，如圖10所示。再增加結點9，此時結點7的BF變成了-2，理論上隻需要旋轉最小不平衡樹7、9、10即可，但是，如果左旋轉後，結點9變成了10的右孩子，這是不符合二叉排序樹的特性的，此時不能簡單的左旋。如圖11所示。
仔細觀察圖11，發現根本原因在于結點7的BF是-2，而結點10的BF是1，也就是說，它們兩個一正一負，符号并不統一，而前面的幾次旋轉，無論左還是右旋，最小不平衡子樹的根結點與它的子結點符号都是相同的。這就是不能直接旋轉的關鍵。
不統一，不統一就把它們先轉到符号統一再說，于是先對結點9和結點10進行右旋，使得結點10成了9的右子樹，結點9的BF為-1，此時就與結點7的BF值符号統一了，如圖12所示。
這樣再以結點7為最小不平衡子樹進行左旋，得到如下圖13。接着，插入8，情況與剛才類似，結點6的BF是-2，而它的右孩子9的BF是1，如圖14，是以首先以9為根結點，進行右旋，得到圖15，此時結點6和結點7的符号都是負，再以6為根結點左旋，最終得到最後的平衡二叉樹，如圖16所示。
通過這個例子，可以發現，當最小不平衡樹根結點的平衡因子BF是大于1時，就右旋，小于-1時就左旋，如上例中的結點1、5、6、7的插入等。插入結點後，最小不平衡子樹的BF與它的子樹的BF符号相反時，就需要對結點先進行一次旋轉以使得符号相同後，再反向旋轉一次才能夠完成平衡操作，如上例中結點9、8的插入時。
目前linux kernel裡已不再使用平衡二叉樹，代之以紅黑樹rbtree。