AVL树是最先发明的自平衡⼆叉查找树，AVL是⼀颗空树，或者具备下列性质的⼆叉搜索树：
它的左右子树都是AV树，且左右子树的高度差的绝对值不超过1。
AVL树是⼀颗高度平衡搜索⼆叉树， 通过控制高度差去控制平衡。

• AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家，他们在1962年的论文《An algorithm for the organization of information》中发表了它。
• AVL树实现这里我们引入⼀个平衡因子(balance factor)的概念，每个结点都有⼀个平衡因子，任何
  结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1，
  AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡， 就像⼀个风向标⼀样。
• 思考⼀下为什么AVL树是高度平衡搜索⼆叉树，要求高度差不超过1，而不是高度差是0呢？0不是更好的平衡吗？画画图分析我们发现，不是不想这样设计，而是有些情况是做不到高度差是0的。⽐如⼀棵树是2个结点，4个结点等情况下，高度差最好就是1，无法作为高度差是0。
• AVL树整体结点数量和分布和完全⼆叉树类似，⾼度可以控制在logN ，那么增删查改的效率也可 以控制在O(logN) ，相⽐⼆叉搜索树有了本质的提升。