现有一串序列1234567，用序列数作为节点值构造二叉搜索树，对于同样的节点，插入的顺序不同，最后得到的二叉搜索树的结构也不一样
当节点固定时，左右子树高度越接近，这颗二叉树就越平衡（高度越低）
理想的平衡是像完全二叉树，满二叉树那样，高度是最小的
在计算机科学中，AVL树是最先发明的自平衡二叉查找树，AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它
相比于"二叉搜索树"，AVL树的特点是：AVL树中任何节点的两个子树的高度最大差别为1
-
添加导致的失衡
新增节点为12
祖先节点10、15失衡
试着分析其他可能出现的情况，得出以下结论：
可能的最坏情况是所有祖先节点都失衡
父节点、非祖先节点，都不可能失衡
因为如果是父节点那么它下面还有一个子节点，总共就两个节点，两个节点的高度差一定是在≤1的范围
-
平衡因子
概念：某节点左右子树的高度差
普通二叉搜索树的平衡因子：
AVL树经过一系列变换可以减少树的高度，让平衡因子的绝对值<=1，每个节点的平衡因子只可能是1，0，-1，超过1称之为失衡
AVL树的搜索、添加、删除的时间复杂度为O(logn)
-
变换
旋转变换可以帮助二叉树恢复平衡，按可能出现的情况分为四种：
RR（右右旋转）：当在AVL树中的一个节点的右子树的右子树上插入了节点，导致右子树高度过高，就会触发右右旋转。通过右右旋转，我们可以将当前节点旋转到其父节点的位置，而原先的父节点则变为当前节点的左子节点。
RL（右左旋转）：当在AVL树中的一个节点的右子树的左子树上插入了节点，导致右子树的左子树高度过高，就会触发右左旋转。通过右左旋转，我们先对右子节点进行右旋转，再对当前节点进行左旋转，以保持树的平衡。
LR（左右旋转）：当在AVL树中的一个节点的左子树的右子树上插入了节点，导致左子树的右子树高度过高，就会触发左右旋转。通过左右旋转，我们先对左子节点进行左旋转，再对当前节点进行右旋转，也是为了保持树的平衡。
LL（左左旋转）：当在AVL树中的一个节点的左子树的左子树上插入了节点，导致左子树高度过高，就会触发左左旋转。通过左左旋转，我们可以将当前节点旋转到其父节点的位置，而原先的父节点则变为当前节点的右子节点。
说明：为了便于观察分析，将左右子树画为长条状，T1 T2 T3 T4可以想象成是节点高度未知的左右子树，在新节点添加之前处于平衡
1、RR-左单旋
2、LL-右单旋
3、LR-RR左单旋，LL右单旋
4、RL-LL右单旋，RR左单旋
-
删除导致的失衡
删除值为11的节点，值为15的节点失衡
试着分析其他可能出现的情况，得出以下结论：
删除只可能导致父节点失衡，除父节点以外的其他节点都不可能失衡
源码解析：
AVLNode：
首先需要了解AVLnode
BST的Node在下面 BST参考 的链接中
private static class AVLNode<E> extends Node<E> {
int height = 1;
public AVLNode(E element, Node<E> parent) {
super(element, parent);
}
public int balanceFactor() {
int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
return leftHeight - rightHeight;
}
public void updateHeight() {
int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
height = 1 + Math.max(leftHeight, rightHeight);
}
public Node<E> tallerChild() {
int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
if (leftHeight > rightHeight) return left;
if (leftHeight < rightHeight) return right;
return isLeftChild() ? left : right;
}
}
balanceFactor( )此方法用于获取节点的平衡因子，需要先获得左（leftNode）右(rightNode)节点的高度，然后根据定义：平衡因子=左节点高度 - 右节点高度
updateHeight( )此方法用于更新节点高度，这个方法的就已经存在说明了在特定位置会进行使用那么什么时候需要更新高度呢？结合下面的add方法进行分析
add( )方法：
添加节点因为涉及的操作较多，所以相对比较复杂
它是在BST的add基础之上进行的添加
BST参考：
BST节点的添加只是按照 二叉树的特征（任意节点的值大于左子树所有节点的值，任意节点的值小于右子树所有节点的值）进行的添加，并不涉及添加后的节点旋转，所以在此基础上需要增加旋转操作（ afterAdd( )方法 ）
下面代码是BST的add操作源码，注意afterAdd( )的位置
public void add(E element) {
elementNotNullCheck(element);
// 添加第一个节点
if (root == null) {
root = createNode(element, null);
size++;
// 新添加节点之后的处理
afterAdd(root);
return;
}
// 添加的不是第一个节点
// 找到父节点
Node<E> parent = root;
Node<E> node = root;
int cmp = 0;
do {
cmp = compare(element, node.element);
parent = node;
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else { // 相等
node.element = element;
return;
}
} while (node != null);
// 看看插入到父节点的哪个位置
Node<E> newNode = createNode(element, parent);
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
size++;
// 新添加节点之后的处理
afterAdd(newNode);
}
分析：
代码的核心思想是 创建新节点 ,因为插入新节点需要element和parent，而parent需要分情况讨论
parent可能出现的情况：parent为null，parent为node.left，parent为node.right
此外在每一种添加操作的最后应该有旋转操作( afterAdd( ) )
-
afterAdd( )
afterAdd( )涉及的操作较多，需要判断平衡因子……
private void afterAdd(Node<E> node) {
while ((node = node.parent) != null) {
if (isBalanced(node)) {
// 更新高度
updateHeight(node);
} else {
// 恢复平衡
rebalance(node);
// 整棵树恢复平衡
break;
}
}
}
循环内：
首先判断是否平衡 isBalanced(node)
private boolean isBalanced(Node<E> node) {
return Math.abs(((AVLNode<E>)node).balanceFactor()) <= 1;
}
public int balanceFactor() {
int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
return leftHeight - rightHeight;
}
平衡则更新高度
public void updateHeight() {
int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
height = 1 + Math.max(leftHeight, rightHeight);
}
不管是获取平衡因子还是更新高度都需要当前节点的高度来完成，关系图如下：
因为每添加一个节点就会更新高度，所以每一个AVLNode的height属性就是当前节点的高度
-
remove( )
删除只可能导致父节点失衡
除父节点以外的其他节点都不可能失衡
删除不会影响父节点的高度，自然祖父节点的平衡因子不会改变（删除了短边，长边高度不变）
删除与添加一样也是LL RR LR RL四种情况，可以自行画图模拟
remove也是在BST的删除方法基础上增加了afterRemove
afterRemove里的逻辑与afterAdd大概一样，只是少了break,因为删除节点后恢复平衡会进行旋转操作，在旋转恢复了平衡后的这个过程里会造成更高一级的祖先节点一直持续到根节点都是不平衡的，那么就需要不断的rebalance恢复平衡
public void remove(E element) {
remove(node(element));
}
private void remove(Node<E> node) {
if (node == null) return;
size--;
if (node.hasTwoChildren()) { // 度为2的节点
// 找到后继节点
Node<E> s = successor(node);
// 用后继节点的值覆盖度为2的节点的值
node.element = s.element;
// 删除后继节点
node = s;
}
// 删除node节点（node的度必然是1或者0）
Node<E> replacement = node.left != null ? node.left : node.right;
if (replacement != null) { // node是度为1的节点
// 更改parent
replacement.parent = node.parent;
// 更改parent的left、right的指向
if (node.parent == null) { // node是度为1的节点并且是根节点
root = replacement;
} else if (node == node.parent.left) {
node.parent.left = replacement;
} else { // node == node.parent.right
node.parent.right = replacement;
}
// 删除节点之后的处理
afterRemove(node);
} else if (node.parent == null) { // node是叶子节点并且是根节点
root = null;
// 删除节点之后的处理
afterRemove(node);
} else { // node是叶子节点，但不是根节点
if (node == node.parent.left) {
node.parent.left = null;
} else { // node == node.parent.right
node.parent.right = null;
}
// 删除节点之后的处理
afterRemove(node);
}
}
protected void afterRemove(Node<E> node) {
while ((node = node.parent) != null) {
if (isBalanced(node)) {
// 更新高度
updateHeight(node);
} else {
// 恢复平衡
rebalance(node);
}
}
}
AVL搜索、删除、添加的时间复杂度是Olog(n)
