平衡二叉树的建立.ppt

文档介绍：平衡二叉树的建立和插入----- 基于非递归算法实现 By 计科 0905 罗苾莹基本框架?1、一个插入函数---总管插入,当输入一个数据时,先将其插入到应有的位置,按插入路径修改结点的平衡因子(用到栈的数据结构),然后发现不平衡结点,判断是那一种旋转,然后调用旋转函数。?2、四个函数---RL,LR,RR,LL 型旋转,并且旋转过后调用高度函数修改三个结点的平衡因子。?3、一个高度函数---求子树高度算法精髓和遇到的瓶颈?要实现该算法,最大的困难必然是“平衡因子”的修改和各种判断,可以说,整个程序都是围着平衡因子 balance 在打转。 1、插入数据时,平衡因子的修改: 使用一个栈 q记录插入路径的结点们,插入完后依次出栈,如果先出栈的结点平衡因子变了,判断这个结点是目前栈顶的左孩子还是右孩子,若为左孩子,则栈顶结点的 balance++ ,右孩子则 balance-- ,然后出栈,依次进行下去直到栈空。 2、插入完毕,寻找失衡点: 由于插入的时候使用了一个栈 s将途径的结点依次入栈,所以插入完后只要依次出栈便可找到失衡点以及旋转点,作出判断。 ,进行旋转: 这里是本算法最精髓的地方,经过经验+数学分析,发现每种旋转平衡因子的变化有规律可循,转的时候,哪个子树接哪个结点都是固定的,所以我们只要知道结点的子树高度,就可以求出相应结点的平衡因子。举例说明?例如 RL型旋转: ?于是可以发现,只要求得各个子树的高度我们就能得到旋转之后的平衡因子。如 A结点的 balance 就是 Height (B) -Height(F ); ?A? CE D BFG ACE DBFG 那么,如何求得子树高度呢? int Height(AVLTree T)/