平衡二叉树的插入

平衡二叉树的概念：

在学习二叉排序树的查找时，通过分析查找算法的效率可知，不同结构的二叉排序树查找效率有很大的不同，单支树的查找效率相当于顺序查找，而越趋于平衡的二叉排序树查找效率越高。因此，在二叉排序树的基础上引进了平衡二叉树。

所谓平衡二叉树是指它除了具备二叉排序树的基本特性之外，还具有一个非常重要的特点：它的左子树与右子树的深度之差（平衡因子）的绝对值不超过1，且都是平衡二叉树。二叉树结点的左子树深度减去右子树深度的值称为平衡因子。那么平衡二叉树上的所有结点的平衡因子只可能是-1，0，1。只要二叉树上一个结点的平衡因子的绝对值大于1，那么该二叉树就不是平衡二叉树。

例如：
平衡二叉树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法）。

平衡二叉树也可以进行查找，插入等操作，在进行查找操作时与二叉排序树相同且效率比二叉排序树高，如果平衡二叉树平衡度高，则相当于是顺序表中的折半查找。

但在执行插入操作时，要随时注意保持树的平衡性，在插入结点时，如果距离插入位置最近且平衡因子绝对值大于1，以此为根结点的子树称为最小不平衡子树。

平衡二叉树的插入：

在平衡二叉树中插入结点要随时保证插入后整棵二叉树还是平衡的，但是在插入结点的时候，会破坏二叉树的平衡性，会产生最小不平衡子树。因此，为了保证插入结点后二叉树仍是平衡的，就需要找出插入新结点后失去平衡的最小子树根结点。然后再调整这棵子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，其他所有不平衡子树无须调整，整个二叉排序树就又称为一棵平衡二叉树。调整结点之间的链接关系的基本方法就是旋转，也有书中称之为结点交换。

旋转的方法有右旋转，左旋转，左右旋转，右左旋转，接下来用一组数据构建一棵平衡二叉树，在构建过程中讲解如何用旋转来调整二叉树的平衡。

假设有一组数据int arr[10]={90,66,65,98,100,88,105,102,110,103};现要用这组数据来构建一棵平衡二叉树，以90为根结点，下一个数据66小于90，则为它的左孩子，此时两个结点构成的二叉树是一棵平衡二叉树；然后插入结点65,65小于66，则为66的左孩子。

结点左边是每个结点的平衡因子，当插入结点65后，结点90的平衡因子变为2，此树不再是平衡二叉树，那么为了保持树的平衡性，就要对树进行调整，即进行旋转。在进行旋转时也有一定的规则：在产生的最小不平衡子树的根结点及其左子树平衡因子都为正，即在最小不平衡子树根结点的左孩子的左孩子处插入结点，则以根结点的左孩子为支点进行右旋转。66为根结点90的左孩子，而结点65就是插入到了结点66的左孩子处，根结点90与左孩子结点66的平衡因子都同为正，因此要调整二叉树的平衡就以66为支点进行右旋转。

如图所示：前三个结点

右旋转

旋转之后二叉树就变为以66为根结点，以65和90分别为左右孩子的平衡二叉树。

接着再插入结点98，则98会成为结点90的右孩子。

插入结点98之后并没有打破二叉树的平衡性，因此不需要调整。接下来再插入结点100，则100成为98的右孩子。

插入结点98和插入结点100

插入结点100后打破了二叉树的平衡性，产生的最小不平衡子树以90为根结点。此时要调整树的平衡性，但是此次插入结点在90右孩子的右孩子98处插入，结点90及其右孩子平衡因子都为负，因此需要左旋转。左旋转规则为：在产生的最小不平衡子树根结点右孩子的右孩子处插入结点，即最小不平衡子树的根结点及其右孩子的平衡因子都为负，则以根结点的右孩子为支点进行左旋转，将结点90变为其左孩子。

左旋转之后，结点98变为了66的右孩子，结点90变为了结点98的左孩子，整棵树又恢复了平衡。需要注意的是，如果插入结点不是98的右孩子而是其左孩子，例如插入的结点值为97。这样如果直接进行简单的左旋转，则97会变成98的右孩子，就不符合二叉排序树的性质，因此不能简单地直接左旋转。

仔细观察会发现结点90与结点结点98的平衡因子符号不同，因此不能简单旋转。在旋转之前可以先将两者符号统一，先对结点98与97进行右旋转，使98成为97的右孩子。

这样就与二叉平衡性一样，此时可以直接进行左旋转。

此处为将100用97替换所出现的情况，如果在插入过程中出现平衡因子符号不同的情况，读者也要知道如何处理。

接下来插入结点88之后，则88会成为90的左孩子。

插入结点88之后，也打破了树的平衡性。产生的最小不平衡子树以66为根结点。66的平衡因子为负，其右孩子98的平衡因子为正，两者的符号不同，因此旋转方式也会改变。先要取消平衡因子符号的差异，当产生的最小不平衡子树中，从根结点的插入路径为右->左->左时，先要以此根结点的右孩子的左孩子为支点进行旋转，然后再进行左旋转。在下图中，产生的最小不平衡子树以66为根结点，则从66到插入的结点88的路径就是右->左->左，那么就先绕结点90（它为根结点66右孩子的左孩子）进行右旋转。

经过右旋转之后，结点66与结点90的平衡因子符号相同，最小不平衡子树的根结点与其右子树的平衡因子因子都为负，按照规则绕结点90进行左旋转，结点66变为90的左孩子，结点88变为66的右孩子。

插入结点88，根据插入的位置及平衡因子先进行右旋转再进行左旋转，调整树的平衡。

接下来插入结点105,105为100的右孩子，生成的最小不平衡子树以98为根结点，根结点与其右孩子平衡因子同为负，则绕结点100进行左旋转来调整二叉平衡树。

接下来插入结点102,102为105的左孩子。

插入结点102后并没有破坏二叉树的平衡性。 继续插入结点110,110为105的右孩子。

插入结点110也没有破坏树的平衡性，因此不必要调整。接下来插入结点103，则103为102的右孩子。

插入结点103后，产生的最小不平衡子树以100为根结点，结点100的平衡因子为-2，结点105的平衡因子为1，平衡因子符号不统一。那么首先要消除平衡因子间符号的差异，绕结点102右旋转。

此时再绕结点102左旋转来调整树的平衡性。

经过左旋转后，得到右边的二叉树，它已经是平衡的，至此用这一组数据构建一棵平衡二叉树完成。

在构建的过程中插入结点时要随时保持树的平衡性，通过上面的学习可知，构建平衡二叉树大致就分为三种情况：插入结点后，如果最小不平衡子树根结点与其孩子平衡因子通为正，则直接右旋转；如果最小不平衡子树根结点与其孩子平衡因子通为正，则直接左旋转；如果最小不平衡子树根结点与其孩子平衡因子符号不同，则先对孩子结点进行旋转，使平衡因子符号无差异，再进行反向旋转。