2-7-2th-AVLBtree-search

1、为保证树型，查找有较高的查找速度，希望该二叉树接近为保证树型，查找有较高的查找速度，希望该二叉树接近满二叉树，即，希望二叉树的每个结点的左、右子树高度尽满二叉树，即，希望二叉树的每个结点的左、右子树高度尽量接近平衡，即使按任意次序不断地插入结点，也不要使此量接近平衡，即使按任意次序不断地插入结点，也不要使此树成为退化树。树成为退化树。8.4.1 8.4.1 定义（定义（Balanced binary Tree / Height-Balanced TreeBalanced binary Tree / Height-Balanced Tree ）1. 1. 定义：定义：又称又称AVL树树, 或是空

2、、或是具有下列性质的二叉树：或是空、或是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过的深度之差的绝对值不超过1 1。2. 2. 例子：例子： 是二叉搜索树是二叉搜索树 树和所有子树的左右树和所有子树的左右子树高度之差绝对值不超过子树高度之差绝对值不超过1 11115142639718161000000013. 3. 平衡因子（平衡因子（balance factorbalance factor） 结点右子树高度减去左子树高度所得高度差结点右子树高度减去左子树高度所得高度差 AVLAVL树中所有结

3、点的平衡因子只能取树中所有结点的平衡因子只能取0 0，1 1，1 1 AVL AVL树的树的ASLASL可保持在可保持在O(logO(log2 2n)n)8.4.2 8.4.2 平衡旋转平衡旋转原因原因方法方法1. LL1. LL平衡旋转平衡旋转右单旋转右单旋转AB( a )4030503520hhh10ABh1hh21hB0hAh0hh1插入前插入后调整后10000插入前403050352010211002插入10后302040503510010000调整后( b )5040596430474030505947642. RR2. RR平衡旋转平衡旋转左左单旋转单旋转3. LR3. LR平衡旋

4、转平衡旋转先左后右双旋转先左后右双旋转h(a)F子树插入结点高度变为hCA- 2FhBDE1h-1Gh插入- 1(b)绕E，将B逆时针转后hACEhhBDFh-1GEBhhDFAh-1hCG(c)绕E，将A顺时针转后0683985462750LR型型ABEGFDC绕绕E，将，将B逆时针转后逆时针转后5039276885AC46E绕绕E，将，将A顺时针转后顺时针转后(LL)463968278550683985462743思考：该类思考：该类LR型平衡旋转如何型平衡旋转如何处理？结果如何？处理？结果如何？4. RL4. RL平衡旋转平衡旋转先右后左双旋转先右后左双旋转1. 1. 平衡二叉树插入结点

5、的算法思想平衡二叉树插入结点的算法思想（1 1）按二叉排序树的性质插入结点。）按二叉排序树的性质插入结点。（2 2）如果插入结点之后出现不平衡的结点，则继续步骤（）如果插入结点之后出现不平衡的结点，则继续步骤（3 3）；）；否则插入完成。否则插入完成。（3 3）找到失去平衡的最小子树。）找到失去平衡的最小子树。（4 4）判断平衡旋转的类型作相应平衡化处理）判断平衡旋转的类型作相应平衡化处理。由平衡二叉树由平衡二叉树的定义可知，的定义可知，在插入之后如在插入之后如果树上出现平果树上出现平衡因子绝对值衡因子绝对值大于大于1的结点，的结点，则说明二叉排则说明二叉排序树已不平衡。序树已不平衡。2.2.

6、 关键问题关键问题 输入次序：输入次序：11110如何发现？如何发现？ , 3939039 11+1, 2323 11+1如何确定？如何确定？ 在查找结点在查找结点x x的插入位置的过程中，记下的插入位置的过程中，记下从根结点到插入位置的路径上离插入位从根结点到插入位置的路径上离插入位置最近的且平衡因子绝对值为置最近的且平衡因子绝对值为1 1的结点，的结点，并令指针并令指针a a指向该结点；如果此路径上不指向该结点；如果此路径上不存在平衡因子绝对值为存在平衡因子绝对值为1 1的结点，则指针的结点，则指针a a指向根结点。指向根结点。a23 39-1230如何判断？如何判断？ RLRLRL型型3

