平衡树 与 AVL树

1.二分搜索树问题：

• 假如元素按照顺序添加： 1 -> 2 -> 3 -> 4 -> 5 则会退化为链表。而搜索的时间复杂度仅和树的高度有关，所以使用平衡二叉树解决这个问题。

  2.AVL树：

  最早可以自平衡的二分搜索树结构，假如在满二叉树的情况下，高度将达到最小。
  对于任意一个节点，左右子树的高度差不能超过1。（AVL树中的平衡二叉树）
  

• 左右子树需要为节点设定高度值，叶子节点为1， 每往上一个节点+1。

• 需要计算平衡因子：节点平衡因子 = 左子树高度 - 右子树高度，若平衡因子绝对值 >=2, 则不再是平衡二叉树。
• 若平衡因子 >=2 或 <= -2 ，则此时需要采用措施恢复二叉树。