1. 前言
AVL树是一种自平衡的二叉搜索树。为什么会出现AVL树。众所周知，虽然普通的二叉搜索树的平均时间复杂度为O(logn)，但最差的情况的时间复杂度为O(n)。为了避免最差的这种情况，出现了AVL树。
我们规定：如果树有个节点它的左子树的高度-右子树的高度大于1或者它的右子树的高度-左子树的高度小于-1，我们就说该二叉搜索树是不平衡的，需要调整。
2. 四种失衡情况以及解决方案
简单聊聊AVL树相关的四种失衡情况：
- （LL）某节点的左子树高度-右子树高度大于1，且失衡节点的左孩子也高于右孩子或等高；
- （LR）某节点的左子树高度-右子树高度大于1，且其左孩子的左子树高度-右子树高度小于-1；
- （RL）某节点的右子树高度-左子树高度大于1，且其右孩子的左子树高度-右子树高度大于1；
- （RR）某节点的右子树高度-左子树高度大于1，且失衡节点的右孩子也高于左孩子或等高；
AVL树需要进行调整：
- （LL）该节点需要右旋。
- （LR）该节点的左孩子需要左旋，且该节点需要右旋。
- （RL）该节点的右孩子需要右旋，且该节点需要左旋。
- （RR）该节点需要左旋。
LL旋转情况如图：
LR旋转情况如图：
RL旋转情况如图：
RR旋转情况如图：
解决方法：
// 右旋(LL)private AVLNode RightRotation(AVLNode red) {AVLNode yellow = red.left;AVLNode blue = yellow.right;yellow.right = red;red.left = blue;// 更新red节点的高度updateHeight(red);// 再更新yellow节点的高度(因为red是yellow的孩子节点，// 只有计算对了red节点的高度，才会正确得出yellow节点的高度)updateHeight(yellow);return yellow;}// 左旋(RR)private AVLNode LeftRotation(AVLNode red){AVLNode yellow = red.right;AVLNode blue = yellow.left;yellow.left = red;red.left = blue;updateHeight(red);updateHeight(yellow);return yellow;}// (LR)private AVLNode LeftRightRotation(AVLNode node) {// 失衡节点的左孩子需要左旋node.left = LeftRotation(node.left);// 失衡节点需要右旋return RightRotation(node);}// (RL)private AVLNode RightLeftRotation(AVLNode node) {// 失衡节点的右孩子需要右旋node.right = RightRotation(node.right);// 失衡节点需要左旋return LeftRotation(node);}3. AVL树代码
public class AVLTree {static private class AVLNode{int key;Object value;AVLNode left;AVLNode right;// 一个节点的默认高度为1int height = 1;public AVLNode(int key, Object value) {this.key = key;this.value = value;}public AVLNode(int key, Object value, AVLNode left, AVLNode right) {this.key = key;this.value = value;this.left = left;this.right = right;}}private int doHeight(AVLNode node){return node == null ? 0 : node.height;}private void updateHeight(AVLNode node) {if (node == null) {return;}node.height = Integer.max(doHeight(node.left), doHeight(node.right)) + 1;}// 平衡因子（balance factor）,处于-1，0，1时是满足平衡的。private int bf(AVLNode node){return doHeight(node.left) - doHeight(node.right);}// 右旋(LL)private AVLNode RightRotation(AVLNode red) {AVLNode yellow = red.left;AVLNode blue = yellow.right;yellow.right = red;red.left = blue;// 更新red节点的高度updateHeight(red);// 再更新yellow节点的高度(因为red是yellow的孩子节点，// 只有计算对了red节点的高度，才会正确得出yellow节点的高度)updateHeight(yellow);return yellow;}// 左旋(RR)private AVLNode LeftRotation(AVLNode red){AVLNode yellow = red.right;AVLNode blue = yellow.left;yellow.left = red;red.left = blue;updateHeight(red);updateHeight(yellow);return yellow;}// (LR)private AVLNode LeftRightRotation(AVLNode node) {// 失衡节点的左孩子需要左旋node.left = LeftRotation(node.left);// 失衡节点需要右旋return RightRotation(node);}// (RL)private AVLNode RightLeftRotation(AVLNode node) {// 失衡节点的右孩子需要右旋node.right = RightRotation(node.right);// 失衡节点需要左旋return LeftRotation(node);}//检查节点是否失衡，重新平衡代码private AVLNode balance(AVLNode node) {if (node == null) return null;int bf = bf(node);if (bf > 1 && bf(node.left) >= 0){// LLreturn RightRotation(node);} else if (bf > 1 && bf(node.left) < 0) {return LeftRightRotation(node);} else if (bf < -1 && bf(node.right) > 0) {return RightLeftRotation(node);} else if (bf < -1 && bf(node.right) <= 0) {return LeftRotation(node);}// 进行到这，说明该节点不需要做平衡调整return node;}// 向AVL树添加节点，并保持平衡特性public void put(AVLNode node) {}
}