7、92311392311如果结点如果结点a a的平衡因子绝对值为的平衡因子绝对值为2 2，则表示二，则表示二叉排序树失去平衡，再根据结点叉排序树失去平衡，再根据结点a a及其左右及其左右孩子的平衡因子值来确定平衡旋转的类型。孩子的平衡因子值来确定平衡旋转的类型。思考题：思考题：做平衡旋转时做平衡旋转时/ /后各结点的平衡因子如何变化？后各结点的平衡因子如何变化？继续输入继续输入6868，8585，8 8，3 3，4646，2727，5050，插入过，插入过程？程？1. 1. 平衡二叉树删除结点的算法思想平衡二叉树删除结点的算法思想（1 1）如果被删结点）如果被删结点x x有左、右孩子，首先查找有

8、左、右孩子，首先查找x x在中序次序下的在中序次序下的直接前直接前驱驱y y( (同样也可以找同样也可以找直接后继直接后继) )，再把结点，再把结点y y的内容传送给结点的内容传送给结点x x，再，再删除结点删除结点y y。（2 2）对于删除最多有一个孩子的结点）对于删除最多有一个孩子的结点x x，可以简单，可以简单地把地把x x的双亲结点中原来指向的双亲结点中原来指向x x的指针改指到的指针改指到x x的的孩子结点。如果结点孩子结点。如果结点x x没有孩子，则其双亲结点没有孩子，则其双亲结点的相应指针置为空。的相应指针置为空。hhhABCDE0- 1hh-1hABCEFG（3 3）对于从结点

9、）对于从结点x x的双亲到根结点的路径上的每的双亲到根结点的路径上的每一个结点一个结点P P，当布尔变量，当布尔变量shorter(shorter(子树高度是子树高度是否被缩短否被缩短) )的值为的值为truetrue时，根据以下三种不同时，根据以下三种不同的情况继续步骤，直到布尔变量的情况继续步骤，直到布尔变量shortershorter的值的值为为falsefalse时，整个删除算法结束。时，整个删除算法结束。 （结点（结点y y最多有一个孩子，因为最多有一个孩子，因为y y即为即为x x左左/ /右子树中的最右子树中的最大大/ /小值，也就是小值，也就是x x左左/ /右子树中的最右右子

10、树中的最右/ /左结点）。左结点）。（1 1）情况一：）情况一：结点结点p p的平衡因子为的平衡因子为0 0，如果它的左子，如果它的左子树或右子树被缩短（树或右子树被缩短（shortershorter的值为的值为truetrue），则它的平衡因子改为），则它的平衡因子改为1 1或或-1-1，由于此时以结点由于此时以结点p p为根的子树高度没有为根的子树高度没有缩短，所以置缩短，所以置shortershorter的值为的值为falsefalse。6850463927118323p p（2 2）情况二：）情况二：结点结点p p的平衡因子不为的平衡因子不为0 0，且其较高的，且其较高的子树被缩短，则

11、子树被缩短，则P P的平衡因子改为的平衡因子改为0 0。由于此时以结点由于此时以结点p p为根的子树高度被缩为根的子树高度被缩短，所以短，所以shortershorter的值仍为的值仍为truetrue。1 1 0 0（1 1）情况三：）情况三：结点结点p p的平衡因子不为的平衡因子不为0 0，且较矮的子树又被缩，且较矮的子树又被缩短，则在结点短，则在结点p p发生不平衡。此时，将进行平发生不平衡。此时，将进行平衡化旋转来恢复平衡。衡化旋转来恢复平衡。68504639278323如果如果q q的平衡因子为的平衡因子为0 0，则只要执行一个单旋转就，则只要执行一个单旋转就可恢复结点可恢复结点p

12、p的平衡，由于旋转后被处理子树的的平衡，由于旋转后被处理子树的高度没有缩短，所以置高度没有缩短，所以置shortershorter的值为的值为falsefalseP P（1 1）q q 0 06850462383927如果如果q q的平衡因子与的平衡因子与p p的平衡因子相同，则只要执的平衡因子相同，则只要执行一个单旋转就可恢复结点行一个单旋转就可恢复结点p p的平衡。由于此时被处的平衡。由于此时被处理子树的高度被缩短，所以理子树的高度被缩短，所以shortershorter的值仍为的值仍为truetrue。最。最后，结点后，结点p p和和q q的平衡因子均改为的平衡因子均改为0 0。6850

