二叉平衡树

动态查找树表—平衡二叉树平衡二叉树的定义如何构造平衡二叉树平衡二叉树的查找性能分析小结和作业课堂练习程序讲解动态查找树表—平衡二叉树LL型LR型RR型RL型应用举例造成不平衡的原因总结平衡二叉树由关键字序列3，1，2，5，4构造而得的二叉排序树由关键字序列1，2，3，4，5构造而得的二叉排序树，ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2(a)(b)2134535412根据不同的关键字输入序列，可以生成各种不同形态的二叉排序树，其性能差别很大从（a）图知，其已蜕变成单分支树，平均查找时间为（N+1）/2与顺序查找相同。所以，含有n个结点的二叉排序树的平均查找长度和树的形态有关。在某些情况下，需要将二叉排序树进行平衡化处理，将其调整为平衡二叉树时，来提高它的查找性能。平衡二叉树平衡二叉树二叉平衡树：又称AVL树是二叉排序树的另一种形式，其特点为：树中每个结点的左、右子树深度之差的绝对值不大于1，即。hL-hR=1平衡二叉树结点的平衡因子：该结点的左子树的深度减去它的右子树的深度平衡二叉树所有结点的平衡因子只可能为：-1，0，1。平衡二叉树54821非平衡树平衡因子10122054820011平衡因子=1平衡树平衡二叉树的构造1）新结点插在平衡因子值为0的结点左或右都不会造成不平衡。平衡结点50左重结点右重结点5040555035602）新结点插在平衡因子值为1的结点的右分支，或者-1的结点的左分支，该结点也不会造成不平衡。1-1000平衡二叉树的构造3）新结点插在平衡因子值为1的结点的左分支上，或者为-1的结点的右分支上，此时，该结点的平衡因子的绝对值大于1，造成二叉排序树不平衡。506040453520插入结点20后，根结点的平衡因子由1变为210000000112平衡二叉树的构造插入结点70后，根结点的平衡因子由-1变为-2506040655570-10000000-1-1-2平衡二叉树的构造1.LL型新结点插在左重结点a（a是离新结点插入位置最近的左重结点地址）的左孩子的左分支上。如下图棕色代表新结点，称LL型。ABBLBRARABBLARh-1h-1h-1h-1ABBLBRARhh-1X平衡二叉排序树插入x后不再平衡12BR平衡二叉树的构造1.LL型调整过程：1）将BA向右旋转90度，把B的右孩子变为A的左孩子2）A变为B的右孩子，B带替A的位置。ABBLBRARhh-1XABBLARhh-1XBAARh重新调整为平衡二叉树20平衡二叉树的构造2.LR型新结点插在左重结点a（a是离新结点插入位置最近的左重结点地址）的左孩子的右孩子的左分支上。如下图棕色代表新结点，称LR型。1BCRABBLARh-1CCLh-2h-2h-1h-1BCRABBLARh-1CCLh-2h-1X2-11平衡二叉树的构造2.LR型调整过程----①：1.将CB向左旋转90度，把CL变为B的右子树，把B变为C的左孩子；h-1BCRABBLARh-1CCLh-2h-1X2-11h-1BCRABLARh-1CCLh-2h-1XBCBLCLXh-1h-1h-1BCRABBLARh-1CCLh-2h-1X2-1122平衡二叉树的构造2.LR型调整过程----②：2)将BCA向右旋转90度，把C的右孩子变为A的左孩子，A变为C的右孩子；C带替A的位置。CRAARh-1h-2BCBLCLXh-1h-122AARh-1h-2BCBLCLXh-1h-1CARh-1CRA-100平衡二叉树的构造3.RR型新结点插在右重结点a（a是离新结点插入位置最近的右重结点地址）的右孩子的右分支上。如下图棕色代表新结点，称RR型。-1AALh-1BRABBLh-1h-1AALh-1-2BRABBLhh-1X-1平衡二叉树的构造3.RR型调整过程：将BA向左旋转90度，把B的左孩子变为A的右孩子，A变为B的左孩子，B带替A的位置。AALh-1-2BRABBLhh-1X-1ALh-1BRABBLhh-1XBALh-1A0平衡二叉树的构造4.RL型新结点插在右重结点a（a是离新结点插入位置最近的右重结点地址）的右孩子的左孩子的右分支上。如下图棕色代表新结点，称RL型。-10AALh-1BRABCLh-1CRCh-2h-2AALh-1BRABCLh-1CRCh-2Xh-11-2-1平衡二叉树的构造4.RL型调整过程-----①：1)将CB向右旋转90度，把CR变为B的左子树，把B变为C的右孩子AALh-1BRABCLh-1CRCh-2Xh-11-2-1AALh-1BRABCLh-1CRCh-2Xh-1BRBh-1C平衡二叉树的构造4.RL型调整过程-----②：2)将BCA向左旋转90度，把C的左孩子变为A的右孩子，A变为C的左孩子；最后，C带替A的位置。AALh-1ABCLCRh-2Xh-1BRBh-1CAALh-1ABCRh-2Xh-1BRBh-1Ch-1CLAL平衡二叉树的构造ABCX2LLABCX2LRABCX-2RRABCX-2RL平衡二叉树的构造例如:依次插入关键字5,4,2,8,6,95424258665842向右旋转一次先向右旋转再向左旋转平衡二叉树的构造42658942689向左旋转一次继续插入关键字95