AVL树

操作

AVL树的基本操作一般涉及运作同在不平衡的二叉查找树所运作的同样的算法。但是要进行预先或随后做一次或多次所谓的"AVL旋转"。
以下图表以四列表示四种情况，每行表示在该种情况下要进行的操作。在左左和右右的情况下，只需要进行一次旋转操作；在左右和右左的情况下，需要进行两次旋转操作。

删除

从AVL树中删除，可以通过把要删除的节点向下旋转成一个叶子节点，接着直接移除这个叶子节点来完成。因为在旋转成叶子节点期间最多有log n个节点被旋转，而每次AVL旋转耗费固定的时间，所以删除处理在整体上耗费O(log n) 时间。

搜索

可以像普通二叉查找树一样的进行，所以耗费O(log n)时间，因为AVL树总是保持平衡的。不需要特殊的准备，树的结构不会由于查找而改变。（这是与伸展树搜索相对立的，它会因为搜索而变更树结构。）

AVL节点数计算

高度为h的AVL树，总节点数N最多； 
最少节点数如以斐波那契数列可以用数学归纳法证明：
 =  - 1 (是斐波那契数列的第h+2项，根据斐波那契多项式得来)。

即:
 = 0  (表示AVL Tree高度为0的节点总数)
 = 1  (表示AVL Tree高度为1的节点总数)
 = 2  (表示AVL Tree高度为2的节点总数)
 =  +  + 1   (表示AVL Tree高度为h的节点总数)

换句话说，当节点数为N时，高度h最多为。