《平衡二叉树的建立》由会员分享，可在线阅读，更多相关《平衡二叉树的建立（10页珍藏版）》请在金锄头文库上搜索。
1、平衡二叉树的建立和插入,-基于非递归算法实现By 计科0905 罗苾莹,基本框架,1、一个插入函数-总管插入，当输入一个数据时，先将其插入到应有的位置，按插入路径修改结点的平衡因子(用到栈的数据结构），然后发现不平衡结点，判断是那一种旋转，然后调用旋转函数。 2、四个函数-RL,LR,RR,LL型旋转，并且旋转过后调用高度函数修改三个结点的平衡因子。 3、一个高度函数-求子树高度,算法精髓和遇到的瓶颈,要实现该算法，最大的困难必然是“平衡因子”的修改和各种判断，可以说，整个程序都是围着平衡因子balance在打转。1、插入数据时，平衡因子的修改：使用一个栈q记录插入路径的结点们，插入完后依次出
2、栈，如果先出栈的结点平衡因子变了，判断这个结点是目前栈顶的左孩子还是右孩子，若为左孩子，则栈顶结点的balance+，右孩子则balance-，然后出栈，依次进行下去直到栈空。,2、插入完毕，寻找失衡点：由于插入的时候使用了一个栈s将途径的结点依次入栈，所以插入完后只要依次出栈便可找到失衡点以及旋转点，作出判断。 3.判断完毕，进行旋转：这里是本算法最精髓的地方，经过经验+数学分析，发现每种旋转平衡因子的变化有规律可循，转的时候，哪个子树接哪个结点都是固定的，所以我们只要知道结点的子树高度，就可以求出相应结点的平衡因子。,举例说明,例如 RL型旋转： 于是可以发现，只要求得各个子树的高度我们就
3、能得到旋转之后的平衡因子。如A结点的balance就是Height（B）-Height(F）；A,C,E,D,B,F,G,A,C,E,D,B,F,G,那么，如何求得子树高度呢？int Height(AVLTree T)/创建计算树的高度的函数 并返回高度值 if(T为空)return -1；else return T的左右孩子的Height中较大的一个+1； ,求高度采用的是递归函数，简单可行，但影响效率，可尝试改成非递归。4.旋转完之后，记得清空栈和一些必要的回归处理，否则会各种麻烦。,本算法的优点和缺点,优点 采用非递归算法，效率较高。 通俗易懂缺点 占用内存大 代码较长,后续,其实还有一个想法，就是用一个数组记录所有数据，先对其排序，然后使用折半的思想找出位于中间的结点，作为根，再一次去找左子树的根，右子树的根循环下去。 这样子就不需要旋转，也不需要平衡因子，直接排序就ok了。,谢谢,
