1.平衡二叉树的概念

平衡二叉树又称为AVL树，是一种特殊的二叉排序树。其左右子树都是平衡二叉树，且左右子树高度之差的绝对值不超过1。一句话表述为：以树中所有结点为根的树的左右子树高度之差的绝对值不超过1。

注意：平衡二叉树首先是二叉排序树。原因是有人先发明了二叉排序树，实现了较高的查找效率。后来发现基于这种查找方法，树越矮查找效率越高，进而又发明了平衡二叉树。平衡二叉树是二叉排序树的改进，因此它是二叉排序树。

为了判断一棵二叉排序树是否是平衡二叉树，引进了平衡因子的概念。平衡因子是针对树中的结点来说的，一个结点的平衡因子为其左子树的高度减去右子树高度的差。对于平衡二叉树，树中的所有结点的平衡因子的取值只能是-1、0、1三个值。

2.平衡二叉树的建立

建立平衡二叉树的过程和建立二叉排序树的过程基本一样，都是将关键字逐个插入空树中的过程。所不同的是，在建立平衡二叉树的过程中，每插入一个新的关键字都要进行检查，看是否新关键字的插入会使得原平衡二叉树失去平衡，即树中出现平衡因子绝对值大于1的结点。如果失去平衡则需要进行平衡调整。本节的重点就是平衡调整，这同样也是考研的重点。

3.平衡调整

假定向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性，则首先要找出插入新结点后失去平衡的最小子树，然后再调整这棵子树，使之成为平衡子树。值得注意的是，当失去平衡的最小子树被调整为平衡子树后，无须调整原有其他所有的不平衡子树，整个二叉排序树就会成为一棵平衡二叉树。所谓失去平衡的最小子树是以距离插入结点最近，且以平衡因子绝对值大于1的结点作为根的子树，又称为最小不平衡子树。

当然，平衡调整必须保持排序二叉树左小右大的性质，平衡调整有4种情况，分别为LL型、RR型、LR型和RL型。下面通过一个例题来综合体会一下平衡二叉树的建立、平衡调整以及关键字的删除过程。

【例9-3】 以关键字序列{16，3，7，11，9，26，18，14，15}构造一棵AVL树（平衡二叉树），构造完成后依次删除结点16、15、11。给出详细操作过程，题目中在结点上方标出平衡因子，用虚线框出需要进行平衡调整的3个结点。

（1）建立二叉树

1）插入结点16。此时树空，可直接插入，如图9-6a所示。

2）插入结点3。3比16小，从根结点向左走找到插入位置后插入，没有发生不平衡现象，如图9-6b所示。

3）插入结点7。按照二叉排序树查找方法找到插入位置后插入，如图9-6c中左图所示。插入7后出现不平衡现象，此时失去平衡的最小子树根结点为16，进行平衡调整，将7作为根结点，3和16分别为其左、右孩子结点，这样仍能保持根大于左小于右的特性，这里进行的是LR调整。LR调整结果如图9-6c中右图所示。

4）插入结点11。没有发生不平衡现象，如图9-6d所示。

图9-6a 插入结点16

图9-6b 插入结点3

图9-6c 插入结点7并进行LR调整

图9-6d 插入结点11

5）插入结点9，如图9-6e中左图所示。插入9后出现了不平衡现象，此时失去平衡的最小子树根结点为16。由图中虚线框内的结点可以看出，将11作为根结点，9和16分别作为其左、右孩子结点同样满足根大于左小于右的特性，这里进行的是LL调整。LL调整结果如图9-6e中右图所示。

6）插入结点26，如图9-6f中左图所示。插入26后出现了不平衡现象，此时失去平衡的最小子树根结点为7。由图中虚线框内的结点可以看出，将11作为根结点，7和16分别作为其左、右孩子结点同样满足根大于左小于右的特性，这里进行的是RR调整。这样处理后，结点7的右子树变为空，可以将结点9连接在结点7的右子树上。调整后的结果如图9-6f中右图所示。

图9-6e 插入结点9并进行LL调整

图9-6f 插入结点26并进行RR调整

7）插入结点18，如图9-6g中左图所示。插入18后出现了不平衡现象，此时失去平衡的最小子树根结点为16。由图中虚线框内的结点可以看出，将18作为根结点，16和26分别作为其左、右孩子结点同样满足根大于左小于右的特性，这里进行的是RL调整。RL调整结果如图9-6g中右图所示。(www.daowen.com)

