AVL树插入新节点后,需要从新插入节点开始向上回溯,依次检查祖先节点的平衡因子。当找到第一个平衡因子绝对值大于等于2的节点时,该节点称为失衡节点A。然后根据新插入节点相对于A的插入路径判断失衡类型:若在A的左子树的左子树中,为LL型;若在A的右子树的右子树中,为RR型;若在A的左子树的右子树中,为LR型;若在A的右子树的左子树中,为RL型。确定类型后进行旋转调整:LL型对A的L孩子进行右旋,RR型对A的R孩子进行左旋;LR型先对A的L孩子的R孩子进行左旋,再对A的L孩子得R孩子进行右旋进行右旋;RL型先对A的R孩子的L孩子进行右旋,再对A的R孩子的L孩子进行左旋。旋转完成后,重新恢复AVL树的平衡。
设 n\_h 表示深度为 h(根结点深度为 1)的平衡二叉树中所含的最少结点数。 最多结点数即对应的满二叉树情况
$$ n_0 = 0,\quad n_1 = 1,\quad n_2 = 2,\quad n_h = n_{h-2} + n_{h-1} + 1 $$