AVL Tree：自平衡二叉树¶

AVL-Tree的定义&性质¶

AVL-Tree：全称Adelson-Velsky and Landis tree, 是由这两位数学家提出的自平衡二叉搜索树(self-balancing binary search tree)
性质：
- 满足BST的所有性质
- 树中每个节点的左右子树高度差不能超过1

当平衡因子超出了{-1，0，1}的范围时为失衡
具体检验过程
- 按照BST方法插入新节点
- 从插入位置向上回溯
- 对每个经过的祖先节点更新高度、计算平衡因子、判断是否失衡
- 当某个节点平衡因子变2或-2，说明该节点失衡，需要旋转
失衡有4种结构：LL,LR,RL,RR

左旋 - 处理RR失衡

对z左旋

      y
     / \
    z   x

右旋 - 处理LL失衡

对z右旋

      y
     / \
    x   z

完整情况下的左、右旋

右旋

      z
     / \
    y   T4
   / \
  T1  T2

对z右旋

先右旋y

像BST插入一样，找位置，比current小就往左，比current大就往右，找到空位置插入
从新节点的父节点开始网上，更新每个祖先的高度
```
height(node)=1+max(height(node.left),height(node.right))
```

对经过的每个节点计算平衡因子

balanceFactor=height(left)−height(right)

删除之后，对路径上的每个节点更新高度

height(node)=1+max(height(node.left),height(node.right))

计算平衡因子

balance(node)=height(node.left)−height(node.right)

Operation	Time Complexity	原因
Search	(O(\log n))	最多沿一条根到叶的路径查找，路径长度等于树高，而 AVL 的高度是 (O(\log n))
Insert	(O(\log n))	先按 BST 找位置，再向上更新高度并检查失衡；路径长度是 (O(\log n))，旋转是 (O(1))
Delete	(O(\log n))	先按 BST 删除，再一路向上更新高度和重新平衡；最多检查到根，路径长度是 (O(\log n))
Left Rotation	(O(1))	只修改常数个指针和节点高度
Right Rotation	(O(1))	只修改常数个指针和节点高度
Rebalancing at one node	(O(1))	对单个失衡节点的修复只涉及一次单旋或一次双旋
Height of AVL Tree	(O(\log n))	AVL 始终保持平衡，高度不会线性退化