数据结构基础(下) ppt.ppt

数据结构基础(下) 教材： 数据结构（C+描述） （金远平编著，清华大 学出版社） n 1JYP 第7章 排序 数据元素之间的次序是一种重要的关系。本 章学习最典型的排序算法，特别讨论内、外排序 的不同策略。还介绍排序结果的顺序化方法。 2JYP 7.1 引言 在数据结构中，数据元素之间的次序是一种重要 的关系。 排序的应用： 查询结果需要按用户指定的属性排序。 在已排序的数组中查找记录可最多用O(log2n)时 间。 核对两个已按学号排序的学生记录表可用O(m+n) 时间完成。 3 JYP 记录 表示数据元素，具有一个或多个数据字 段。 关键字 用于区分记录的字段。 表 记录的有限集合。 给定一个记录表（R0, R1, , Rn-1），设记录Ri的 关键字值为Ki。 关键字上存在一种次序关系 class Element public: KeyType getKey( ) const return key;/ 取记录的关键字值 void setKey(KeyType k) key = k; / 修改记录的关键字 / 其它操作 private: KeyType key;/ 关键字 / 其它字段 ; 假设在KeyType被实例化时，相应实参类型的、= 和 = 等已定义。 6 JYP 7.2 插入排序 插入排序的基本步骤：将记录R插入一个已排好 序的记录序列R0, R1, , Ri（K0K1Ki）中，使 得新的有i + 2个记录的序列也是排好序的。 函数Insert实现了此步骤： template void insert(const Element e, Element *list, int i) / 将e插入已排好序的 list0,listi中， /使结果序列也排好序。list至少可容纳i+2个记录。 while (i = 0) j void insert2(const Element e, Element *list, int i, int incr) while (i =0) j void ShellSort(Element *list, int n) int incr = n; do / 对每个增量 incr = incr/3 + 1; for (int start = 0; start 1); 19 JYP 大规模实验研究表明： 当记录个数n很大时，希尔排序对记录的移动次 数在n1.25到1.6n1.25的范围之内。 这比插入排序有实质性的改进。 作业：P2595 20 JYP 7.4 快速排序 插入排序将控制当前插入的基准记录Ri插入相对 于已排好序的子表 (R0, , Ri1) 的正确位置，而快 速排序将基准记录Ri放在相对于整个记录表的正确 位置。 设输入表为 (Rleft, , Rright)，如果Ri放在位置s(i) ，则有KjKs(i)（j s(i)）。 21 JYP 因此，根据Ri的关键字大小，整个记录表被划分 为左子表 (Rleft, , Rs(i)1)和右子表 (Rs(i)+1, , Rright) ，如下图所示： 由于左、右子表的记录分别在位置s(i)的左、右 边，可独立地对这两个子表排序。 22 JYP 基准记录可任意选取，在此选第一个记录Rleft。 划分记录表： 从左到右扫描，找到关键字大于等于Kleft的记录Ri ； 从右到左扫描，找到关键字小于等于Kleft的记录Rj ； 交换Ri和Rj； 继续上述过程，直到i，j错位。 23 JYP 算法QuickSort给出了实现细节： template void QuickSort (Element *list, const int left, const int right) / 排序listleft,listright，任选listleft为基准记 / 录，假设listleft.keylistright+1.key。 if (left pivot); if (i void ImpQuickSort (Element *list, const int left, const int right) / 排序listleft,listright，任选listleft为 / 基准记录，设listleft.key listright+1.key while (left pivot); if (i = j left) / 左子表较小 ImpQuickSort(list, left, j 1); left = j + 1; else / 右子表较小 ImpQuickSort(list, j + 1, right); right = j 1; 36 JYP 设S(n)为ImpQuickSort所需的栈空间，每层递归 调用需要栈空间为c，则 S(n) c + S(n/2) 2c + S(n/4) clog2n + S(1) = O(log n)。 不难看出，快速排序是不稳定排序。 作业：P25911 37 JYP 7.5 归并排序 7.5.1 迭代归并排序 归并排序的基础是归并，即将两个已排序的表归 并为一个已排序的表。 在迭代归并排序中，需要归并的两个表： (initListl, , initListm) (initListm+1, , initListn) 生成的结果表是 (mergedListl, , mergedListn)。 38 JYP 函数merge： template void merge(Element *initList, Element *mergedList, const int l, const int m, const int n) for (int i1 = l, iResult = l, i2 = m +1; i1 m) for (int t = i2; t void MergePass(Element *initList, Element *resultList, const int n, const int len) / 一遍归并扫描。将表initList的相邻子表归并到表resultList for (int i = 0; i void MergeSort(Element *list, const int n) Element *tempList = new Element n; for (int l = 1; l class Element private: KeyType key;/ 关键字 int link; / 其它字段 public: Element( ) link = -1;/ -1表示空指针 ; 50 JYP 假设： 所有访问Element私有数据成员的的函数已声明为 Element的友元。 listi.key和listi.link分别是记录i的key和link字段 的值（0in1）。 初始时listi.link = 1（0in1），即每个记录构 成一个只含其本身的链表。 51 JYP 函数ListMerge(list, start1, start2) 将两个由start1 和start2指向的按关键字非递减次序链接的链表归并 为一个按关键字非递减次序链接的链表，并返回首 记录指针： template int ListMerge(Element *list, const int start1, const int start2) / 将分别由start1和start2指向的已排序链表归并为 / 一个已排序链表，并返回其首记录的下标。记录 / 之间通过整型下标链接。 int iResult, iStart, i1, i2; if (liststart1.key -1 / 最多只含一个记录 int mid = (left + right)/2; / 分别排序左、右半部分，并归并所得的两个已排序链表 return ListMerge(list, rMergeSort(list, left, mid), rMergeSort(list, mid+1, right); 当需要对list0, , listn1排序时，可调用 rMergeSort(list, 0, n1)。此排序也是稳定的。 54 JYP 7.6 堆排序 堆排序只需要O(1)的辅助空间，同时其最坏和平 均时间复杂性也都是O(n log n)。 堆排序通过最大堆的插入和删除操作实现排序： 首先将n个记录插入一个初始为空的堆， 接着逐个从堆中取出记录。 然而，还可以通过函数adjust更快地构建具有n个 记录的堆。 给定一棵二叉树T，其左、右子树都满足最大堆 的性质，但其根结点却不一定满足，函数adjust调 整T使得整个二叉树都满足最大堆性质。 55 JYP template void adjust (Element *tree, const int root, const int n) / 结点下标不大于n Element e = treeroot; int k = e.getKey( ); for (int j = 2*root; j = treej.getKey( ) break; / 如果k不小于左、右子女 / 中的较大者，则e可放在j的双亲处 treej/2 = treej; / 将第j个记录上移 treej/2 = e; 设以root为根的树深为d，其计算时间为O(d)。 56 JYP 算法HeapSort首先利用函数adjust构建最大堆， 如下图所示： 57 JYP 接着对记录表list作n 1遍处理，每次将当前最 大堆的第一个记录与最后一个交换，并将当前最大 堆记录数减少1，重新调整。 由于第一个记录的关键字总是堆中最大的，经过 交换该记录一定是就序的。 调用HeapSort(list, n)即可对list1, , listn排序 。 58 JYP template void HeapSort (Element *list, const int n) / 按关 / 键字非递减次序排序list1, , listn for (int i = n /2; i = 1; i-) / 将list转化为最大堆 adjust(list, i, n); for (i = n 1; i = 1; i-) / 排序list Element t = listi+1; listi+1 = list1; list1 = t; / 交换list1和listi+1 adjust(list, 1, i); / 重建堆 59 JYP 例7.7 用HeapSort对(26, 5, 77, 1, 61, 11, 59, 15, 48, 19)的排序过程： 60 JYP 61 JYP 62 JYP 63 JYP 64 JYP 分析：设2k1n = 0; i-) / 对keyi排序 for (int j = 0; j -1 ;current = listcurrent.link) /分配记录 int k = listcurrent.keyi; if (fk = -1) fk = current; else listek.link = current; ek = current; for (j = 0; fj = -1; j+);/ 找到第一个非空队列 current = fj; int last = ej; for (int k = j+1; k -1) listlast.link = fk; last = ek; listlast.link = -1; / for (i = d -1; i = 0; i-) 结束 return current;/ 返回已就序链表的第一个记录下标 73 JYP 分析：RadixSort对数据作d遍扫描，每遍扫描用 O(n+r) 时间，总计算时间是O(d(n+r)。 例7.8 设需要排序的10个数的取值范围是0, 999 。数的每一位作为一个子关键字，d =3，r =10。排 序过程如后面两页所示。 74 JYP 75 JYP 76 JYP 77 JYP 实验作业：P26025 78 JYP 7.9 外排序 7.9.1 概述 需要排序的记录表大到计算机内存不能容纳时， 内排序已不足以解决问题。 假设需要排序的记录表存放在磁盘上。由于计算 机访问内存的速度比访问磁盘的速度快得多，影响 外排序性能的主要是访问磁盘的次数。 磁盘的读、写以IO块为单位。一个IO块通常可 包含多个记录。 79 JYP 影响磁盘读写时间的有以下三个因素： 寻找时间：将读写头定位于正确的柱面所用时间 。 等待时间：本磁道中所需块旋转到读写头下所用 时间。 传输时间：将块中数据读入内存或写到磁盘所用 时间。 其中，就数据传输而言，寻找和等待都是辅助性 的，但其时间却较长。为了提高传输效率，IO块 的容量一般都较大，通常可包含数千字节。 80 JYP 外排序的最基本方法是归并，包括两个阶段： （1）根据内存容量将输入记录表分为若干段，并利 用某种内排序方法逐个对这些段排序。这些已排 序的段又称为归并段（runs）。 （2）归并第一阶段生成的归并段，直到最终只剩一 个归并段。 由于归并算法只要求同一时刻两个归并段的前端记 录在内存，因此经过归并，可以生成比内存大的 归并段。 81 JYP 例7.11 设记录表有4500个记录，可用于排序的计 算机内存容量是750个记录，IO块长度是250个记录 。按上述方法，排序步骤如下： 82 JYP 83 JYP 分析用符号： tseek = 最长寻找时间 tlatency = 最长等待时间 trw = 读写一个IO块（250个记录）所需时间 tIO = tseek + tlatency + trw tIS = 内排序750个记录所需时间 ntm = 将n个记录从输入缓冲区归并到输出缓冲区所 需时间 84 JYP 例7.11中排序4500个记录的操作时间： 85 JYP 由于tIO tIS，tIO tm，影响计算时间的主要 因素是输入输出操作的次数，而后者又主要依赖于 对数据扫描的遍数。 例7.11中，生成初始归并段需要1遍数据扫描， 归并需要 遍数据扫描。 一遍扫描需要输入输出218个IO块，总的输入输 出时间是( + 1) 218tIO = 132tIO。 归并时间是 4500tm = 12000tm。 86 JYP 显然，k路归并（k 2）可以减少数据扫描遍数 。例如，如果在上例中采用6-路归并，则只需对数 据扫描一遍即可完成排序。 此外，初始归并段应尽可能长，从而减少初始归 并段个数。 在内存容量给定的情况下，可以利用动态流动的 思想，生成平均长度几乎是通常方法所得的两倍的 归并段。 但这些归并段长短不一，对它们归并的次序也会 影响计算时间。 下面将分别讨论这些问题。 87 JYP 7.9.2 k路归并 按2-路归并，给定m个归并段，相应的归并树有 log2m+1层，需要对数据扫描log2m遍。 采用k路归并可减少数据扫描遍数。如下图对16 个归并段进行4-路归并只需扫描数据2遍： 88 JYP 一般地，采用k路归并需要对数据扫描logkm遍 。因此，当k 2时，采用k路归并可有效减少输入 输出时间。 但k路归并要求从k个归并段的前端记录中选择 关键字最小的输出。 可以采用具有k个叶结点的败者树来选择关键字 最小的记录。从败者树中每选一个最小记录并重新 调整需要O(log2k)时间，所以对n个记录归并一遍需 要的时间是O(n log2k)。 归并logkm遍的CPU处理时间是O(n log2k logkm) = O(n log2m)，即与k无关。 89 JYP 还应该看到，当k超过一定范围时，输入输出时 间并不随着k的增大而减少。因为： k路归并所需的缓冲区个数随着k的增大而增加 ； 在内存容量给定情况下，缓冲区容量随着k的增 大而减小； 这又导致IO块的有效容量减小，从而使一遍数 据扫描需要更多的IO块操作。 因此，当k超过一定值时，输入输出时间反而会 随着k的增大而增加。k值的最佳选择与磁盘参数 和可用于缓冲区的内存容量有关。 90 JYP 7.9.3 生成初始归并段 用传统的内排序方法生成初始归并段，需要将内 存容纳的所有记录都排序好后再全部输出到磁盘。 从在排序过程中没有内外存数据交换的意义上看， 这属于静态方法，由此生成的归并段最多与内存容 纳的记录数同样大。 如果采用动态流动的方法，即在生成归并段的过 程中不断将记录写到磁盘，同时从磁盘读入新的记 录到内存，则可能生成比内存容量大的归并段。 91 JYP 设内存可容纳k个记录，用r0, r1, , rk1表 示，记录的输入和输出通过IO缓冲实现。 输入k个记录后，这些记录都属于当前归并段。 从属于当前归并段的内存记录中选关键字最小的 记录rq（0q 2 void runs(const int k) 3 Element *r = new Elementk; 4 int *rn = new intk; int *l = new intk; 5 for ( int i = 0; i rmax ) break; / 遇到虚拟记录，说明实际 / 记录已输出完，跳出循环 15 else rc = rq; 16 17 WriteRecord(rq); LastKey = rq.key; 18 / 输入新记录 19 if (输入结束) rnq = rmax + 1; / 生成虚拟记录，以把实 / 际记录“顶”出败者树 20 else 21 ReadRecord (rq); 22 if ( rq.key list) int n = list.Size( ); / 表list中的二叉树棵数 for (int i = 0; i class SymbolTable / 对象: 名字属性对集合，其中每个名字都是唯一的 public: SymbolTable(int size = DefaultSize); / 建立一个容量为size / 的空符号表 Boolean IsIn(Name name); / 如果name在符号表中，则返回 / TRUE，否则返回FALSE Attribute *Find(Name name); / 如果name在符号表中，则返 / 回相应属性的指针，否则返回0 void Insert(Name name, Attribute attr); / 如果name在符号表 / 中，则用attr替换原有属性，否 / 则将(name, attr)插入符号表中 124 JYP void Delete(Name name); / 如果name在符号表中，则从符 / 号表中删除(name, attr) ; 其中最基本的操作是查找、插入和删除。 符号表的表示应确保这三个基本操作的实现效率 。 在实际应用中，又常常将符号表作为元素集合， 元素的key字段表示名字或关键字，其它字段表示属 性。 125 JYP 8.2 二叉查找树 8.2.1 二叉查找树定义 定义：二叉查找树是一棵二叉树。如果不空，该 树应满足以下性质： （1） 每个元素有一个关键字，且任何两个不同的 元素的关键字不相等（即关键字唯一）； （2） 左子树（如果存在的话）中的关键字小于根 结点中的关键字； （3） 右子树（如果存在的话）中的关键字大于根 结点中的关键字； （4） 左、右子树也是二叉查找树。 126 JYP 二叉树的例子: 其中，（a）不是二叉查找树，（b）和（c）是。 127 JYP 8.2.2 二叉查找树的查找、插入和删除操作 1 查找 假设需要查找关键字为k的元素，根据二叉查找树 的性质，很容易得到其查找方法： 查找从树根开始。如果树根为0，则查找不成功。 否则，将k与树根中元素的关键字比较。如果相等 则查找成功结束。 如果k小于树根中元素的关键字则只需查找左子树 否则只需查找右子树。 子树的查找也相同。 128 JYP 由此可得函数Search： template BstNode* BST:Search(const Type k) BstNode *t = root; while (t) if (k = tdata.key) return t; if (k BstNode* BST:Search(int k) BstNode *t = root; while (t) if (k = tLeftSize) return t; if (k :Insert实现了上述策略： template Boolean BST:Insert(const Element BstNode*q = 0; while (p) q = p; if (x.key = pdata.key) return FALSE; / x.key已在树中 if (x.key ; pLeftChild = pRightChild = 0; pdata = x; if (!root) root = p; else if (x.key class AVL; template class AvlNode friend class AVL; private: Element data; AvlNode *LeftChild, *RightChild; int bf; ; 158 JYP template class AVL public: AVL(AvlNode *init=0):root(init) ; Boolean Insert(const Element Boolean Delete(const Element AvlNode* Search(const Type private: AvlNode *root; ; 159 JYP 算法Avl:Insert给出了实现上述插入和重新平衡 过程的细节。 template Boolean AVL:Insert(const Element Boolean Found, Unbalanced; int d; if (!root) / 空树 y = new AvlNode; ydata = x; root = y; rootbf = 0; rootLeftChild = rootRightChild = 0; return TRUE; 160 JYP / 阶段1：定位x的插入点，a跟踪BF为1的最近结点，f是a / 的双亲，在查找树的过程中q 紧跟p f = 0; a = p = root; q = 0; Found = FALSE; while (p f = q; if (x.key pdata.key) q = p; p = pRightChild; else y = p; Found = TRUE; / while结束 if (!Found) / 阶段2：插入和重新平衡。 y = new AvlNode; ydata = x; yLeftChild = yRightChild = 0; ybf = 0; if (x.key adata.key) p = aRightChild; b = p; d = -1; / 确定B else p = aLeftChild; b = p; d = 1; / 确定B while (p != y) if (x.key pdata.key) / p的右子树高度增加1 pbf = -1; p = pRightChild; else / p的左子树高度增加1 pbf = 1; p = pleftChild; 162 JYP Unbalanced = TRUE; / 准备判断树是否平衡 if (!(abf) | !(abf +d) / 树仍然平衡。注意abf = 0 / 表示在插入前不存在BF=1的A abf += d; Unbalanced = FALSE; if (Unbalanced) / 树不平衡，根据图8.13确定旋转类型 if (d =1) / 偏左 if (bbf = 1) / LL型：A和B的BF分别是+2和+1 aLeftChild = bRightChild; bRightChild = a; abf = 0; bbf = 0; 163 JYP else / LR型：A和B的BF分别是+2和-1 c = bRightChild; / 确定C bRightChild = cLeftChild; aLeftChild = cRightChild; cLeftChild = b; cRightChild = a; switch (cbf) case 1: / LR(b) abf = -1; bbf = 0; break; case -1: / LR(c) bbf = 1; abf = 0; break; case 0: / LR(a) bbf = 0; abf = 0; break; cbf = 0; b = c; / 总是令b为新子树的根 / LR结束 164 JYP / 偏左结束 else / 偏右，这种情况与偏左对称，在此省略 / 以b为根结点的新子树已平衡 if (!f) root = b; / a无双亲，a是根 else if (a = fleftChild) fLeftChild = b; else fRightChild = b; / if Unbalanced结束 return TRUE; / if (!found)结束 return FALSE; / AVL:Insert结束 165 JYP 分析：设h是插入前AVL树的高度，则插入时间 是O(h)。 设Nh是高度为h的AVL树包含的最少结点数。在 最稀疏情况下，该树的一棵子树的高度为h 1，另 一棵的应为h 2。而且这两棵子树都是AVL树。因 此 Nh = Nh-1 + Nh-2 + 1，N0 = 0，N1 = 1，N2 = 2 这与斐波纳契数Fh = Fh-1 + Fh-2，F0 = 0，F1 = 1相 似。 用归纳法可以证明： Nh = Fh+2 1，h0 166 JYP 根据斐波纳契数的理论， Fh+2 h 其中 = 即 Nh + 1 h 所以 h n个结点的AVL树的高度h最多是 。 其最坏情况插入时间是O(log n)。 167 JYP AVL树的高度也决定了其查找时间。绝大多数的 AVL树不处于最稀疏状态，因此其平均高度远小于 最坏情况的高度，从而可以期望AVL树的平均查找 时间接近最好情况。 实验结果表明，当n很大时，查找AVL树的平均 比较次数为log2n + 0.25，这已非常接近最好情况下 的log2n 1。 作业：P32910 168 JYP 8.4 2-3树* 8.4.1 定义与性质 如果保持查找树在高度上的绝对平衡，而允许树 结点的子女个数在2到3之间变化（即在宽度上相对 平衡），是否也能取得很好的性能呢？ 这启发我们得到2-3树的设计。 2-3树中每个内部结点的度为2或3。 度为2的结点称为2-结点，包含1个元素. 度为3的结点称为3-结点，包含2个元素。 169 JYP 定义：一棵2-3树是一棵查找树，该树或者为空 ，或者满足下列性质： （1） 每个内部结点是2-结点或3-结点。 （2） 令LeftChild和MiddleChild为2-结点的子女， dataL为该结点中的元素。LeftChild子2-3树中的所 有关键字小于dataL.key，MiddleChild子2-3树中的 所有关键字大于dataL.key。 （3） 令LeftChild，MiddleChild和RightChild为3- 结点的子女，dataL和dataR为该结点中的两个元素 ，且dataL.key class Two3; template class Two3Node friend class Two3; public: int compare(const Type); private: Element dataL, dataR; Two3Node *LeftChild, *MiddleChild, *RightChild; ; 174 JYP template class Two3 public: Two3(Type max, Two3Node *init=0):MAXKEY(max), root(init) ; / 构造函数 Boolean Insert(const Element Boolean Delete(const Element Two3Node* Search(const Type private: Two3Node *root; Type MAXKEY; ; 175 JYP 这里用统一的结点类型定义2-3树的结点。 假设任何元素的关键字都不等于MAXKEY。 规定2-结点的dataR.key = MAXKEY，其单个元 素存放在dataL中，两个子女由LeftChild和 MiddleChild指向，其RightChild字段可被赋予任意 值。 176 JYP 8.4.2 2-3树的查找 由二叉查找树查找算法易得2-3树查找算法： template Two3Node* Two3:Search(const Type k) / 查找关键字为k的元素 BstNode *p = root; while (p) switch (pcompare(k) case 1: p = pLeftChild; break; / k Boolean Two3:Insert(const Element Element if (x.key = MAXKEY) return FALSE; / 无效关键字 184 JYP if (!root) NewRoot(x, 0); return TRUE; / 空2-3树 if (!(p = FindNode(x.key) return FALSE;/ 关键字已在树中 for (Two3Node *a = 0; ; ) if (pdataR.key = MAXKEY) / p是2-结点 pPutIn(x, a); return TRUE; else / p是3-结点 Two3Node *q = new Two3Node; x = Split(p, x, a, q); a = q; if (root = p) / 根结点已分裂 NewRoot(x, a); return TRUE; else p = parent(p);/ 假设查找时已保存路径 / for循环结束 / Insert结束 185 JYP 插入操作所需的时间与2-3树的高度成正比，因 此，对于有n个结点的2-3树，Two3:Insert的时间复 杂性是O(log n)。 186 JYP 8.4.4 2-3树的删除操作 如果需删除的元素不在叶结点中，可用被删除元 素左边子树中的最大元素或右边子树的最小元素取 代需删除的元素，从而将问题转化为从叶结点中删 除元素。 下面将只考虑从叶结点删除元素的情况。 187 JYP 假设由从下图开始： 188 JYP 首先删除95，这只需将结点D的dataR设置为 MAXKEY，结果如下图所示： 189 JYP 接着删除60。这使结点C为空。C的左兄弟B是3- 结点，可以将C的双亲结点A中的50移到C，并将B 中的20的元素移到A的dataL，将B的dataR设置为 MAXKEY，结果如下图所示。这称为旋转。 190 JYP 再删除90，使得结点D为空。由于D的左兄弟C是 2-结点，且D没有右兄弟，所以不能进行前面的旋转 。但可以将D的双亲A中的80移到C，并删除结点D ，从而得到下图的结果。这称为合并。 191 JYP 接着删除50，结果如下图所示： 192 JYP 最后删除10。结点B变为空。由于B的右兄弟C是 2-结点，只能进行合并，即将B的双亲A中的20和C 中的80移到B中，并删除结点C。这又使A变为空。 如果A不是根，可以考察其左、右兄弟，进一步 执行旋转或合并。现在A是根，只需删除A，并使B 成为新的树根，如下图所示： 193 JYP 一般地，假设被删除元素在结点p中。 旋转有三种情况，如图8.18所示。 其中，如果p是其双亲r的左子女，则q为p的右兄 弟，否则q为p左兄弟。a，b，c和d是p和q 的子女。 “？”和u分别表示与旋转无关的内容和子树。 194 JYP 图8.18 1 195 JYP 图8.18 2 196 JYP 图8.18 3 197 JYP 图8.19 1 图8.19给出了当p是r的左子女时合并的两种情况 ： 198 JYP 图8.19 2 199 JYP 从2-3树的叶结点p中删除元素的主要步骤: 第1步：修改结点p以反映相应元素删除后的状态。 第2步：for (; p不含任何元素 p = r) 设r是p的双亲，q是p的左兄弟或右兄弟; if (q是3-结点) 执行旋转; else 执行合并; 第3步：if (p不含任何元素) / p一定是root 令p的左子女成为新的root; 删除结点p; 200 JYP 分析：一次旋转或合并的时间是O(1)。执行旋转 后整个删除即可完成。如果执行合并，则p将在2-3 树中向上移动一层。 在删除过程中执行的合并次数不超过2-3树的高 度。对于具有n个元素的2-3树，确定被删除元素所 在叶结点p的时间是O(log n)。 因此，删除操作的时间复杂性是O(log n)。 201 JYP 8.6 B树 8.6.1 m叉查找树 当符号表的大小超过内存容量时，诸如AVL树和 2-3树这样的平衡查找树就不适应了。 这是因为我们必须从磁盘中读取查找树结构的结 点。 例如，为了在2-3树中查找x，需要读取从树根结 点到目标结点的路径中的全部结点。在最坏情况下 ，需要O(h)次磁盘访问，其中h是2-3树的高度.当n = 107，h可达到24。 202 JYP 由于磁盘访问的代价远远大于内存访问的代价， 需要寻求能够有效减少磁盘访问次数的结构。 以后将用索引表示因规模太大而需要存储在磁盘 上的符号表。 磁盘访问的单位是I/O块，其容量一般比2-3树结 点的大得多。 203 JYP 如果用2-3树来实现索引，那么访问一个结点实 际上是访问一个I/O块，而该块中的大部分数据都是 无用的，如图8.23所示： 这反过来启发我们采用度更大的m叉查找树，以 提高I/O访问的数据利用率。 204 JYP 定义：一棵m叉查找树或者为空，或者满足下列 性质： （1） 根结点最多有m棵子树，且具有下列结构： n, A0, (K1, A1), (K2, A2), , (Kn, An) 其中，Ai是子树指针，0in class Mtree public: Triple Search(const Type protected: Mnode *root; int m; ; 类型Triple将在后面定义。 206 JYP 2-3树是3叉查找树。当然，还存在不是2-3树的3 叉查找树。下图的3叉查找树就不是2-3树： 207 JYP 8.6.2 m叉查找树的查找 假设需要在m叉查找树T中查找关键字x，且T存 储在磁盘上。还假设K0 = ，Kn+1 = +。 首先，从磁盘读取根结点。通过搜索根结点中的 关键字（例如用二分查找），可以确定i，使得Kix Triple Mtree:Search(const Type for (Mnode *p = root, *q = 0; p; q = p, p = Ai) 从磁盘读取位于p的结点; 令该结点对应于n, A0, (K1, A1), (K2, A2), , (Kn, An); Kn+1 = MAXKEY; 确定i，使得Ki class Btree : public Mtree public: / Search从Mtree继承 Boolean Insert(const Type Boolean Delete(const Type ; 213 JYP 2-3树是3阶B树。所有2阶B树都是满二叉树。因 此，只有当关键字个数为2k 1时（k0）才存在2阶 B树。 然而，对于任意n0和m3，总存在一棵包含n个 关键字的m阶B树。 214 JYP B树中的关键字个数 失败结点处于第h + 1层的m阶B树最多可容纳mh 1个关键字。 那么其中关键字的最小个数N是多少呢？ 根据定义，如果h 1，根结点至少有2个子女， 即第2层至少有2个结点。这2个结点又都至少有 m/2个子女，即第3层至少有2m/2个结点。第4层 至少有2m/22个结点，依此类推，第h层至少有 2m/2h-2个结点。 215 JYP 假设K0 = ，KN+1 = +。如果树中的关键字是 K1, K2, , KN且Ki 1。 反过来，hlogm/2(N + 1) / 2 + 1。 216 JYP 查找的最大访问次数是h。当m = 300， N6.75106 3，hlog150(3.375106 - 1) + 1 由于h是整数，所以h3。 因此，采用高阶B树可用很少的磁盘访问次数搜 索大规模索引。 217 JYP m的选择 虽然高阶B树的高度大大减少，但m也不是越大 越好。 如果索引有N个元素，则m = N +1阶的B树的高 度只是1。但这时m的选择显然不合理，因为按假设 ，内存不可能容纳整个索引。因此，表示索引的单 个结点不可能读入内存处理。 为了合理选择m，必须确定一个目标，这就是使 在B树中查找关键字x的时间最少。该时间包括两方 面：（1）从磁盘读入结点的时间和（2）在结点中 查找x的时间。 218 JYP 假设m阶B树的结点大小固定，且足以容纳n, A0, 以及m 1个三元组(Ki, Ai, Bi)，1i Boolean Btree:Insert(const Type / p是可插入结点指针 if (j) return FALSE; / x已在B树中 Mnode *A = 0; for (Type K = x; p; K = Km/2, A = q, p = parent(p) / (K, A)是要插入的二元组，根结点的双亲为0 将 (K, A) 插入结点p的适当位置; 令新的p结点的结构为：n, A0, (K1, A1), , (Kn, An); 227 JYP if (n 2时构建具有p个结点的B树的最多 分裂次数s=p2： 231 JYP 从直觉上也能看到，当m较大时，一个结点在内 容充实到需要分裂之前，需要足够的积累。 一棵具有p个结点的m阶B树至少有 1 + (m/2 1)( p 1) 个关键字 因为根结点至少有1个关键字，其余结点每个至少有 m/2 1个关键字。 因此平均分裂次数savg可如下确定： savg = 总分裂次数/N (p 2)/1 + (m/2 1)( p 1) Boolean Btree:Delete (const Type if (!j) return FALSE;/ x不在树中 令p 的结构为：n, A0, (K1, A1), , (Kn, An)且Ki = x; if (A0) /p不是叶结点，用Ki的右子树中最左关键字替换之 for (q =Ai; q不是叶结点; q = ); / 假设q的结构为： / nq, , ( , ), , ( , ) 用 替换结点p中的Ki 并将修改后的结点p写到磁盘; p = q; i = 1; 令新结点p 的结构为：n, A0, (K1, A1), , (Kn, An); / if(A0)结束 241 JYP 从叶结点p=n, A0, (K1, A1), , (Kn, An)中删除 (Ki, Ai); n-; while (n = m/2 ) / 旋转 (Kn+1, An+1) = ( , ); n+; / 修改结点p = ;/ 修改结点z (ny, , ( , ), ) = (ny-1, , ( , ), );/ 修改y 将结点p, y, z输出到磁盘上; return TRUE; / if(ny = m/2)结束 242 JYP / 合并结点p、y和 r = 2* m/2 - 2; 将r, A0, (K1, A1), , (Kn, An), ( , ),( , ), , ( , )输出到磁盘位置p处; 释放结点y占用的磁盘空间; (n, A0, (K1, A1), ) = (nz-1, , ( , ), ( , ), ); p = z; / if (p有最邻近的右兄弟y)结束 else / p一定最左邻兄弟，这与右兄弟情况对称，省略 / if-else以及while结束 if (n) 将p = n, A0, (K1, A1), , (Kn, An)输出到磁盘上; else root = A0; 释放结点p占用的磁盘空间; / Btree:Delete结束 243 JYP 分析：还是假设在自顶向下的查找中访问的结点 都保存在内存中，从而在自底向上的重构过程中不 必再次从磁盘读入。 对于高度为h的B树，找到需删除关键字所在的结 点并将删除转化为从叶结点删除问题需要h + 1次磁 盘访问。 在最坏情况下，从根到叶路径的后h 2个结点都 发生合并