数据结构与算法

1、1 1AVLAVL树树 高度平衡的二叉搜索树高度平衡的二叉搜索树ABDABCDECEnAVL 树的定义树的定义 一棵一棵 AVL 树或者是空树，或树或者是空树，或者是具有下列性质的二叉搜索树：它的左子树者是具有下列性质的二叉搜索树：它的左子树和右子树都是和右子树都是 AVL 树，且左子树和右子树的树，且左子树和右子树的高度之差的绝对值不超过高度之差的绝对值不超过 1。 2 2结点的平衡因子结点的平衡因子bfbf (balance factorbalance factor)n每个结点附加一个数字，给出该结点右子树每个结点附加一个数字，给出该结点右子树的高度减去左子树的高度所得的高度差，这的高度减

2、去左子树的高度所得的高度差，这个数字即为结点的平衡因子个数字即为结点的平衡因子bf。 nAVL树任一结点平衡因子只能取树任一结点平衡因子只能取 -1, 0, 1。n如果一个结点的平衡因子的绝对值大于如果一个结点的平衡因子的绝对值大于1，则，则这棵二叉搜索树就失去了平衡，不再是这棵二叉搜索树就失去了平衡，不再是AVL树。树。n如果一棵有如果一棵有 n 个结点的二叉搜索树是高度平个结点的二叉搜索树是高度平3 3衡的，其高度可保持在衡的，其高度可保持在O(log2n)，平均搜，平均搜索长度也可保持在索长度也可保持在O(log2n)。AVLAVL树的类定义树的类定义 (略)4 4平衡化旋转n如果在一棵

3、平衡的二叉搜索树中插入一个新如果在一棵平衡的二叉搜索树中插入一个新结点，造成了不平衡。此时必须调整树的结结点，造成了不平衡。此时必须调整树的结构，使之平衡化。构，使之平衡化。n平衡化旋转有两类：平衡化旋转有两类： 单旋转单旋转 (左旋和右旋左旋和右旋) 双旋转双旋转 (左平衡和右平衡左平衡和右平衡)n每插入一个新结点时每插入一个新结点时, AVL 树中相关结点的树中相关结点的平衡状态会发生改变。因此平衡状态会发生改变。因此, 在插入一在插入一 个新个新结点后，需要结点后，需要从插入位置沿通向根的路径回从插入位置沿通向根的路径回溯溯，检查各结点的平衡因子检查各结点的平衡因子。5 5n如果在某一结

4、点发现高度不平衡，停止回溯。如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。直接下两层的结点。n如果这三个结点处于一条直线上，则采用单旋如果这三个结点处于一条直线上，则采用单旋转进行平衡化转进行平衡化。单旋转可按其方向分为单旋转可按其方向分为左单旋左单旋转转和和右单旋转右单旋转, 其中一个是另一其中一个是另一 个的镜像，个的镜像，其方向与不平衡的形状相关。其方向与不平衡的形状相关。n如果这三个结点处于一条折线上，则采用双旋如果这三个结点处于一条折线上，则采用双旋转进行平衡化转进行平衡化。双旋转分为双旋转分

5、为先左后右先左后右和和先右后先右后左左两类。两类。6 6右单旋转右单旋转左单旋转左单旋转左右双旋转左右双旋转右左双旋转右左双旋转左单旋转左单旋转 (RotateLeft ) (RotateLeft )n在结点在结点A的右子女的右子女的的右子树右子树E中插入新结点，中插入新结点，该子树高度增该子树高度增1导致结点导致结点A的平衡因子变成的平衡因子变成2，出现不平衡。为使树恢复平衡，从出现不平衡。为使树恢复平衡，从A沿插入路沿插入路径连续取径连续取3个结点个结点A、C和和E，以结点，以结点C为旋转为旋转轴，让结点轴，让结点A反时针旋转。反时针旋转。7 7插入插入ACEBDhhh-1 h-1BACE