13、46398323q(1)q(1)68504623839如果如果p p与与q q的平衡因子的符号相反，则需要执行一的平衡因子的符号相反，则需要执行一个双旋转来恢复平衡，先围绕个双旋转来恢复平衡，先围绕q q转、再围绕转、再围绕p p转。由转。由于此时被处理子树的高度被缩短，所以于此时被处理子树的高度被缩短，所以shortershorter的值仍的值仍为为truetrue，新的根结点的平衡因子置为，新的根结点的平衡因子置为0 0，其它结点的，其它结点的平衡因子作相应处理。平衡因子作相应处理。684639278323P(1)P(1)q(-1)q(-1)46392368827顺序查找、二分查找、二叉排

14、序树适用于内查找顺序查找、二分查找、二叉排序树适用于内查找( (较小较小的表的表) )；不适用于较大的、存储在外存储器上的文件。；不适用于较大的、存储在外存储器上的文件。( (平平衡衡) )二叉排序树中二叉排序树中若以结点作为内外存交换的单位，则在若以结点作为内外存交换的单位，则在查找过程中需对外存进行查找过程中需对外存进行log2n次访问，显然很费时。次访问，显然很费时。分块查找可以应用于外查找；分块查找可以应用于外查找；B-B-树是一种多路平衡查找树是一种多路平衡查找树，也适用于外查找。树，也适用于外查找。8.5.1 8.5.1 基本概念基本概念1. 1. 动态的动态的mm路查找树路查找树

15、类似静态表的分类似静态表的分块（索引）查找块（索引）查找一棵一棵m路查找树，它或者是一棵空树，或者是满足如下性质的树：路查找树，它或者是一棵空树，或者是满足如下性质的树：（1） 根结点最多有根结点最多有m棵子树，并具有如下的结构：（棵子树，并具有如下的结构：（n、p0、k1、p1、k2、p2、kn、pn），其中，），其中，Pi是指向子树的指针，是指向子树的指针，Ki是数据元素的关键字；是数据元素的关键字；1inm。（2） KiKi+1，1in。（3） 在在Pi所指的子树中所有的数据元素的关键字都小于所指的子树中所有的数据元素的关键字都小于K i+1，且，且大于大于K i，0in。（4） 在在P

16、n所指的子树中所有数据元素的关键字都大于所指的子树中所有数据元素的关键字都大于kn，而子树，而子树P0中的所有数据元素的关键字都小于中的所有数据元素的关键字都小于K1。（5） Pi所指的子树也是所指的子树也是m路查找树，路查找树，0in。特点：特点：对于一棵对于一棵m路查找树，适路查找树，适当提高查找树的路数当提高查找树的路数m，可以改，可以改善善m路查找树的查找性能。路查找树的查找性能。如果查找树是平衡的，可如果查找树是平衡的，可以使以使m路查找树的查找性能接近路查找树的查找性能接近最佳。最佳。11110hhiimmm 2. B2. B树树q 定义定义B-B-树是一种树是一种平衡的平衡的多路

17、查找树多路查找树，用于文件系统。，用于文件系统。一棵一棵m m阶的阶的B-B-树树, ,或为空或为空, ,或为满足下列特性的或为满足下列特性的m m叉树叉树v 树中每个结点树中每个结点至多至多有有m m棵子树棵子树; ;v 若根结点不是叶子结点若根结点不是叶子结点, ,则至少有两棵子树则至少有两棵子树; ;v 除根之外的所有非终端结点至少有除根之外的所有非终端结点至少有 m/2m/2 棵子树棵子树; ;v 所有的非终端结点中包含下列信息数据所有的非终端结点中包含下列信息数据(n,A(n,A0 0,K,K1 1,A,A1 1,K,K2 2,A,A2 2, ,K,Kn n,A,An n) ) 同同

