设计初衷

树主要是链表数据结构的变形，目的是实现各种操作的O(logN)时间复杂度，从而优化链表的O(N)时间复杂度。对于二叉查找树来说，对于每个节点，左子树的值均小于该节点的值，右节点的值均大于该节点值。故当数据分布不均匀时，可能会导致所有节点都在根节点的左子树或者右子树，从而退化回了链表，造成性能问题。所以为了解决这个问题，AVL树通过对树节点的旋转操作，保证每个节点的左右子树高度差最大为1来避免退化为链表，实现相对平衡，各种操作平均复杂度为O(logN)。

AVL树的特性

AVL树：每个节点的左右子树的高度差最大为1的二叉查找树。当因为插入操作导致某个节点不符合AVL树的特性时，需要对受到影响的节点（即左右子树的高度差大于1的节点）进行旋转操作来使之重新符合AVL树的每个节点的左右子树的高度差最大为1的特性。节点的高度：从该节点到其子节点的最长路径。树的高度为根节点到叶子节点中最长的路径的长度。节点的深度：从根节点到该节点的路径长度，同一深度的节点的高度不一定相等。破坏平衡的两种情况：外边插入（左子树的左子节点，右子树的右子节点），内边插入（左子树的右子节点，右子树的左子节点）。外边插入：单旋转内边插入：双旋转

节点插入与平衡调整

由于AVL树是一棵二叉查找树，节点定义如下：除了左右节点定义外，每个节点还包含高度height。（代码引自《数据结构与算法分析 Java语言描述》第三版）插入过程为：首先是按照二叉查找树（左子树的值小于根节点的值，右子树的值大于根节点的值）插入这个节点，实现如下：平衡旋转操作在balance方法定义。如果插入之后，没有节点的高度失衡，则插入操作结束。否则需要根据是外边插入还是内边插入来决定是单旋转和双旋转，实现如下：

32行代码表示在左子树的左节点失衡（39行为在右子树的右节点失衡，情况类似），故是“外边插入”，执行单旋转，rotateWithLeftChild，旋转过程的实现和示意图如下：35行表示为左子树的右节点失衡（41行为右子树的左节点失衡，情况类似），故是“内边插入”，执行双旋转：

删除节点操作与旋转平衡

删除操作跟插入操作类似，也需要在删除之后调用balance方法对失衡节点进行调整，不过balance方法不能完全重用以上的balance方法，因为删除操作情况更加复杂。