数据结构第六章 平衡树.doc

6.5平衡二叉树平衡二叉树（balanced binary tree）是对二叉搜索树的一种改进。二叉搜索树有一个缺点，那就是树的结构事先无法预料，随意性很大，它只与结点的值和插入次序有关，往往得到的是一棵很不“平衡”的二叉树。二叉搜索树与理想平衡树相差越远，树的高度就越高，其运算时间就越长，在最坏的情况下，就是对单链表进行运算的时间，其时间复杂度由O(n)变为O(n)，从而部分或全部地丧失了利用二叉搜索树组织数据的优点。为了克服二叉搜索树的这个缺点，需要在插入和删除结点时对树的结构进行必要的调整，使二叉搜索树始终处于一种平衡的状态，即始终成为一种平衡二叉树(balanced binary tree)，简称平衡树。当然它不是理想平衡树，因为那将使调整操作更为复杂，使调整带来的好处得不偿失。本节将首先讨论平衡树的定义和调整操作，然后讨论B_树的定义以及查找、插入和删除等运算。6.5.1平衡二叉树的定义平衡二叉树简称平衡树是由阿德尔森一维尔斯基和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。平衡树的定义是：若一棵二叉树中每个结点的左、右子树的高度至多相差，则称此树为平衡树。我们把二叉树中每个结点的左子树高度减去右子树的高度定义为该结点的平衡因子(balance factor)，因此，平衡树中每个结点的平衡因子只能是1,0或-1。图7-6(a)是一棵平衡树，图7-6(b)和图7-6(c)分别是一棵非平衡树，每个结点的上方所标数字为该结点的平衡因子。虽然平衡树的平衡性比理想平衡树要差一些，但理论上已经证明：具有n个结点的平衡树的高度在任何情况下决不会比具有相同结点数的理想平衡树高出45%以上。因此，在平衡树上进行查找运算虽比理想平衡树要慢一些，但通常比任意生成的二叉搜索树快得多，当然，其时间复杂度的数量级表示仍为O(n). 1 2 36 -1 15-1 -1 -2 20 -1 48 0 10 -232 0 0 0 016 2 30 0 650 5 012 1 60 0 0 0 28 0 45 0 25 (a)平衡 (b) 非平衡 (c)非平衡图7-6 带平衡因子的二叉树当向一棵平衡树插入一个新结点时，若插入后，某些结点的左、右子树的高度不变，则就不会影响这些结点的平衡因子，因而也不会因为这些造成不平衡；若插入后某些结点的左子树高度增加（右子树高度增加的情况与之类似），则就影响了这些结点的平衡因子，具体又分为三种情况：(1)若插入前一部分结点的左子树高度为h与右子树的高度h相等，即平衡因子为，则插入后将使平衡因子变为，但仍符合平衡的条件，不必对它们加以调整；(2)若插入前一部分结点的h小于h，即平衡因子为-1，则插入后将使平衡因子变为，平衡更加改善，不必对它们进行调整；(3)若插入前一部分结点的h大于h，即平衡因子为，则插入后将使平衡因子变为，破坏了平衡树的限制条件，需对它们加以调整，使整个二叉搜索树恢复为平衡树。若插入后，某些结点的右子树高度增加，则也分为相应的三种情况，对于第(1)种情况，平衡因子将由变为-1，不必进行调整；对于第(2)种情况是平衡因子由-1变为-2，则必须对它们进行调整；对于第(3)种情况是平衡因子由变为，平衡更加改善，也不必进行调整。假定向平衡树中插入一个结点后破坏了其平衡性，则首先要找出唯一一棵最小不平衡子树，然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当然，调整后该子树的二叉搜索树性质要不变，即调整前后得到的中序序列要完全相同。稍后便知，最小不平衡子树调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉搜索树就又成为一棵平衡树。所谓最小不平衡子树是指以离插入结点最近，且平衡因子绝对值大于的结点作为根的子树。如在图7-6(b)中，以值为30的结点作根的子树是该树的最小不平衡子树，分别以20和36作为根的不平衡子树不是最小不平衡子树；在图7-6(c)中，以值为32的结点作根的子树是该树的最小不平衡子树，当然它也是唯一一棵不平衡子树。为了便于讨论，不妨设最小不平衡子树的根结点用表示，则调整该子树的操作可归纳为下列四种情况：(1)LL型调整操作它是因在结点的左(left)孩子（假定用B表示）的左(left)子树上插入结点，使得A结点的平衡因子由1变为2而引起的不平衡所进行的调整操作。调整过程如图7-7所示，图中用长方框表示子树，用长方框的高度表示子树的高度，用带阴影的小方框表示被插入的结点。图7-7(a)为 插入前的平衡子树，、和的子树高度均为h(h0，若h=0，则它们均为空树)，A结点和B结点的平衡因子分别为1和0。图7-7(b)为在B的左子树上插入一个新结点，以A为根的子树成为最小不平衡子树的情况。图7-7(c)为调整后成为新的平衡平衡子树的情况，调整规则是：将A的左孩子B向右旋转代替成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为结点的左子树。此调整过程需要修改三个指针，如图7-7(c)中的箭头所示，一是将原指向结点的指针修改为指向结点，二是将孤右指针修改为指向结点，三是将的左指针修改为指向的原右子树的根结点；另外，还需要修改和结点的平衡因子，应均被置为0。从图7-7可以看出，调整后对应的中序序列相同，即为BA，所以经调整后仍保持了二叉搜索树的性质不变。 1 50 2 50 0 450 45 0 60 1 45 0 60 1 30 0 500 30 0 48 0 30 0 48 0 20 0 48 0 60 0 20 (d)插入前 (e)插入20后 (f)调整后 1 2 0 A A B 0 1 0 B B A h h+1 插入前, , 为h 中序为BA (a)插入前 (b)插入后 (c)调整后 1 10 2 10 1 10 1 9 0 12 2 9 0 12 0 6 0 12 0 6 1 6 0 3 0 9 0 3 (a)插入前 (b)插入3后 (c)调整后 1 50 2 50 0 45 0 45 0 60 1 45 0 60 1 30 0 50 0 30 0 48 0 30 0 48 0 20 0 48 060 0 20 (d)插入前 (e)插入20后 (f)调整后 图7-8 LL调整实例图7-8是LL型调整的两个实例，其中图7-8中的(a)、(b)、(c)为一例，此处A结点为9，B结点为6，、均为空树；图7-8的(d)、(e)、(f)为另一例，此处A结点为50，B结点为45，、分别为只含有一个结点30、48、60的子树。(2)RR型调整操作它是因在A结点的右(Right)孩子（假定用B表示）的右(Right)子树上插入结点，使得A结点的平衡因子由-1变为-2而引起的不平衡所进行的调整操作。调整过程如图7-9所示。图7-9(a)为插入前的平衡子树，、子树的高度相同，均为h(h0)，A结点和B结点的平衡因子分别为-1和0；图7-9(b)为在B结点的右子树上插放一个新结点，使以A根的子树成为最小不平衡子树的情况；图7-9(c)为调整后重新恢复平衡的情况。调整是：将A的右孩子B向左上 -1 -2 0 A A B 0 -1 0 h B B A h h+1 插入前, , 为h 中序为AB (a)插入前 (b)插入后 (c)调整后7-9 RR型调整操作示意图旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树。此调整过程同LL型调整过程对称，要修改的三个指针如图7-9(c)中的箭头所示。 同样，进行RR型调整前后，仍保持着二叉搜索树的性质不变。(3)LR型调整操作它是因在A结点的左(Left)孩子（假定用B表示）的右(Right)子树上插入结点，使得A结点的平衡因子由1变为2而引起的不平衡所进行的调整操作。调整过程如图7-10所示。图7-10(a)为插入前的平衡子树，和子树的高度均为h(h0)，和子树的高度均为h+1，尤其是当和子树为空树时，则B结点的右子树也同时为空，此时C结点将是被插入的新结点；插入前结点和结点的平衡因子分别为和，若存在，则结点的平衡因子为。图7-10(b)为在B结点的右子树上插入一个新结点（当B的右子树为空时，则为C结点，否则为C的左子树或右子树上带阴影的结点，图中给出在左子树上插入的情况，若在右子树上插入，情况类似），使得以A为根的子树成为最小不平衡子树的情况，此处A结点和B结点的平衡因子是按相反方向变化的，而不像前两种操作那样，都是按同一方向变化的。图7-10(c)为调整后的情况，调整规则是：将A的左孩子的右子树的根结点C提升到A结点的位置；将B结点作为C的左子树的根结点，而C结点的原左子树则作为B结点的右子树；将A结点作为C的右子树的根结点，而C结点的右子树则作为A结点的左子树。此调整过程比前两种情况要复杂，需修改五个指针，如图7-10(c)中的箭头所示。 1 2 0 A A C 0 -1 0 1 B 0 B 1 B A C C h+1 h h+1 插入前, 为h+1 , 为h 中序为BCA(a)插入前 (b)插入后 (c)调整后图7-10 LR型调整操作示意图从图7-10可以看出， 调整前后对应的中序序列相同，即为，只是链接次序不同罢了，但没有影响其二叉搜索树的性质。图7-11是LR型调整操作的两个实例，其中图7-11中的(a)、7-11中的(b)、7-11中的(c)为一例，此处A结点为9，B结点为3，C结点为6，它是新插入的结点，、均为空树；图7-11中的(d)、7-11中的(e)、7-11中的(f)为 1 9 2 9 0 6 -1 56 0 3 -1 3 0 3 0 9 1 34 1 85 0 6 0 20 074 0 92 0 65 080 (a) (b)插入6后 (c)调整后 (d)插入前 -256 -1 56 1 34 2 85 1 34 0 80 0 20 -174 092 0 20 0 74 -1 85 0 65 180 0 65 078 0 92 0 78 (e)插入78后 (f )调整后图7-11 LR型调整实例 1 2 0 A A C 0 -1 0 1 B 0 B 1 B A C C h+1 h h+1 插入前, 为h+1 , 为h 中序为BCA (a)插入前 (b)插入后 (c)调整后图7-10 LR型调整操作示意图另一例，此处A结点为85，B结点为74，C结点为80,和子树分别为65和92，和均为空。 -1 -2 0 A A C 0 1 1 0 h+1 0 B -1 B A B C C h h+1 插入前, 为h+1 , 为h 中序为ACB图7-12 RL型调整操作示意图它是因在A结点的右(Right)孩子的左(Left)子树上插入结点，使得A结点的平衡因子由-1变为-2而引起的不平衡所进行的调整操作。调整过程如图7-12所示，它同LR型调整过程对称，请读者自行分析。在上述每一种调整操作中，以A为根的最小不平衡子树的高度在插入结点前和调整后相同，所以对除此子树之外的其余所有结点的平衡性不会产生影响，即原有的平衡因子不变，故按照上述方法将最小不平衡子树调整为平衡子树后，整个二叉搜索树就成了一棵新的平衡树。下面假定用一组关键字为(46,15,20,35,28,58,18,50,54)生成一棵平衡的二叉搜索树，则生成过程如图7-13所示。 46 46 2 20 20 15 15 46 15 462 20 35 (a) (b) (c)LR型调整 28 (d) 20 2 35 3515 35 20 46 20 46 -2 28 46 15 28 58 15 28 58 58 18 50(e)LL型调整 (f)RR型调整 (g) 35 35 20 50 20 5015 28 46 58 15 28 46