8）插入结点14，没有发生不平衡现象，如图9-6h所示。

图9-6g 插入结点18并进行RL调整

图9-6h 插入结点14

9）插入结点15，如图9-6i中左图所示。插入15后出现了不平衡现象，此时失去平衡的最小子树根结点为16。由图中虚线框内的结点可以看出，将15作为根结点，14和16分别作为其左、右孩子结点同样满足根大于左小于右的特性，这里进行的是LR调整。LR调整结果如图9-6i中右图所示。至此，平衡二叉树建立完成。

（2）删除结点

1）删除结点16。因结点16是叶子结点，应按照删除操作的第一种情况来处理：直接删除，结果如图9-6j所示。

图9-6i 插入结点15并进行LR调整

图9-6j 删除结点16

2）删除结点15。结点15含有一棵子树，因此应按照删除操作的第二种情况来处理：删除结点15，并将结点15的子树根连接在15与其双亲结点相连的指针上，结果如图9-6k所示。

3）删除结点11。结点11含有两棵子树，因此应按照删除操作的第三种情况来处理：沿着结点11的左子树根一直往右走，最终来到结点9，因结点9是叶子结点，这样就转化成了删除操作的第一种情况，将结点9直接删除。然后将关键字11用关键字9来代替，结果如图9-6l所示。

图9-6k 删除结点15

图9-6l 删除结点11

（3）平衡调整过程总结

通过上边的例题可以总结如下4种可能发生不平衡的情况以及调整方法：

1）如图9-7a所示，某时刻在b的左子树Y上插入一个结点，导致a的左子树高度为h+2，右子树高度为h，发生不平衡。此时应该将a下移一个结点高度，b上移一个结点高度，也就是将b从a的左子树取下，然后将b的右子树挂在a的左子树上，最后将a挂在b的右子树上以达到平衡，如图9-7b、c所示。这就是LL调整，也叫右单旋转调整。如果b在a的右子树上，且插入的新结点在b的右子树上，即与图9-7a对称的情况，则此时只需将上述步骤中的左换成右，右换成左，做对称处理即可。这种调整叫RR调整，也叫左单旋转调整。

图9-7 LL调整过程

2）如图9-8a所示，某时刻在b的右子树Y上插入一个结点导致不平衡。此时需要将子树Y拆分成两个子树U和V（见图9-8b），根结点为c，并将b的右子树、a的左子树和c的左右子树都取下，如图9-8c所示。然后将c作为a和b两棵子树的根，b为左子树，a为右子树，c原来的左子树U作为b的右子树，c原来的右子树V作为a的左子树以达到平衡，如图9-8d所示。这就是LR调整，也叫先左后右双旋转调整。如果b在a的右子树上，且插入的结点在b的左子树上，即与图9-8a对称的情况，则此时只需将上述过程做左右对称处理即可。这种调整叫RL调整，也叫先右后左双旋转调整。

图9-8 LR调整过程

说明：图9-8b中显示的导致发生不平衡的结点落在子树U上只是一种情况，还可能落在V上，处理方法不变。

说明：1）和2）中所出现的调整方式的命名：LL、RR、LR、RL，并不是对调整过程的描述，而是对不平衡状态的描述。如LL（Left-Left）调整，即新插入结点落在最小不平衡子树根结点的左（L）孩子的左（L）子树上，如图9-7a图所示，对这种不平衡状态进行调整称之为LL调整。又如LR调整（Left-Right），即新插入结点落在最小不平衡子树根结点的左（L）孩子的右（R）子树上，如图9-8a所示，对这种不平衡状态进行调整称之为LR调整。因此大家要在脑子里建立一个这4个名称到不平衡状态的一一映射，而不是到调整过程的一一映射。知道这个可以在做题时减少思维量，提高做题速度。在考研数据结构题目中，常常问某种不平衡状态下应采用何种调整方式，从LL、RR、LR、RL中选其一，其实问的就是出现了哪种不平衡状态。如果你在脑子里建立的是4个名称到不平衡状态的一一映射，就可以直接选出答案。如果你在脑子里建立的是4个名称到调整方式的一一映射，则会在脑子里过一遍调整过程才能选出答案。