二叉平衡树（课堂PPT）

1、.1动态查找树表动态查找树表平衡二叉树平衡二叉树平衡二叉树的定义如何构造平衡二叉树平衡二叉树的查找性能分析小结和作业课堂练习程序讲解.2动态查找树表动态查找树表平衡二叉树平衡二叉树LL型LR型RR型RL型应用举例造成不平衡的原因总结.3平衡二叉树平衡二叉树由关键字序列 3 3，1 1，2 2，5 5，4 4构造而得的二叉排序树由关键字序列 1 1，2 2，3 3，4 4，5 5构造而得的二叉排序树，ASL =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5 = 2.2(a)(b)2134535412.4根据不同的关键字输入序列，可以生成各种不同根据不同的关键字输入序列

2、，可以生成各种不同形态的二叉排序树，其性能差别很大形态的二叉排序树，其性能差别很大从（从（a a）图知，其已蜕变成单分支树，平均查找时间）图知，其已蜕变成单分支树，平均查找时间为（为（N+1N+1）/2 /2 与顺序查找相同。与顺序查找相同。所以，含有所以，含有n n个结点的二叉排序树的平均查找长度和个结点的二叉排序树的平均查找长度和树的形态有关。树的形态有关。在某些情况下，需要将二叉排序树进行在某些情况下，需要将二叉排序树进行平衡化平衡化处理，处理，将其调整为将其调整为平衡二叉树平衡二叉树时，来提高它的查找性能。时，来提高它的查找性能。平衡二叉树平衡二叉树.5平衡二叉树平衡二叉树二叉平衡树：

3、又称二叉平衡树：又称AVLAVL树是二叉排序树的另一树是二叉排序树的另一种形式，其特点为：种形式，其特点为：树中每个结点的左、右子树深度之差的绝对值树中每个结点的左、右子树深度之差的绝对值不大于不大于1 1，即，即 。hL-hR 10122054820011平衡因子平衡因子 =1平衡树平衡树.8平衡二叉树的构造平衡二叉树的构造1）新结点插在平衡因子值为）新结点插在平衡因子值为0的结点左或右都不会的结点左或右都不会造成不平衡。造成不平衡。平衡结点平衡结点50左重结点左重结点右重结点右重结点5040555035602）新结点插在平衡因子值为）新结点插在平衡因子值为1的结点的右分支，或者的结点的右分

4、支，或者-1的结点的左分支，的结点的左分支，该结点也不会造成不平衡。该结点也不会造成不平衡。1-1000.9平衡二叉树的构造平衡二叉树的构造3）新结点插在平衡因子值为）新结点插在平衡因子值为1的结点的左分支上，或的结点的左分支上，或者为者为-1的结点的右分支上，此时，该结点的平衡因子的的结点的右分支上，此时，该结点的平衡因子的绝对值大于绝对值大于1，造成二叉排序树不平衡。，造成二叉排序树不平衡。506040453520插入结点插入结点20后，根结点的平衡因子由后，根结点的平衡因子由1变为变为2 10000000112.10平衡二叉树的构造平衡二叉树的构造插入结点插入结点70后，根结点的平衡因子

5、由后，根结点的平衡因子由-1变为变为-2 506040655570-10000000-1-1-2.11平衡二叉树的构造平衡二叉树的构造1.1.LLLL型型新结点插在左重结点新结点插在左重结点a a（ a a是离新结点插入位置最近的左重是离新结点插入位置最近的左重结点地址）的结点地址）的左孩子的左分支左孩子的左分支上。如下图棕色代表新结点，上。如下图棕色代表新结点，称称LLLL型。型。ABBLBRARABBLARh-1h-1h-1h-1ABBLBRARhh-1X平衡二叉排序树平衡二叉排序树插入插入x后不再平衡后不再平衡12.12BR平衡二叉树的构造平衡二叉树的构造1.1.LLLL型调整过程：型调

