数据结构高分笔记 精彩摘录之B.docx

立志于打造最贴近考生实际的辅导书计算机考研之数据结构高分笔记率辉编著周伟张浩审核数据结构高分笔记精彩摘录之B-树7.3.2 B-树的基本操作1.B-树的查找B-树的查找很简单，是二叉排序树的扩展，二叉排序树是二路查找，B-树是多路查找。 因为B-树结点内的关键字是有序的，在结点内进行查找的时候除了顺序查找之外，还可以 用折半查找来提高效率。B-树具体查找步骤如下（key为要查找的关键字）：先让key与根结点中的关键字比较，如果key等于ki（k为结点内的关键字数组， 如7.1.1节中结点结构图所示），则查找成功。若key<k1，则到p0所指示的子树中进行继续查找（p为结点内的指针数组， 如7.1.1节中结点结构图所示）。若key>kn，则到pn所指示的子树中进行继续查找。若ki<keyi+1，则沿着指针pi 所指示的子树继续查找。如果最后遇到叶子结点，则证明查找不成功。例如图7.5,关键字key等于42,首先在根结点内查找，因42>3 0则沿着根结点中 指针p1 往下走；在子树根中查找，因39<42<45,则沿着子树根结点中指针p1往下 走，在下层结点中查找关键字42成功，查找结束。 . 、/2.B-树的插入和删除对于B-树的插入和删除操作，我们先举一个例子，通过例子最后总结出其一般方法。例题 7.4 用以下关键字序列1,2,6,7,11,4,8,13,10,5,17,9,16,2 0,3,12, 14,18,19,15创建一棵5阶B-树。对于该B-树，给出删除关键字8,16,15,4的过程。分析：和二叉排序树的建立一样，B-树的创建过程也是将关键字逐个插入到树中的过程。在进行插入或者删除之前要确定一下每个结点中关键字的个数范围，如果B-树的阶数 为m，则结点中关键字个数范围为回/2-1m-1。对于关键字的插入，需要找到插入位置。在B-树的查找过程中，当遇到叶子结点指针 时则证明查找不成功，同时也找到了插入位置，即根据叶子结点指针我们可以确定在上一层 的非叶结点中的插入位置。由此我们看出B-树插入的新结点总是落在最下层的非叶子结点 上；在插入过程中有可能破坏B-树的特性，比如新关键字的插入使得结点中关键字的个数 超出规定个数，这时要进行结点的拆分。对于关键字的删除，需要找到待删除关键字；在结点中删除关键字的过程也有可能破坏 B-树的特性，比如旧关键字的删除可能使得结点中关键字的个数少于规定个数，这时可能需要向其兄弟结点借关键字或者和其孩子结点进行关键字的交换，也可能需要进行结点的合 并。其中和当前结点的孩子结点进行关键字交换的操作可以保证删除操作也发生在最下层 的非叶子结点上。具体步骤如下：（1）求结点中关键字个数范围：由于题目要求建立5阶B-树，则关键字个数在24之间。(2)1)结点的插入：根结点最多可以容纳4个关键字，依次插入1,2,6,7后的B-树如图（a）所示：12 6 7（a）插入1,2,6,7后的结果2)当插入关键字11的时候，发现此时结点中的关键字个数变为5,超出范围，则需 拆分。取关键字数组的中间位置即5/2=3处的关键字k3=6,独立作为一个结点，即新 的根结点；将关键字6左右的关键字分别做成两个结点，作为新根结点的两个分支结点。 此时B-树如图（b）所示:（b）插入11后的结果3）新关键字总是插入在最下层的非叶结点上，插入关键字4,8,13后的B-树如图（c） 所示：4）关键字10需要插入在关键字8和11之间，此时又会出现关键字个数超出范围， 因此需要拆分。拆分时需要将关键字10并入根结点内，并将10左右的关键字做成两个新 的结点连接在根结点上。插入10并经过拆分操作后的B-树如图（d）所示：（插入关键字10后的结果5）插入关键字5,17,9,16后的B-树如图（e）所示：作）插入关键字5,17,9,16后的结果6）关键字20需要插入在关键字17之后，会造成结点关键字个数超出范围，需要拆分，（f）插入关键字20后的结果7）按照上述步骤将关键字3,12,14,18,19插入后的B-树如图（g）所示，在这之间 也需要拆分操作。（9）插入3,12,14,18,19后的结果8）插入最后一个关键字15, 15应该插入在14之后，会出现关键字个数超出范围， 则需进行拆分，将15并入根结点；15并入后又使得根结点中关键字个数超出范围，需再 次拆分，将10作为新的根结点，并将10左右的关键字做成两个新结点连接在新根结点的 指针上，这种插入一个关键字之后出现多次拆分的情况称为连锁反应。此时的B-树如图（h） 所示：（h）插入15后的结果（3）结点的删除：yS1）删除关键字8,16。关键字8在最底层的非叶子结点上，并且删除后其所在结点中 关键字的个数不会少于2,因此可以直接删除。关键字16不在最底层的非叶子结点上，可 以用17来覆盖16,然后将原来的17删掉，这里就是上边提到的和孩子结点进行关键字交 换的操作。为什么不用15来覆盖16然后删除原来的15呢，显然是因为这样做会使得15 所在的结点中关键字的个数小于2,不满足B-树的规定。此时的B-树如图（a）所示：（a）删除8,16后的结果2）删除15。15虽然也在最底层的非叶子结点上，但是不能直接删除，因为删除后当 前结点中的关键字个数小于2。这时需要向其兄弟结点借关键字，显然应该向其右兄弟来借 关键字，因为左兄弟的关键字个数已经是下限2。借关键字不能直接将右兄弟中的18移到15所在的结点上，因为这样会使得15所在的结点上出现了比17大的关键字，不满足B- 树的规定。正确的借法应该是，先用17覆盖15,再用18覆盖原来的17,最后删除原来 的18。（b）删除15后的结果合并方法合并方法二3）删除关键字4。此时4所在结点中关键字的个数已经是下限，需要借关键字，但其 左右兄弟结点的关键字数也都是下限，这里就要用到关键字的合并。我们可以先将关键字4 删除，然后将关键字5,6,7,9合并为一个结点连接在关键字3右边的指针上；也可以将 1,2,3,5合并成一个结点连接在关键字6左边的指针上，此两种合并方法的局部图如下， 因此可以看出，采用不同的合并方法将产生不同的B-树。即出现了非根的双分支结点，需要继续显然上述两种情况都已经不满足B-树的规定，进行合并，我们沿着合并方法一的路线往下进行，将3,10,13,18合并为一个新的结点， 此时的B-树为图（c）所示：（c）删除4后的结果由上边这个例子我们可以总结出对于m阶的B-树的插入和删除的一般操作：（1）插入操作按照B-树的查找方法找到插入位置（插入位置一定出现在最底层的非叶结点上），然后 直接插入；插入后检查被插入结点内关键字的个数，如果关键字个数大于m-1，则需要进行 拆分。进行拆分时，结点内的关键字已经有 m个，此时取出第回/2个关键字，并将第 1回/2-1个关键字和第回/2+1m个关键字做成两个结点连接在第回/2个关键字左右的指针上，并将第回/2个关键字插入其父结点相应的位置中；如果在其父结点内又出现了 关键字个数超出规定范围的情况，则依照上述方法继续进行拆分操作。插入操作只会使得 B-树逐渐变高而不会改变叶子结点在同一层的特性。（2）删除操作1）要删除的关键字在最底层非叶结点上，这时有三种情况:结点内的关键字个数大于回/2-1，这时可以直接删除。结点内的关键字个数等于回/2-1，并且其左右兄弟结点中，存在关键字个数大于 回/2-1的结点，则从关键字个数大于回/2-1的兄弟结点中借关键字，过程如图7.6所示。图7.6删除关键字a的过程图（a<b<c）结点内的关键字个数等于回/2-1，并且其左右兄弟结点中， 回/2-1，的结点，这时需要进行结点的合并，过程如图7.7所示。不存在关键字个数大于图7.7删除关键字a后的结点合并过程（a<b<c）要注意的是图7.7中删除关键字a后使得其父结点中关键字减少一个，因此有可能使 得其父结点中关键字个数少于规定个数，这种情况出现时要对其父结点继续进行合并操作， 方法同上。这是由于删除结点引起的连锁反应。2）要删除的关键字不在最底层非叶结点上，这需要将其转化成在最底层叶子结点上的 情况，再按1）中所讲方法进行处理。.在讲这种情况下的删除方法之前，要引入一个相邻关键字的概念，对于不在最底层非叶 子结点上的关键字a，它的相邻关键字为其左子树中值最大的关键字或者其右子树中值最小 的关键字。找a的相邻关键字的方法为，沿着a的左指针来到其子树根结点，然后沿着根 结点中最右端的关键字的右指针往下走，用同样方法一直走到最底层的非叶结点上，最底层 非叶结点上的最右端的关键字即为a的相邻关键字。这里找到的是a左边的相邻关键字， 找其右边的相邻关键字的方法类似，这与二叉排序树中找一个关键字的前驱和后继的方法是 类似的。如图7.8所示，a的相邻关键字是d,e。要删除关键字a，可以用d来取代a，然 后按照1）中所讲方法删除最底层非叶结点上的d即可，当然用e来取代a，之后删除e 也可以。图7.8 a的相邻关键字为d,e。