平衡二叉排序树平衡二叉排序树DGEDABCFEGBA 起因：提高查找速度，避免最坏起因：提高查找速度，避免最坏情况出现。如右图情况的出现。情况出现。如右图情况的出现。CF 平衡因子（平衡度）：结点的平衡度是结点的左子树的高度平衡因子（平衡度）：结点的平衡度是结点的左子树的高度右子树的高度。右子树的高度。 平衡二叉树：每个结点的平衡因子都为平衡二叉树：每个结点的平衡因子都为 1、1、0 的二叉的二叉树。或者说每个结点的左右子树的高度最多差一的二叉树。树。或者说每个结点的左右子树的高度最多差一的二叉树。平衡二叉树平衡二叉树平衡二叉排序树平衡二叉排序树AV树树定义：定义： 一棵平衡二叉排序树或者是空树，或者是具有下列一棵平衡二叉排序树或者是空树，或者是具有下列性质的二叉排序树：性质的二叉排序树：1、左子树与右子树的高度之差的、左子树与右子树的高度之差的绝对值绝对值小于等于小于等于1；2、左子树和右子树也是平衡二叉排序树。、左子树和右子树也是平衡二叉排序树。平衡二叉排序树的平衡二叉排序树的平均查找长度为平均查找长度为O（log2n）。平衡因子平衡因子：结点的左子树深度与右子树深度之差：结点的左子树深度与右子树深度之差：-1，0，1。4030255020605840302560708050141253928635360501718730+1+1-1-1-100000000是平衡树不是丰满树是平衡树不是丰满树145392863536050171830+1+2-1-100000+1不是平衡树不是平衡树-1以插入为例：以插入为例： 在左图所示的平衡树中插入数据场为在左图所示的平衡树中插入数据场为 2 的结点。的结点。 插入之后仍应保持平衡分类二叉树的性质不变。插入之后仍应保持平衡分类二叉树的性质不变。141253928635360501718730+1+1-1-1-100000000平衡树平衡树141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡原平衡度为度为 0危机结点危机结点如何用最简单、最有效的办法保如何用最简单、最有效的办法保持平衡分类二叉树的性质不变？持平衡分类二叉树的性质不变？141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡原平衡度为度为 0危机结点危机结点如何用最简单、最有效的办法保如何用最简单、最有效的办法保持平衡分类二叉树的性质不变？持平衡分类二叉树的性质不变？解决方案：解决方案：不涉及到危机结点的父亲结点，不涉及到危机结点的父亲结点，即以危机结点为根的子树的高即以危机结点为根的子树的高度应保持不变（图为度应保持不变（图为 3 ）。）。新结点插入后，找到第一个平新结点插入后，找到第一个平衡度不为衡度不为 0 的结点（如左图结的结点（如左图结点点 9）即可。新插入的结点和）即可。新插入的结点和第一个平衡度不为第一个平衡度不为 0 的结点的结点（也可能是危机结点）之间的（也可能是危机结点）之间的结点，其平衡度皆为结点，其平衡度皆为 0。在调整中，仅调整那些在平衡在调整中，仅调整那些在平衡度变化的路径上的结点（如：度变化的路径上的结点（如：3 5 9），其它结点不予调整。），其它结点不予调整。仍应保持二叉排序树的性质不仍应保持二叉排序树的性质不变。变。141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡原平衡度为度为 0危机结点危机结点关键：将导致出现关键：将导致出现危机结点的情况危机结点的情况全部分析清除，就全部分析清除，就可以使得平衡分类二叉树的性质保持不变！可以使得平衡分类二叉树的性质保持不变！14932528635360501718730+1+1-1-1-100000001200最低层失衡结点为最低层失衡结点为A，在结点，在结点A的左子树的左子树的左子树的左子树上插入新结点上插入新结点S后，导致失衡，由后，导致失衡，由A和和B的平衡因子的平衡因子可知，可知，BL、BR和和AR深度相同，为恢复平衡并保持二深度相同，为恢复平衡并保持二叉排序树的特性，可将叉排序树的特性，可将A改为改为B的右子，的右子，B原来的右原来的右子子BR改为改为A的左子，这相当于以的左子，这相当于以B为轴，对为轴，对A做了一做了一次顺时针旋转。次顺时针旋转。ABBLSBRARBABLSBRAR不平衡二叉排序树的调整不平衡二叉排序树的调整LL型型不平衡二叉排序树的调整不平衡二叉排序树的调整LL型型4030256020AB15AB253020401560A-lchild=B-rchild B-rchild=A最低层失衡结点为最低层失衡结点为A，在结点，在结点A的左子树的右子树上插入新的左子树的右子树上插入新结点结点S后，导致失衡，假设在后，导致失衡，假设在CL下插入下插入S，由，由A、B、C的平衡因的平衡因子可知，子可知，CL与与CR深度相同，深度相同，BL与与AR深度相同，且深度相同，且BL、AR的深的深度比度比CL、CR的深度大的深度大1；为恢复平衡并保持二叉排序树的特性，；为恢复平衡并保持二叉排序树的特性，可将可将B改为改为C的左子，而的左子，而C原来的左子原来的左子CL改为改为B的右子，然后将的右子，然后将A改为改为C的右子，的右子，C原来的右子原来的右子CR改为改为A的左子；这相当于以的左子；这相当于以B为为轴，对轴，对A做了一次顺时针旋转。做了一次顺时针旋转。ABBLSCRARCLCCBBLSCRARCLA不平衡二叉排序树的调整不平衡二叉排序树的调整LR型型不平衡二叉排序树的调整不平衡二叉排序树的调整LR型型806040905020957085301045605040804520908570301095ABCCABA-lchild=c-rchild B-rchild=c-lchildc-rchild=Ac-lchild=B最低层失衡结点为最低层失衡结点为A，在结点，在结点A的右子树的右子树上插入新结的右子树的右子树上插入新结点点S后，导致失衡，由后，导致失衡，由A和和B的平衡因子可知，的平衡因子可知，BL、BR和和AL深度深度相同，为恢复平衡并保持二叉排序树的特性，可将相同，为恢复平衡并保持二叉排序树的特性，可将A改为改为B的左的左子，子，B原来的左子原来的左子BL改为改为A的右子，这相当于以的右子，这相当于以B为轴，对为轴，对A做了做了一次逆时针旋转。一次逆时针旋转。ASBBLBRARBAALSBLBR不平衡二叉排序树的调整不平衡二叉排序树的调整RR型型不平衡二叉排序树的调整不平衡二叉排序树的调整RR型型3025204060AB703025204060AB70A-rchild=B-lchild B-lchild=A最低层失衡结点为A，在结点A的右子树的左子树上插入新结点S后，导致失衡，假设在CR下插入S，由A、B、C的平衡因子可知，CL与CR深度相同，AL与BR深度相同，且AL、BR的深度比CL、CR的深度大1；为恢复平衡并保持二叉排序树的特性，可将B改为C的右子，而C原来的右子CR改为B的左子，然后将A改为C的左子，C原来的左子CL改为A的右子；这相当于以B为轴，对A做了一次顺时针旋转。ABALSCRBRCLCCAALSCRBRCLB不平衡二叉排序树的调整不平衡二叉排序树的调整RL型型不平衡二叉排序树的调整不平衡二叉排序树的调整RL型型8560408050209070953010ABC55854060805020907095301055A-rchild=c-lchild B-lchild=c-rchildc-lchild=Ac-rchild=B54263187思考：此树是否为平衡二叉树，在此二叉树中插入结点7后，该树是否为平衡二叉树，若不平衡，如何调整542731861、引入、引入大量数据存放在外存中，通常存放在硬盘中。由于是海量数据，不可大量数据存放在外存中，通常存放在硬盘中。由于是海量数据，不可能一次调入内存。因此，要多次访问外存。但硬盘的驱动受机械运动的制能一次调入内存。因此，要多次访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外次数。约，速度慢。所以，主要矛盾变为减少访外次数。在在 1970 年由年由 R bayer 和和 E macreight 提出用提出用B_ 树作为索引组织文树作为索引组织文件。提高访问速度、减少时间。件。提高访问速度、减少时间。内存内存 用二叉树组织文件，当文件的记用二叉树组织文件，当文件的记录个数为录个数为 100，000时，要找到给时，要找到给定关键字的记录，需访问外存定关键字的记录，需访问外存17次次（log100,000）,太长了！太长了！502510751535609020304055708095索索引引文文件件数数据据文文件件文件头，可常驻内存文件头，可常驻内存文件访问示意图：索引文件、数据文件存在盘上文件访问示意图：索引文件、数据文件存在盘上B_ 树树m 阶阶 B_ 树的树的 定义定义定义：一棵定义：一棵m阶的阶的B-树，或者为空树，或为满足下列特性的树，或者为空树，或为满足下列特性的m叉树：叉树： 树中每个结点至多有树中每个结点至多有m棵子树；棵子树； 若根结点不是叶子结点，则至少有两棵子树；若根结点不是叶子结点，则至少有两棵子树； 除根结点之外的所有非终端结点至少有除根结点之外的所有非终端结点至少有 m/2 棵子树；棵子树； 所有的非终端结点中包含以下信息数据：（所有的非终端结点中包含以下信息数据：（n，A0，K1，A1，K2，Kn，An）其中：其中：Ki（i=1,2,n）为关键码，且）为关键码，且KiKi+1，Ai为指向子为指向子树根结点的指针树根结点的指针(i=0,1,n)，且指针，且指针Ai-1所指子树中所有所指子树中所有结点的关键码均小于结点的关键码均小于Ki (i=1,2,n)，An所指子树中所有结所指子树中所有结点的关键码均大于点的关键码均大于Kn， m/2 1nm 1 ，n为关键码的为关键码的个数。个数。 所有的叶子结点都出现在同一层次上，并且不带信息所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。不存在，指向这些结点的指针为空）。例如：例如：m = 4 阶阶 B_ 树。除根结点和叶子结点之树。除根结点和叶子结点之外，每个结点的儿子个数至少为外，每个结点的儿子个数至少为 m/2 = 2 个；个；结点的关键字个数至少为结点的关键字个数至少为 1 。该。该 B_ 树的深度为树的深度为 4。叶子结点都在第叶子结点都在第 4 层上。层上。1，993，47，58，641，391，271，112，43，781，181，35FFFFFFFFFFFF第第 1 层层第第 2 层层第第 3 层层(L层层)第第 4 层层(L1层层)一棵5阶的B-树，其深度为4 2 3 72 20 253 79 84 934 35 41 51 53 2 66 68 2 71 762 12 302 69 781 54tF F FF F FF F F F FF F FF F FF F F Fabcdeghfi 查找过程，类似于二叉树的查找。如查找关键字为查找过程，类似于二叉树的查找。如查找关键字为 KEY 的记录。的记录。 从根开始查找，如果从根开始查找，如果 Ki = KEY 则查找成功，则查找成功，Ki 为关键字为为关键字为 KEY 的记录的地址。的记录的地址。 若若 Ki KEY Ki+1; 查找查找 Ai 指向的结点指向的结点若若 KEY Kn; 查找查找 An指向的结点指向的结点若若 找到叶子，则查找失败。找到叶子，则查找失败。注意：每次查找将去掉注意：每次查找将去掉 （s-1）/s 个分支，个分支，比二分查找快得多比二分查找快得多 B_ 树的查找树的查找历届题目：m阶B-树是一棵( ) 【北京邮电大学 2000 二、2 （20/8分）】 A. m叉排序树 B. m叉平衡排序树 C. m-1叉平衡排序树 D. m+1叉平衡排序树 B.下面关于m阶B树说法正确的是( ) 【南京理工大学 1999 一、5 （2分）】 每个结点至少有两棵非空子树； 树中每个结点至多有m一1个关键字;所有叶子在同一层上; 当插入一个数据项引起B树结点分裂后，树长高一层。 A B. C. D. B.高度为4的3阶b-树中，最多有_个关键字。【合肥工业大学 2000 三、9 （2分）】 26在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是_;若在某结点中删除一个关键字而导致结点合并,则该结点中原有的关键字的个数是_。 【中国科技大学 1998 一、5 （3分）】【南京理工大学 2001 二、4 （3分）】 m-1m/2 -1