6、整过程：1 1）将）将BABA向右旋转向右旋转9090度，把度，把B B的右孩子变为的右孩子变为A A的左孩子的左孩子2 2）A A变为变为B B的右孩子，的右孩子，B B带替带替A A的位置。的位置。ABBLBRARhh-1XABBLARhh-1XBAARh重新调整为平衡二叉树重新调整为平衡二叉树20.13平衡二叉树的构造平衡二叉树的构造2.LR型型新结点插在左重结点新结点插在左重结点a（ a是离新结点插入位置最近的左重是离新结点插入位置最近的左重结点地址）的左孩子的结点地址）的左孩子的右孩子的左分支右孩子的左分支上。如下图棕色代表上。如下图棕色代表新结点，称新结点，称LR型。型。1BCRA

7、BBLARh-1CCLh-2h-2h-1h-1BCRABBLARh-1CCLh-2h-1X2-11.14平衡二叉树的构造平衡二叉树的构造2.2.LRLR型调整过程型调整过程-：1.1.将将CBCB向左旋转向左旋转9090度，把度，把CLCL变为变为B B的右子树，把的右子树，把B B变为变为C C的左的左孩子；孩子；h-1BCRABBLARh-1CCLh-2h-1X2-11h-1BCRABLARh-1CCLh-2h-1XBCBLCLXh-1h-1h-1BCRABBLARh-1CCLh-2h-1X2-1122.15平衡二叉树的构造平衡二叉树的构造2.2.LRLR型调整过程型调整过程-：2)2)将

8、将BCABCA向右旋转向右旋转9090度，把度，把C C的右孩子变为的右孩子变为A A的左孩子，的左孩子，A A变为变为C C的右孩子；的右孩子；C C带替带替A A的位置。的位置。CRAARh-1h-2BCBLCLXh-1h-122AARh-1h-2BCBLCLXh-1h-1CARh-1CRA-100.16平衡二叉树的构造平衡二叉树的构造3.RR型型新结点插在右重结点新结点插在右重结点a（ a是离新结点插入位置最近的右重是离新结点插入位置最近的右重结点地址）的结点地址）的右孩子的右分支右孩子的右分支上。如下图棕色代表新结点，上。如下图棕色代表新结点，称称 RRRR型。型。-1AALh-1BR

9、ABBLh-1h-1AALh-1-2BRABBLhh-1X-1.17平衡二叉树的构造平衡二叉树的构造3.3.RRRR型调整过程：型调整过程： 将将BA向左旋转向左旋转90度，把度，把B的左孩子变为的左孩子变为A的右孩子，的右孩子，A变为变为B的左孩子，的左孩子，B带替带替A的位置。的位置。AALh-1-2BRABBLhh-1X-1ALh-1BRABBLhh-1XBALh-1A0.18平衡二叉树的构造平衡二叉树的构造4.RL型型新结点插在右重结点新结点插在右重结点a（ a是离新结点插入位置最近的右重是离新结点插入位置最近的右重结点地址）的右孩子的左孩子的右分支上。如下图棕色代表结点地址）的右孩子

10、的左孩子的右分支上。如下图棕色代表新结点，称新结点，称RL型。型。-10AALh-1BRABCLh-1CRCh-2h-2AALh-1BRABCLh-1CRCh-2Xh-11-2-1.19平衡二叉树的构造平衡二叉树的构造4.4.RLRL型调整过程型调整过程-：1)将将CB向右旋转向右旋转90度，把度，把CR变为变为B的的 左子树，把左子树，把B变为变为C 的右孩子的右孩子AALh-1BRABCLh-1CRCh-2Xh-11-2-1AALh-1BRABCLh-1CRCh-2Xh-1BRBh-1C.20平衡二叉树的构造平衡二叉树的构造4.4.RLRL型调整过程型调整过程-：2)将将BCA向左旋转向左旋转90 度，把度，把C的左孩子变为的左孩子变为A 的右孩子，的右孩子，A变为变为C的左孩子；最后，的左孩子；最后，C带替带替A的位置。的位置。AALh-1ABCLCRh-2Xh-1BRBh-1CAALh-1ABCRh-2Xh-1BRBh-1Ch-1CLAL.21平衡二叉树的构造平衡二叉树的构造ABCX2LLABCX2LRABCX-2