数据结构严蔚敏-查找表3

1、1二、二叉平衡树二、二叉平衡树1. 二叉平衡树定义二叉平衡树定义3. 平衡旋转技术平衡旋转技术2. 如何构造二叉平衡树如何构造二叉平衡树4. 二叉平衡树的插入二叉平衡树的插入5. 二叉平衡树的删除二叉平衡树的删除2问题： 二叉排序树的缺点是树的结构事先无法预料，随意性很大，它只与结点的值和插入的次序有关，有时会得到一颗很不平衡的二叉树。 当二叉树与理想的平衡树相差越远，树的高度越高时，其运算的时间就越长。最坏的情况下，二叉树退化成单链表，其时间复杂度由O(log2n)变为O(n)。1. 二叉平衡树定义二叉平衡树定义3 二叉平衡树（又称二叉平衡树（又称AVLAVL树）树） 例如例如:548254

2、821平衡树平衡树非平衡树非平衡树1510325126045非平衡树非平衡树 结点的平衡因子：结点的平衡因子：左子树的高度减右子树的左子树的高度减右子树的高度高度 。 011001220001-101-24 构造平衡的二叉排序树的方法是： 根据根据初始序列，从空树开始插入新结点，在插入过程空树开始插入新结点，在插入过程 中，中，在保持在保持二叉排序树二叉排序树特性的前提下，采用采用平衡旋转技平衡旋转技 术术，对，对最小不平衡子树最小不平衡子树进行调整，使其平衡。进行调整，使其平衡。2. 如何构造如何构造“二叉平衡树二叉平衡树”1548215103260450122001-2-2053. 平衡旋

3、转技术平衡旋转技术6右单旋转右单旋转 如果在左子树根结点的左子树上插入结点如果在左子树根结点的左子树上插入结点, , 引起不平衡，则需要进行引起不平衡，则需要进行右单旋转 。 以结点以结点B B为旋转轴，将结点为旋转轴，将结点A A顺时针旋转。顺时针旋转。hhhACEBD(a) (b) (c)hh+1BACEDhhh+1CEABDh5435437左单旋转左单旋转 如果在右子树根结点的右子树上插入结点，如果在右子树根结点的右子树上插入结点， 引起不平衡，则需要进行引起不平衡，则需要进行左单旋转 以结点以结点C C为旋转轴，让结点为旋转轴，让结点A A逆时针旋转。逆时针旋转。hhhACEBD(a)

4、 (b) (c)hhh+1BACEDhhh+1CEABD5434358先左后右双旋转先左后右双旋转 如果在左子树根结点的右子树上插入结点，如果在左子树根结点的右子树上插入结点，引起不平衡，则需要进行引起不平衡，则需要进行先左后右双旋转 。5345439插入左单旋转右单旋转先左后右双旋转先左后右双旋转 1043554311插入右单旋转右单旋转先右后左双旋转先右后左双旋转 12例如:依次插入的关键字为5, 4, 2, 8, 6, 95424258665842向右旋转一次先向右旋转再向左旋转4. 二叉平衡树的插入二叉平衡树的插入13426589426895向左旋转一次继续插入关键字 9145. 二叉

5、平衡树的删除二叉平衡树的删除 1. 首先不考虑平衡问题，按二叉排序树的首先不考虑平衡问题，按二叉排序树的删除原理对二叉平衡树进行删除。删除原理对二叉平衡树进行删除。 2. 然后再考虑平衡问题，沿被删除结点通向然后再考虑平衡问题，沿被删除结点通向根的路径反向追踪检查路根的路径反向追踪检查路 径上各个结点平径上各个结点平衡因子的变化。衡因子的变化。 分三种情况考虑：分三种情况考虑：15ncase 1 : 当前结点当前结点 p 的的平衡因子平衡因子为为0。如果。如果它的左子树或右子树被缩短，则只需要修改它的左子树或右子树被缩短，则只需要修改它的它的 平衡因子平衡因子为为 1 或或-1。不需要旋转。不

6、需要旋转。0hhh-1删除一个结点删除一个结点, ,高度不变高度不变不旋转1hh-1pp16ncase 2 : 结点结点 p 的的平衡因子平衡因子不为不为0，且较，且较高的子树被缩短，则高的子树被缩短，则 p 的的平衡因子平衡因子改为改为0。不需要旋转。不需要旋转。 1h+1hh删除一个结点删除一个结点, ,高度降低一层高度降低一层不旋转0hhpp高度减117ncase 3 : 结点结点 p 的的平衡因子平衡因子不为不为0，且，且较较矮矮的子树又被缩短，则在结点的子树又被缩短，则在结点 p 发生不平发生不平衡。需要进行平衡化旋转来恢复平衡。衡。需要进行平衡化旋转来恢复平衡。n令结点令结点 p

