平衡二叉树的建立

1、平衡二叉平衡二叉树的建立和插入树的建立和插入 -基于非递归算法实现基于非递归算法实现 By 计科0905 罗苾莹基本框架基本框架 1、一个插入函数、一个插入函数-总管插入，当输入一个总管插入，当输入一个数据时，先将其插入到应有的位置，按插数据时，先将其插入到应有的位置，按插入路径修改结点的平衡因子入路径修改结点的平衡因子(用到栈的数据用到栈的数据结构），然后发现不平衡结点，判断是那结构），然后发现不平衡结点，判断是那一种旋转，然后调用旋转函数。一种旋转，然后调用旋转函数。 2、四个函数、四个函数-RL,LR,RR,LL型旋转，并且旋型旋转，并且旋转过后调用高度函数修改三个结点的平衡转过后调用高

2、度函数修改三个结点的平衡因子。因子。 3、一个高度函数、一个高度函数-求子树高度求子树高度算法精髓和遇到的瓶颈算法精髓和遇到的瓶颈 要实现该算法，最大的困难必然是要实现该算法，最大的困难必然是“平衡因子平衡因子”的的修改和各种判断，可以说，整个程序都是围着平衡修改和各种判断，可以说，整个程序都是围着平衡因子因子balance在打转。在打转。 1、插入数据时，平衡因子的修改：、插入数据时，平衡因子的修改： 使用一个栈使用一个栈q记录插入路径的结点们，插入完后依次记录插入路径的结点们，插入完后依次出栈，如果先出栈的结点平衡因子变了，判断这个出栈，如果先出栈的结点平衡因子变了，判断这个结点是目前栈顶

3、的左孩子还是右孩子，若为左孩子，结点是目前栈顶的左孩子还是右孩子，若为左孩子，则栈顶结点的则栈顶结点的balance+，右孩子则，右孩子则balance-，然后，然后出栈，依次进行下去直到栈空。出栈，依次进行下去直到栈空。 2、插入完毕，寻找失衡点：、插入完毕，寻找失衡点： 由于插入的时候使用了一个栈由于插入的时候使用了一个栈s将途径的结将途径的结点依次入栈，所以插入完后只要依次出栈点依次入栈，所以插入完后只要依次出栈便可找到失衡点以及旋转点，作出判断。便可找到失衡点以及旋转点，作出判断。3.判断完毕，进行旋转：判断完毕，进行旋转： 这里是本算法最精髓的地方，经过经验这里是本算法最精髓的地方，

4、经过经验+数数学分析，发现每种旋转平衡因子的变化有学分析，发现每种旋转平衡因子的变化有规律可循，转的时候，哪个子树接哪个结规律可循，转的时候，哪个子树接哪个结点都是固定的，所以我们只要知道结点的点都是固定的，所以我们只要知道结点的子树高度，就可以求出相应结点的平衡因子树高度，就可以求出相应结点的平衡因子。子。举例说明举例说明 例如例如 RL型旋转：型旋转： 于是可以发现，只要求得各个子树的高度于是可以发现，只要求得各个子树的高度我们就能得到旋转之后的平衡因子。如我们就能得到旋转之后的平衡因子。如A结结点的点的balance就是就是Height（B）-Height(F）；）； A CEDBFGA

5、CEDBF G那么，如何求得子树高度呢？那么，如何求得子树高度呢？ int Height(AVLTree T)/创建计算树的高度的创建计算树的高度的函数函数 并返回高度值并返回高度值 if(T为空为空) return -1； else return T的左右孩子的的左右孩子的Height中较大的一个中较大的一个+1； 求高度采用的是递归函数，简单可行，但影求高度采用的是递归函数，简单可行，但影响效率，可尝试改成非递归。响效率，可尝试改成非递归。 4.旋转完之后，记得清空栈和一些必要的回旋转完之后，记得清空栈和一些必要的回归处理，否则会各种麻烦。归处理，否则会各种麻烦。本算法的优点和缺点本算法的优点和缺点 优优点点 采用非递归算法，效率较高。采用非递归算法，效率较高。 通俗易通俗易懂懂 缺点缺点 占占用内存大用内存大 代码代码较长较长后续后续 其实还有一个想法，就是用一个数组记录其实还有一个想法，就是用一个数组记录所有数据，先对其排序，然后使用折半的所有数据，先对其排序，然后使用折半的思想找出位于中间的结点，作为根，再一思想找出位于中间的结点，作为根，再一次去找左子树的