6、Dhhh-1 hBhhCEADh-1 h8 8n在结点在结点A的左子女的左子女的的左子树左子树D上插入新结上插入新结点使其高度增点使其高度增1导致结点导致结点A的平衡因子增的平衡因子增到到-2，造成不平衡。为使树恢复平衡，造成不平衡。为使树恢复平衡，从从A沿插入路径沿插入路径右单旋转右单旋转 (RotateRight ) (RotateRight )9 9n插入路径连续取插入路径连续取3 个结点个结点A、B和和D，以结点，以结点B为旋转轴，将结点为旋转轴，将结点A顺时针旋转。顺时针旋转。BACEDhhh-1hh插入插入hhh-1h-1ABDCEhhh-1BCEADh1010先左后右双旋转先左后

7、右双旋转 (RotationLeftRight) (RotationLeftRight)n在结点在结点A的左子女的右子树中插入新结点，的左子女的右子树中插入新结点，该子树高度增该子树高度增1导致结点导致结点A的平衡因子变的平衡因子变为为-2， 造成不平衡。造成不平衡。11 11插入插入hhACEDh-1h-1BFGE左单左单旋转旋转GACDBFhhh-1hn以结点以结点E为旋转轴，将结点为旋转轴，将结点B反时针旋转，反时针旋转，以以E代替原来代替原来B的位置。的位置。1212n再以结点再以结点E为旋转轴，将结点为旋转轴，将结点A顺时针旋顺时针旋转。使之平衡化。转。使之平衡化。右单右单旋转旋转A

8、EhhCDh-1hBFGFGDhAh-1CEBhh1313n在结点在结点A的右子女的左子树中插入新结点，的右子女的左子树中插入新结点，该子树高度增该子树高度增1。结点。结点A的平衡因子变为的平衡因子变为2，发生了不平衡。发生了不平衡。n首先以结点首先以结点D为旋转轴，将结点为旋转轴，将结点C顺时针顺时针旋转，以旋转，以D代替原来代替原来C的位置。的位置。先右后左双旋转先右后左双旋转 (RotationRightLeft) (RotationRightLeft)1414插入插入hhh-1h-1ACEDBFG右单旋转右单旋转ACEBFGDhhhh-1n再以结点再以结点D为旋转轴，将结点为旋转轴，将

9、结点A反时针旋转，反时针旋转， 恢复树的平衡。恢复树的平衡。1515ACEDBFGhhh-1hhhh-1hACEBFGD1616AVLAVL树的插入树的插入n在向一棵本来是高度平衡的在向一棵本来是高度平衡的AVL树中插入一树中插入一个新结点时，如果树中某个结点的平衡因子个新结点时，如果树中某个结点的平衡因子的绝对值的绝对值 | bf | 1，则出现了不平衡，需要，则出现了不平衡，需要做平衡化处理。做平衡化处理。nAVL树的插入算法从一棵空树开始，通过输树的插入算法从一棵空树开始，通过输入一系列对象关键码，逐步建立入一系列对象关键码，逐步建立AVL树。树。n在插入新结点后，需从插入结点沿通向根的

10、在插入新结点后，需从插入结点沿通向根的路径向上回溯，如果发现有不平衡的结点，路径向上回溯，如果发现有不平衡的结点，需从这个结点出发，使用平衡旋转方法进行需从这个结点出发，使用平衡旋转方法进行平衡化处理。平衡化处理。1717n设新结点设新结点p的平衡因子为的平衡因子为0，其父结点为，其父结点为pr。插。插入新结点后入新结点后pr的平衡因子值有三种情况：的平衡因子值有三种情况：n 结点结点pr的平衡因子为的平衡因子为0。说明刚才是在说明刚才是在pr的较的较矮的子树上插入了新结点，此时不需做平衡化矮的子树上插入了新结点，此时不需做平衡化处理，返回主程序。子树的高度不变。处理，返回主程序。子树的高度不