7、的的较高较高的子树的根为的子树的根为 q, 根据根据 q 的的平衡因子平衡因子，有如下，有如下 3 种平衡化操作：种平衡化操作：18ncase 3a : 如果如果 q (较高的子树较高的子树) 的的平衡因子平衡因子为为 0，执行一个单旋转来恢复结点执行一个单旋转来恢复结点 p 的平的平衡。衡。-1hhh-1左单旋ph0q-1hh-1phq 119ncase 3b : 如果如果 q 的的平衡因子平衡因子与与 p 的的平衡平衡因子因子相同，则执行一个单旋转来恢复平衡相同，则执行一个单旋转来恢复平衡, 结点结点 p 和和 q 的的平衡因子平衡因子均改为均改为0。-1hh-1左单旋ph-1q0h-1p

8、hq0h-1h-1200ncase 3c : 如果如果 p 与与 q 的的平衡因子平衡因子相反相反, 则则执行一个双旋转来恢复平衡执行一个双旋转来恢复平衡, 先围绕先围绕 q 转再转再围绕围绕 p 转。新根结点的转。新根结点的平衡因子平衡因子置为置为0，其，其它结点的它结点的平衡因子平衡因子相应处理。相应处理。-1hh-1p1qh-1或h-2h-1或h-2h-1rh-1h-1h-1h-100pqr右左双旋高度减121ABCDEFGHIJKLMNOPQRST00000001111111-1-1-1-1-1树的初始状态树的初始状态举例：举例：删除结点删除结点 P22ABCDEFGHIJKLMNOP

9、QRST00000001111111-1-1-1-1-1POOPOOP23ABCDEFGHIJKLMNOQRST0000001111111-1-1-1-1-1删除结点删除结点P case 3b：O与与R的平衡因子同号的平衡因子同号, 以以R为旋转轴为旋转轴做左单旋转做左单旋转, M的子树高度减的子树高度减 1。qp24ABCDEFGHIJKLMNOQRST0000001111111-100-1case3c：M的子树高度减的子树高度减 1, M发生不平衡。发生不平衡。M与与E的平衡因子反号的平衡因子反号, 做左右双旋转。做左右双旋转。0qp25ABCDEFGHIJNKLMOR0000010011

10、110-10000TQ0S26n设在新结点插入前设在新结点插入前AVL树的高度为树的高度为 h，结点个数，结点个数为为 n，则插入一个新结点的时间是，则插入一个新结点的时间是O(h)。n对于对于AVL树来说，树来说，h 多大？多大？n设设 Nh 是高度为是高度为 h 的的AVL树中含有的最少结点个树中含有的最少结点个数。显然有：数。显然有： N0 = 0 (空树空树)， N1 = 1 (仅有根结点仅有根结点) Nh = Nh-1 + Nh-2 +1 , h 06. 二叉平衡树的高度二叉平衡树的高度可以看出：可以看出：Nh 的定义与斐波那契数列的定义非常相似。的定义与斐波那契数列的定义非常相似。

11、 F0 = 0, F1 = 1, Fh = Fh-1 + Fh-2 可以证明可以证明, 对于对于 h 0, 有有 Nh = Fh+2 -1 成立。成立。有有 n 个结点的个结点的AVL树的高度不超过：树的高度不超过： 1.44*log2 2(n+1) -127 已知长度为12的表：(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)例题：例题：1. 按表中元素的顺序依次插入生成一颗二叉排序树二叉排序树(初始为空)，并求其在等概率的情况下查找成功时的平均查找长度；2. 若对表中元素先进行排序，构成有序表有序表，并求其在等概率的情况下，对此有序表查找成

12、功时的平均查找长度；3. 按表中元素的顺序构造一颗平衡二叉排序树平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度；28例题：例题： 已知长度为12的表：(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)JanFebMarAprMayJun JulAugSepOctNovDecASL = (11+2 2 +3 3 +4 3 +5 2 +6 1) /12 = 42 /121. 求二叉排序树求二叉排序树29例题：例题： 已知长度为12的表：(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)AS

13、L = (11+2 2 +3 4 +4 5 ) / 12 = 37 /122. 有序表有序表 排序后采用折半查找排序后采用折半查找(Apr, Aug, Dec, Feb, Jan, Jul, Jun, Mar,May,Nov ,Oct, Sep) 3 4 2 3 4 1 3 4 2 4 3 430例题：例题： 已知长度为12的表：(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)JanFebMarAprMayJun JulAug3. 求平衡二叉排序树求平衡二叉排序树31例题：例题： 已知长度为12的表：(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)AugAprJanMarMayJun Jul3. 求平衡二叉排序树求平衡二叉排序树FebSepOct32例题：例题： 已知长度为12的表：(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)Oct3. 求平