18、m m路查找树路查找树 v 所有所有叶子结点都出现在同一层次上叶子结点都出现在同一层次上,并且不带信息并且不带信息(可看作是外可看作是外部结点或查找失败的结点部结点或查找失败的结点,实际上这些结点不存在实际上这些结点不存在,指向这些结指向这些结点的指针为空点的指针为空);49356017 2674 824153查找查找26成功，返回结成功，返回结点地址及在结点地址及在结点中的关键字点中的关键字序号序号查找查找58查找失败查找失败结论结论1： B树的查找过程是一个在结点内树的查找过程是一个在结点内查找和按某一条路径向下一层查找交替进查找和按某一条路径向下一层查找交替进行的过程。显然，如果提高行的

19、过程。显然，如果提高B树的阶数树的阶数m，可以减少树的高度，从而减少读入结点的可以减少树的高度，从而减少读入结点的次数，因而可减少读磁盘的次数。次数，因而可减少读磁盘的次数。 结论结论2：B树的树的查找时间与查找时间与B树树的阶数的阶数m和和B树树的高度的高度h直接有关，直接有关，必须加以权衡。必须加以权衡。 821. 1. 插入的含义插入的含义插入是指在插入是指在 B-树中插入关键字树中插入关键字【叶结点叶结点】插入是生成插入是生成 B-树的基础运算树的基础运算【通过插入建立通过插入建立B-树树】m 阶阶B-树结点关键字数都在树结点关键字数都在 m/2 -1 ，m-1之间之间若超出了结点关键

20、字个数上界若超出了结点关键字个数上界 m-1，结点要，结点要“分裂分裂”2. 2. 结点分裂的原则结点分裂的原则设结点设结点p中已经有中已经有m-1个关键字，当再插入一个关键字后结点中的状个关键字，当再插入一个关键字后结点中的状态为：态为：(m, P0, K1, P1, K2, P2, Km, Pm)其中其中 KiKi+1, 1 i = = m/2m/2 （若该结点同时为根（若该结点同时为根结点，结点，n n= = 2 2）, ,则直接删除则直接删除被删关键字所在结点关键字数被删关键字所在结点关键字数n = n = m/2m/2 - 1, - 1,而左而左( (或右或右) )兄弟兄弟结点有结点

21、有n n = = m/2m/2 , ,则要在则要在该选定的兄弟该选定的兄弟和和双亲双亲三个结点中进行三个结点中进行关键字调整关键字调整60 7055 5875 8065cfgh删删65调整调整 g, h, c7075思考题思考题1：用：用58调整，结果如何？调整，结果如何？思考题思考题2：若有多个兄弟：若有多个兄弟m较大较大，哪些兄弟可用来调整？为什么？哪些兄弟可用来调整？为什么？思考题思考题3：选左右相邻兄弟的原则？：选左右相邻兄弟的原则？q被删关键字所在叶结点被删关键字所在叶结点p删除前关键字个数删除前关键字个数n m2 - 1，若这时与该结点相邻的左、右兄弟结点中的关键字个数也若这时与该

22、结点相邻的左、右兄弟结点中的关键字个数也都为都为 m2 - 1：将双亲结点中大于将双亲结点中大于( (或小于或小于) )该被删关键字的所有关键字中最大该被删关键字的所有关键字中最大（或最小）的一个关键字（或最小）的一个关键字K Ki i下移到下移到p p结点中，将结点中，将P P和和P P的左的左( (或右或右) )兄弟结点合并；兄弟结点合并；修改修改p p结点和其双亲结点关键字个数结点和其双亲结点关键字个数；在合并结点的过程中，双亲结点中的关键字个数减少了在合并结点的过程中，双亲结点中的关键字个数减少了1 1。若。若p p的双亲结点是根结点且结点关键字个数减到的双亲结点是根结点且结点关键字个数减到0 0，则该双亲结点应，则该双亲结点应从树上删去，合并后保留的从树上删去，合并后保留的p p结点成为新的根结点；若双亲结点结点成为新的根结点；若双亲结点f f不是根结点，且关键字个数减到不是根结点，且关键字个数减到 m m2 2 -2-2，则结点，则结点f f又要与它自又要与它自己的兄弟结点合并。重复上面的合并步骤，最坏情况下这种结己的兄弟结点合并。重复上面的合并步骤，最坏情况下这种结点合并处理要自下向上直到根结点。点合并处理要自下向上直到根结点。休息休息 41fgh