平衡二叉树的定义，插入操作以及插入新结点后的调整规则（ALV树）

1.定义

平衡二叉树( Balanced Binary Tree），简称平衡树（AVL树）。

1.特点

树上任一结点的左子树和右子树的高度之差不超过1。
结点的平衡因子=左子树高-右子树高。

2.平衡二叉树的判定

平衡二叉树结点的平衡因子的值只可能是-1、0或1。
只要有任一结点的平衡因子绝对值大于1,就不是平衡二叉树。

3.结点设计

//平衡二叉树结点
typedef struct AVLNode {
    int key;//数据域
    int balance;//平衡因子
    struct AVLNode *lchild, *rchild;
} AVLNode, *AVLTree;
1
2
3
4
5
6

2.插入操作

在二叉排序树中插入新结点后,
查找路径上的所有结点都有可能受到影响，如何保持平衡？

1.插入时导致不平衡的解决方案

1. 引入最小不平衡子树的概念：从插入点往回找到第一个不平衡结点，调整以该结点为根的子树。
2. 在插入操作中，会使最小不平衡子树高度加1，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡。

3.插入新结点后如何调整”不平衡"问题

调整最小不平横子树A的规则

根据二叉排序树的特性:左子树结点值<根结点值<右子树结点值。

1.LL：在A的左孩子的左子树中插入导致不平衡

解决方案：右旋操作：

1.步骤：

• LL平衡旋转（右单旋转）。由于在结点A的左孩子(L)的左子树（L)上插入了新结点，然后A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。
• 将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。

2.RR：在A的右孩子的右子树中插入导致不平衡

解决方案：左旋操作：

1.步骤：

• RR平衡旋转（左单旋转）。
• 由于在结点A的右孩子的右子树上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。
• 将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树。

3.LR：在A的左孩子的右子树中插入导致不平衡

解决方案：先左旋后右旋
例如：若C的左子树插入结点导致不平衡的处理

4.RL：在A的右孩子的左子树中插入导致不平衡

解决方案：先右旋再左旋
例如：在C的子树插入结点的处理

只有左孩子才能右上旋，只有右孩子才能左上旋。

4.查找效率分析

1.推理

• 若树高为h，则最坏情况下，查找一个关键字最多需要对比h次，即查找操作的的时间复杂度不可能超过o(h)。
• 平衡二叉树：树上任一结点的左子树和右子树的高度之差不超过1。
• 假设以nh,表示深度为h的平衡树中含有的最少结点数。
• 则有n0 = 0,n1 = 1, n2 =2，并且有nh = nh-1 + nh-2+ 1

可以证明含有n个结点的平衡二叉树的最大深度为$O(lo{g}_{2}n)$，
平衡二叉树的平均查找长度(即时间复杂度)为$O(lo{g}_{2}n)$.