11、变。1.结点结点pr的平衡因子的绝对值的平衡因子的绝对值|bf| = 1。说明插入说明插入前前pr的平衡因子是的平衡因子是0，插入新结点后，以，插入新结点后，以pr为为根的子树不需平衡化旋转。但该子树高度根的子树不需平衡化旋转。但该子树高度10插入后prp1818增加，还需从结点增加，还需从结点pr向根方向回溯，继续考向根方向回溯，继续考查结点查结点pr双亲双亲(pr = Parent(pr)的平衡状态。的平衡状态。n 结点结点pr的平衡因子的绝对值的平衡因子的绝对值|bf| = 2。说明新说明新结点在较高的子树上插入，造成了不平衡，结点在较高的子树上插入，造成了不平衡，需要做平衡化旋转。此时

12、可进一步分需要做平衡化旋转。此时可进一步分2种情况种情况讨论：讨论：3. 若结点若结点pr的的bf = 2，说明右子树高，结合，说明右子树高，结合其右子女其右子女q 的的bf分别处理：分别处理：0-1 插入后prp1919若若q的的bf为为1，执行左单旋转。，执行左单旋转。若若q的的bf为为-1，执行先右后左双旋转。，执行先右后左双旋转。左单旋转插入后2q1prp0pr0ppr=q右左双旋转插入后2q-1prp0pr0qpr=p2020 若结点若结点pr的的bf = -2，说明左子树高，结合，说明左子树高，结合其左子女其左子女q 的的bf分别处理：分别处理：若若q的的bf为为-1，执行右单旋转

13、；，执行右单旋转；若若q的的bf为为1，执行先左后右双旋转。，执行先左后右双旋转。n下面举例说明在下面举例说明在AVL树上的插入过程。树上的插入过程。-2q-1prp-2q1prp右单旋转左右双旋转2121n例如，输入关键码序列为例如，输入关键码序列为 16, 3, 7, 11, 9, 26, 18, 14, 15 ，插入和调整过程如下。插入和调整过程如下。160163- -10731600073110- -111637169000111163701273161190- -1- -2237112691601122222右左双旋右左双旋0左单旋左单旋18160073261190003160917

14、1126183- -1- -171614269111739182611162323151831816731171491615112626149从空树开始的建树过程从空树开始的建树过程2424AVLAVL树的删除树的删除n如果如果被删结点被删结点 x 最多只有一个子女，可做简最多只有一个子女，可做简单删除单删除:将将结点结点 x 从树中删去。从树中删去。因为结点因为结点 x 最多有一个子女，可以简单地最多有一个子女，可以简单地把把 x 的双亲中原来指向的双亲中原来指向 x 的指针改指到这的指针改指到这个子女结点；个子女结点；如果结点如果结点 x 没有子女，没有子女，x 双亲原来指向双亲原来指向

15、x的指针置为的指针置为 NULL。将原来以结点将原来以结点 x 为根的子树的高度减为根的子树的高度减 1。2525n如果如果被删结点被删结点 x 有两个子女有两个子女:搜索搜索 x 在中序次序下的在中序次序下的直接前驱直接前驱 y (同样同样可以找直接后继可以找直接后继)。把把结点结点 y 的内容传送给结点的内容传送给结点 x，现在问题，现在问题转移到删除转移到删除结点结点 y。把结点。把结点 y 当作被删结当作被删结点点x。因为结点因为结点 y 最多有一个子女，可以简单最多有一个子女，可以简单地用地用 1. 给出的方法进行删除。给出的方法进行删除。n必须沿结点必须沿结点 x 通向根的路径反向

16、追踪高度通向根的路径反向追踪高度的变化对路径上各个结点的影响。的变化对路径上各个结点的影响。2626n用一个布尔变量用一个布尔变量shorter（缩短）（缩短）来指明子来指明子树高度是否被缩短。在每个结点上要做的树高度是否被缩短。在每个结点上要做的操作取决于操作取决于 shorter的值和结点的的值和结点的bf，有时，有时还要依赖子女的还要依赖子女的bf。n布尔变量布尔变量shorter的值初始化为的值初始化为True。然后。然后对于从对于从x的双亲到根的路径上的各个结点的双亲到根的路径上的各个结点p，在在 shorter保持为保持为True时执行下面操作。如时执行下面操作。如果果 short

17、er变成变成False，算法终止。，算法终止。 当前结点当前结点 p 的的bf为为0。如果它的左子树或如果它的左子树或右子树被缩短，则它的右子树被缩短，则它的bf改为改为1或或-1，同，同时时 shorter置为置为False。2727删除后不旋转 结点结点 p 的的 bf 不为不为0且较高的子树被缩短。且较高的子树被缩短。则则 p 的的 bf 改为改为0，同时，同时shorter置为置为True。p0hhh-1p1hh-1删除后不旋转p-1hh-1p0h-1h-12828 结点结点 p 的的 bf 不为不为0，且较矮的子树又被缩，且较矮的子树又被缩短。短。则在结点则在结点 p 发生不平衡。需

18、要进行平发生不平衡。需要进行平衡化旋转来恢复平衡。衡化旋转来恢复平衡。令令 p 的较高的子树的根为的较高的子树的根为 q（该子树未被（该子树未被缩短），根据缩短），根据 q 的的 bf，有如下，有如下 3 种平衡化种平衡化操作。操作。旋转的方向取决于是结点旋转的方向取决于是结点 p 的哪一棵子树的哪一棵子树被缩短。被缩短。2929 如果如果 q（较高的子树）的（较高的子树）的 bf 为为0，执行一，执行一个单旋转来恢复结点个单旋转来恢复结点 p 的平衡，置的平衡，置shorter为为False。无需检查上层结点的平无需检查上层结点的平衡因子。衡因子。左单旋转1hh-1phq-11hhh-1ph

19、0q3030 如果如果 q 的的 bf 与与 p 的的 bf 相同，则执行一个相同，则执行一个单旋转来恢复平衡，结点单旋转来恢复平衡，结点 p 和和 q 的的 bf 均均改为改为0，同时置，同时置shorter为为True。还要继续还要继续检查上层结点的平衡因子。检查上层结点的平衡因子。左单旋转0h-1h-1phq01hh-1h-1ph1q3131 如果如果 p 与与 q 的的 bf 相反，则执行一个双旋相反，则执行一个双旋转来恢复平衡。先围绕转来恢复平衡。先围绕 q 转再围绕转再围绕 p 转。转。新根结点的新根结点的 bf 置为置为0，其他结点的，其他结点的 bf 相相应处理，同时置应处理，

20、同时置shorter为为True。0h-1h-1h-1h-100pqr右左双旋转高度减11hh-1p- -1qh-1或h-2h-1或h-2h-1r3232ABCDEFGHIJKLMNOPQRST0000000- -1- -1- -1- -1- -1- -1- -111111树的初始状态树的初始状态举例举例3333删除结点删除结点P寻找结点寻找结点P的中序直接前驱的中序直接前驱O, 用用O顶替顶替P, 删除删除O。ABCDEFGHIJKLMNOPQRST0000000- -1- -1- -1- -1- -1- -1- -111111用用O取代取代P3434删除结点删除结点PABCDEFGHIJKLMNOQRST000000- -1- -1- -1- -1- -1- -1- -111111左单旋转左单旋转O与与R的平衡因子同号的平衡因子同号, 以以R为旋转轴做左单旋转为旋转轴做左单旋转, M的子树高度减的子树高度减 1。3535删除结点删除结点PM的子树高度减的子树高度减 1，M发生不平衡。发生不平衡。M与与E的平的平衡因子反号衡因子反号, 做左右双旋转。做左右双旋转。ABCDEFGHIJKLMNOQRST000000- -1- -1- -1- -1- -1- -1- -1