【数据结构】平衡二叉树(AVL树)

平衡二叉树(AVL树)：它或者是一棵空树;或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是 -1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

　　下面即四种情况分别为：左左、右右、左右、右左，每种情况又有两个图①、②，①是该情况的最简单的图形，②是该情况的一般的图形。

　　设x为最小不平衡子树的根结点，y为刚插入的点

　　左左：即在x的左孩子a的左孩子c上插入一个结点y(该结点也可以是c,如图①)，即y可以是c，也可以是c的左孩子(如图②)，也可以是c的右孩子(不在画出)。

　　图①就不用说了，结点x和结点a变换，则树平衡了;那么图②就是树中的一般情况了a结点有右孩子d，那要进行x和a变换，那么a的右孩子放哪啊?很简单，如图放在x的左孩子上;分析：x>d,d>a,所以d可作为x的左孩子，且可作为a的右孩子中的孩子。下边这样的类似情况不再分析，自己分析分析。

　　实现：找到根结点x，与它的左孩子a进行交换即可使二叉树树再次平衡;

　　右右：即在x的右孩子a的右孩子c上插入一个结点y(该结点也可以是c,如图①)，即y可以是c，也可以是c的右孩子(如图②)，也可以是c的左孩子(不在画出)。

　　实现：找到根结点x，与它的右孩子a进行交换即可使二叉树树再次平衡;

　　左右：即在x的左孩子a的右孩子c上插入一个结点y(该结点也可以是c,如图①)，即y可以是c，也可以是c的右孩子(如图②)，也可以是c的左孩子(不在画出)。

　　这个左右和下边的右左，稍微复杂了点，需要进行两次交换，才能达到平衡，注意这时y是c的右孩子，最终y作为x的左孩子;若y是c的左孩子，最终y作为a的右孩子，画图分析一下~~下边类似，不再敖述。

　　实现：找到根结点x，让x的左孩子a与x的左孩子a的右孩子c进行交换，然后再让x与x此时的左孩子c进行交换，最终达到平衡;

　　右左：即在x的右孩子a的左孩子c上插入一个结点y(该结点也可以是c,如图①)，即y可以是c，也可以是c的右孩子(如图②)，也可以是c的左孩子(不在画出)。

        实现：找到根结点x，让x的右孩子a与x的右孩子a的左孩子c进行交换，然后再让x与x此时的右孩子c进行交换，最终达到平衡;

　　上边的四种情况包含了所有插入时导致不平衡的情况，上面给出的仅仅是一棵大树中的最小不平衡子树，一定要想清楚，别迷了!另外一定要注意这个交换操作，比如a与b交换(a在上，b在下)，b一定要占据a的位置!什么意思?就是b要放在(覆盖)储存a的那块内存上，再通俗点说，若a是x的左孩子，则交换后b要做x的左孩子;这就是所谓的b占据a的位置!

来源于网络

20考研的QQ群，有各个学校的考研资料，欢迎加入

群号是 984844252

您还可以在以下平台找到我们

你点的每个在看，我都认真当成了喜欢