为了保证树的高度，也就出现了如下的平衡二叉树，例如 AVL Tree、Red-Black Tree 等，两者都是针对可能出现的不同场景进行调整，从而达到了平衡状态，但是两者处理不平衡状态都不太好记忆，而且死板。

这里先介绍下自平衡二叉树的实现。

简介 #

自平衡二叉查找树 (AVL Tree) 中任意节点的两个子树的高度差最大为 1，查找、插入和删除在平均和最坏情况下都是 O(log n)，插入和删除可能需要通过一次或多次树旋转来重新平衡这个树。

该平衡二叉树得名于其发明者 G.M. Adelson-Velsky 和 E.M. Landis，在 1962 年的论文《An algorithm for the organization of information》有相关的介绍。

相比红黑树来说 AVL 树要更加平衡一些，带来的问题就是插入和删除比较慢，但是查询的速度会更快一些。

平衡因子 #

每个节点会保存树的高度信息，当前节点高度会选择左右节点较高的值加一计算得到，然后每个节点可以根据高度计算一个平衡因子 (Balance Factor)，可以采用左子树的高度减去右子树的高度。

当平衡因子为 1、0 或 -1 时，该节点被认为是平衡的，而 -2、2 的节点被认为是不平衡，就需要重新平衡这个树。

为了保持平衡，AVL Tree 可能需要执行四种的旋转方式。

旋转 #

旋转的逻辑很简单，每次旋转完之后需要更新节点的高度，介绍如下。

向左旋转 #

此时右侧不平衡，需要向左旋转。

向右旋转 #

此时左侧不平衡，需要向右旋转。

左右旋转 #

右左旋转 #

总结 #

实际实现只需要向左和向右旋转即可，而左右、右左旋转直接调用上述的接口即可。