大学《数据结构》第八章：查找-第三节-树表的查找（二）

第三节树表的查找（二）二、B树1、B树的概念（1）B树的定义一棵m（m≥3）阶的B树，或为空树，或为满足下列性质的m叉树：①每个结点至少包含下列信息域：（n，p0，k1，p1，k2，…，kn，pn）其中，n为关键字的个数；ki（1≤i≤n）为关键字，且ki

<ki+1（1≤i≤n-1）；pi（0≤i≤n）为指向子树根结点的指针，且pi所指向子树中所有结点的关键字均小于ki+1，pn所指子树中所有结点关键字均大于kn。②树中每个结点至多有m棵子树。③若树为非空，则根结点至少有1个关键字，至多有m-1个关键字。因此，若根结点不是叶子，则它至少有两棵子树。④所有的叶结点都在同一层上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向它们的指针均为空），叶子的层数为树的高度h。⑤每个非根结点中所包含的关键字个数满足：

-1≤n≤m-1。因为每个内部结点的度数正好是关键字总数加1，所以，除根结点之外的所有非终端结点（非叶子结点的最下层的结点称为终端结点）至少有棵子树，至多有m棵子树。（2）实例下图是一棵4阶的B树（3）B树的结点类型定义#definem10//m为B树的阶，结点中关键字最多可有m-1个typedefstructnode{intkeynum；//结点中关键字个数，即结点的大小KeyTypekey[m]；//关键字向量，key[0]不用struct*parent；//指向双亲结点structnode*ptr[m]；//子树指针向量}BTNode；typedefBTNode*BTree；2、B树上的插入在B树中插入一个结点的过程：先在最低层的某个非终端结点中添加一个关键字。若该结点中关键字的个数不超过m-1，则插入完成，否则要产生结点"分裂"。"分裂"结点时把结点分成两个，将中间的一个关键字拿出来插入到该结点的双亲结点上，如果双亲结点中已有m-1个关键字，则插入后将引起双亲结点的分裂，这一过程可能波及B树的根结点，引起根结点的分裂，从而使B树长高一层。【例】试画出将关键字序列：24，45，53，90，3，50，30，6l，12，70，100依次插入一棵初始为空的4阶B树中的过程。【真题选解】（例题•简答题）已知3阶B树如图所示，（1）画出将关键字6插入之后的B树；（2）画出在（1）所得树中插入关键字2之后的B树。隐藏答案3、B树上的删除（1）若需删除关键字所在结点中的关键字数目不小于，则只需要该结点中关键字和相应的指针删除。【例】画出删除图（a）中所示3阶B树上的关键字3后的B树。隐藏答案【解析】在3阶B树中，要删除的关键字所在的结点有2个关键字，直接删除该关键字和相应的指针即可。【答案】删除关键字3后的B树如图（b）所示（2）若需删除关键字所在结点中的关键字数目等于－1，即关键字数目已是最小值，直接删除该关键字会破坏B树的性质。删除这样关键字分两种情况处理：①若所删结点的左(或右)邻兄弟结点中的关键字数目不小于，则将其兄弟结点中的最大(或最小)的关键字上移至双亲结点中，而将双亲结点中相应的关键字移至删除关键字所在结点中。【例】画出删除上面（b）图中的关键字12后的B树。隐藏答案【解析】直接删除12及其指针，关键字24所在结点就变成1叉树，不满足B树的性质，可以将关键字12结点的兄弟结点中的最小值30移双亲结点中，而将双亲结点中的关键字24移至删除关键字12所在结点中。【答案】删除关键字12后的B树如图（c）所示②若需删除关键字所在结点及其相邻的左、右兄弟(或只有一个兄弟)结点中关键字数目均等于－1，则按上述情况①的移动操作就不能实现。此时，就需要将被删结点与其左兄弟或右兄弟结点进行"合并"。【例】画出删除上面（c）图中的关键字50后的B树。隐藏答案【解析】删除50，需要将63和70合并，90单独作为双亲结点。【答案】删除（c）图中的关键字50后的B树如图（d）所示。上述情况②如果因"合并"操作引起对父结点中关键字的删除，又可能要合并结点，这一过程可能波及根，引起对根结点中关键字的删除，从而可能使B树的高度降低一层。【例】画出删除上面（d）图中的关键字24后的B树。隐藏答案【解析】删除24后，30需要37进行合并，这样需要45和90合并才能满足B树的性质，使B树的高度降低一层。【答案】删除（d）图中的关键字24后的B树如图（e）所示。4、B树上的查找（1）查找算法思想在B树中查找一个关键字等于给定值K的具体过程：若B树为非空，则首先取出树根结点，将给定值K依次与关键字向量中从高下标端（key[keynum]）开始的每个关键字进行比较，直到K≥Ki（0≤i≤n=keynum，用key[0]作为中止标志，存放给定的查找值K）为止，此时，若K=Ki且i>0，则表明查找成功，返回具有该关键字的结点的存储位置及K在key[1...keynum]中的位置；否则，其值为K的关键字只可能落在当前结点的pi所指向的子树上，接着只要在该子树上继续进行查找即可。这样，每取出一个结点比较后就下移一层，直到查找成功，或被查找的子树为空(即查找失败)为止。（2）算法描述BTNode*SearchBTree(BTreeT，KeyTypeK，int*pos)｛//从树根指针为T的B树上查找关键字为K的对应结点的存储地址及K在其中的//位置*pos，查找失败返回NULL，*pos无定义inti；BTNode*p=T；while(p!=NuLL)//从根结点开始起依次向下一层查找{i=p->keynum；//把结点中关键字个数赋给ip->key[0]=K；//设置哨兵，顺序查找key[0…keynum]while(K<p->key[i])//从后向前查找第1个小于等于K的关键字i--；if(K==key[i]&&i>0){*pos=i；returnp；}elsep=p->ptr[i]；}returnNULL；}（3）实例分析【例】分析下图所示B树，查找18的过程先和根结点a比较：把K=18赋给k0。K=18小于k1的值48，再同a结点中k0比较，k0=K，因为i=0，所以接着取出a结点的p0指向的结点b，用K与b结点中的k2=32进行比较，k=18<k2=32，而K=18>k1=16，所以再取出b结点的p1所指向的结点e，因为k=k1，因此查找成功，返回e结点的存储地址以及k1的位置pos=l。当前讲授三、B+树B+树是一种常用于文件组织的B树的变形树。一棵m阶的B+树和m阶的B树的差异在于：（1）有k个孩子的结点必含有k个关键字。（2）所有的叶结点中包含了关键字的信息及指向相应结点的指针，且叶子结点本身依照关键字的大小从小到大顺序链接。（3）所有非终端