1.AVL树介绍
2.2 等价变换方式
等价变换的基本操作有两种：
顺时针旋转(zig)，可以形象的理解为x->y箭头方向下午两点变成了下午四点，也被称为右旋
逆时针旋转(zag)，可以形象的理解为y->x箭头方向上午十点变成了上午八点，也被称为左旋
顺时针旋转和逆时针旋转的操作是互逆的，复杂等价变换操作可以看成是由这两种基本操作组合而成。
顺时针旋转：
逆时针旋转：
2.3 AVL树的失衡状态及重平衡
在了解如何恢复AVL树平衡状态之前，需要先理解几个关键点：
1.无论是插入新节点还是删除老节点，最多只会导致插入/删除节点位置的上层的历代祖先节点失去平衡(数量大致为 logN)，而不会导致全树节点都失去平衡，因此只需要判断其历代祖先节点的平衡状态，即可判断其是否破坏了AVL树的平衡状态
2.当原先较高的子树中插入新节点时，可能会导致历代祖先节点失衡(部分祖先节点，而非全部)
3.当原先较低的子树中删除老节点时，可能会导致历代祖先节点失衡(部分祖先节点，而非全部)
针对AVL树的失衡节点进行重平衡时，主要关注失衡节点自身(N Node)、引起失衡方向的孩子节点(S Son)、引起失衡方向的孙子节点(GS GrandSon)及所属子树，对其进行等价变换操作，使之恢复平衡。
我们从失衡节点出发，依据失衡节点和其引起失衡方向的孩子节点、其引起失衡方向的孙子节点的共同构成的拓扑结构，共以下四种形态：
2.3.1 左左形
左左形 插入节点引起失衡及重平衡：
左左形 删除节点引起失衡及重平衡：
2.3.3 左右形
左右形 插入节点引起失衡及重平衡：
左右形 删除节点引起失衡及重平衡：
2.3.2 右右形
右右形和左左形是镜像的拓扑结构，失衡场景和重平衡手段与"2.3.1 左左形"原理相同，限于篇幅，不再展开说明。
2.3.4 右左形
右左形和左右形是镜像的拓扑结构，失衡场景和重平衡手段与"2.3.2 左右形"原理相同，限于篇幅，不再展开说明。
2.3.5 插入和删除操作重平衡的区别
在示意图中，注意观察标识树高层次的横向细长的白色箭头。
插入和删除操作会导致操作节点位置的历代祖先失去平衡，这需要从低到高依次检查平衡状态并进行重平衡处理。
插入新节点导致失衡并重平衡的过程中，当前失衡节点(最低的失衡祖先节点)所在子树的高度在重平衡操作完成后和未插入新节点之前是一样的。因而当最低位置的祖先节点恢复了平衡后，更高的祖先节点也将自动的恢复平衡（因为插入前是平衡的，而插入后失衡子树的高度在重平衡后也和原先一致了）。
删除老节点导致失衡并重平衡的过程中，当前失衡节点(最低的失衡祖先节点)所在子树的高度在重平衡操作完成后和未插入新节点之前可能是不一样的(所在子树高度降低1)。因而当最低位置的祖先节点恢复平衡后，可能会导致更高的祖先节点进而失去平衡，这种现象会向上逐层传播。最坏的极端情况下，每当恢复一个较低的祖先节点平衡时，都会导致更高一层祖先节点失衡，直至根节点完成重平衡，这样的重平衡操作最多需要执行(logN)次。
2.4 3+4重构
前面介绍了针对不同失衡状态拓扑结构进行重平衡的方法，都是使用一次或多次旋转的方式完成的。
如果我们聚焦于重平衡操作所涉及的元素，会发现其实质只是改变了Node，Son，GrandSon三个节点及所挂载的四颗子树(T0,T1,T2,T3)的位置关系。更为重要的是，无论是左左形还是其它三种形状，其重平衡完成之后的拓扑结构是一样的，区别只在于N，S，GS三个节点的相对位置不同。
因此，便有了另一种更高效的重平衡等价变换的方式，被称为"3+4重构"。3+4重构在重平衡时，暴力的将元素打散，并不使用旋转的技巧，而是直接改变节点和节点、节点和子树之间的引用关系，一口气将其转变为重平衡之后的最终拓扑结构，直达目标。
3.AVL树实现细节
3.1 二叉搜索树拓展
AVL树的实现继承自前面介绍的普通二叉搜索树—TreeMap类。由于AVL树通过树高作为判断平衡的依据，因此在二叉搜索树TreeMap的节点中增加了一个height(高度)属性。
/** * 二叉搜索树 内部节点 * */ static class EntryNode<K,V> implements Map.EntryNode<K,V>{ /** * key值 * */ K key; /** * value值 * */ V value; /** * 高度值 * */ int height; /** * 左孩子节点 * */ EntryNode<K,V> left; /** * 右孩子节点 * */ EntryNode<K,V> right;
