平衡树和AVL

前面我们讲过二分搜索树，二分搜索树在某些情况下会退化成链表，比如它存入的数据从小到大排好序的：[1, 2, 3, 4, 5]

AVL 树得名于它的发明者 G. M. Adelson-Velsky 和 E. M. Landis，是他们两个人名字的缩写。他们在 1962 年的论文中发表了它。

AVL 树本质上还是一棵二分搜索树，只不过它每个节点左右子树的高度差的绝对值（平衡因子）不能超过 1。细心的朋友可能看到了 平衡因子 这个词，大家不要怕，这个词看着挺高端，实际就是节点左右子树高度差的绝对值而已。

下面这颗树就不是一个 AVL 树，因为节点 12 和 节点 8 他们之间的高度差绝对值为 2：

计算节点的高度和平衡因子

检查二分搜索树性质和平衡性