第三节 - 树表的查找（二）
发布时间：2020-09-20 11:18来源：未知
第三节 树表的查找（二）
二、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树的结点类型定义
#define m 10 //m为B树的阶，结点中关键字最多可有m-1个
typedef struct node
{int keynum； //结点中关键字个数，即结点的大小
KeyType key[m]； //关键字向量，key[0]不用
struct *parent； //指向双亲结点
struct node *ptr[m]； //子树指针向量
}BTNode；
typedef BTNode *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树。
（2）若需删除关键字所在结点中的关键字数目等于－1，即关键字数目已是最小值，直接删除该关键字会破坏B树的性质。删除这样关键字分两种情况处理：
① 若所删结点的左(或右)邻兄弟结点中的关键字数目不小于，则将其兄弟结点中的最大(或最小)的关键字上移至双亲结点中，而将双亲结点中相应的关键字移至删除关键字所在结点中。
【例】画出删除上面（b）图中的关键字12后的B树。
② 若需删除关键字所在结点及其相邻的左、右兄弟(或只有一个兄弟)结点中关键字数目均等于－1，则按上述情况①的移动操作就不能实现。此时，就需要将被删结点与其左兄弟或右兄弟结点进行"合并"。
【例】画出删除上面（c）图中的关键字50后的B树。
上述情况②如果因"合并"操作引起对父结点中关键字的删除，又可能要合并结点，这一过程可能波及根，引起对根结点中关键字的删除，从而可能使B树的高度降低一层。
【例】画出删除上面（d）图中的关键字24后的B树。
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 (BTree T，KeyType K，int * pos)
｛ //从树根指针为T的B树上查找关键字为K的对应结点的存储地址及K在其中的
//位置*pos，查找失败返回NULL，*pos无定义
int i；
BTNode *p=T；
while (p!=NuLL) //从根结点开始起依次向下一层查找
{i=p->keynum； //把结点中关键字个数赋给i
p->key[0]=K； //设置哨兵，顺序查找key[0…keynum]
while(K <p-> key[i]) //从后向前查找第1个小于等于K的关键字
i--；
if(K==key[i] && i>0)
{*pos=i；return p；
}
else
p=p->ptr[i]；
}
return NULL；
}
（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）所有非终端结点可看成是索引部分，结点中仅含有其子树（根结点）中的最大关键字（或最小）关键字。
下图所示是一棵3阶的B+树。通常在B+树上有两个头指针root和sqt，前者指向根结点，后者指向关键字最小的叶子结点。因此，可以对B+树进行两种查找运算：一种是从最小关键字起进行顺序查找，另一种是从根结点开始进行随机查找。
