AVL树仍然是一棵二叉查找树。
平衡是指对AVL树的任意结点来说，其左子树和右子树的高度之差的绝对值不超过1。
平衡因子是指左子树和右子树的高度之差。
因此需要在树的结构中加入一个变量height
左旋的三个步骤：
①让B的左子树成为A的右子树
②让A成为B的左子树
③将根结点设定为结点B
右旋则把左旋代码里的lchild改为rchild，rchild改为lchild就行了
LL、LR、RR、RL：
在这个基础上，由于需要从插入的结点开始从下往上判断结点是否平衡，因此需要在每个insert函数之后更新当前子树的高度，并在这之后根据树型是LL型、LR型、RR型、RL型之一来进行平衡的操作：
网友评论