平衡二叉树(AVL树)

AVL树仍然是一棵二叉查找树。

平衡是指对AVL树的任意结点来说，其左子树和右子树的高度之差的绝对值不超过1。

平衡因子是指左子树和右子树的高度之差。

因此需要在树的结构中加入一个变量height

左旋的三个步骤：

①让B的左子树成为A的右子树

②让A成为B的左子树

③将根结点设定为结点B

右旋则把左旋代码里的lchild改为rchild，rchild改为lchild就行了

LL、LR、RR、RL：

在这个基础上，由于需要从插入的结点开始从下往上判断结点是否平衡，因此需要在每个insert函数之后更新当前子树的高度，并在这之后根据树型是LL型、LR型、RR型、RL型之一来进行平衡的操作：