《算法导论》18.2 B树上的基本 *** 作（搜索、创建、插入）（包含C++代码）

一、约定

本节将给出B-TREE-SEARCH、B-TREE-CREATE和B TREE-INSERT *** 作的细节。在这些过程中，我们采用两个约定:
●B树的根结点始终在主存中，这样无需对根做DISK-READ *** 作;然而，当根结点被改变后，需要对根结点做一次DISK-WRITE *** 作。
●任何被当做参数的结点在被传递之前，都要对它们先做一次DISK-READ *** 作。
给出的过程都是“单程”算法，即它们从树的根开始向下，没有任何返回向上的过程。

二、搜索B树

1、对每个内部结点x，做的是(x.n+1)路的分支选择。
2、B-TREE-SEARCH是定义在二叉搜索树上的TREE-SEARCH过程的一个直接推广。它的输入是一个指向某子树根结点x的指针，以及要在该子树中搜索的一个关键字k。因此，顶层调用的形式为B-TREE-SEARCH(T. root, k)。如果k在B树中，那么B-TREE-SEARCH返回的是由结点y和使得y. key_i=k的下标i组成的有序对(y, i)；否则，过程返回NIL。

B-TREE-SEARCH
i = 1
while i <= x.n and k > x.keyi
	i = i+1
if i <= x.n and k == x.keyi	//i小于x存储的关键字个数且等于其中一个值
	return(x,i)
elseif x.leaf	//如果x是叶结点，直接返回
	return NIL
else DISK-READ(x,ci)//如果x不是叶结点，继续调用函数
	return B-TREE-SEARCH(x,ci,k)

三、创建一棵B树

为构造一棵B树T，先用B-TREE-CREATE来创建一个空的根结点，然后调用B-TREE-INSERT来添加新的关键字。这些过程都要用到一个辅助过程ALLOCATE-NODE，它在O(1)时间内为一个新结点分配一个磁盘页。我们可以假定由ALLOCATE-NODE所创建的结点并不需要DISK-READ,因为磁盘上还没有关于该结点的有用信息。

B-TREE-CREATE(T)
x = ALLOCATE-NODE()
x.leaf = TRUE
x.n = 0
DISK-WRITE(x)
T.root = x

四、向B树中插入一个关键字

1、将新的关键字插入一个已经存在的叶结点上。由于不能将关键字插入一个满的叶结点，故引入一个 *** 作，将一个满的结点y(有2t-1个关键字)按其中间关键字( median key)y. key~t，分裂(split)为两个各含t-1个关键字的点。
2、中间关键字被提升到y的父结点，以标识两棵新树的划分点。但是如果y的父结点也是满的，就必须在插入新的关键字之前将其分裂，最终满结点的分裂会沿着树向上传播。
3、与一棵二叉搜索树一样，可以在从树根到叶子这个单程向下过程中将一个新的关键字插入B树中。为了做到这一点，当沿着树往下查找新的关键字所属位置时，就分裂沿途遇到的每个满结点(包括叶结点本身)。因此就能确保每当要分裂一个满结点y时，它的父结点不是满的。

分裂B树中的结点

过程B-TREE-SPLIT-CHILD的输入是一个非满的内部结点x(假定在主存中)和一个使x.c_i(也假定在主存中)为x的满子结点的下标i。
该过程把这个子结点分裂成两个，并调整x，使之包含多出来的孩子。要分裂一个满的根，首先要让根成为一个新的空根结点的孩子，这样才能使用B-TREE-SPLIT-CHILD。树的高度因此增加；分裂是树长高的唯一途径。

B-TREE-SPLIT-CHILD(x,i)
z = ALLOCATE-NODE()
y = x.ci			//x是被分裂的结点，y是x的第i个孩子
z.leaf = y.leaf	
z.n = t - 1
//将y的t-1个关键字给z
for j = 1 to t-1
	z.keyj = y.key(j+t)
if not y.leaf
	for j = 1 to t
		z.cj = y.c(j+t)	
y.n = t - 1	//调整y关键字个数
//将z插入为x的一个孩子
for j = x.n + 1 downto i + 1	//从i+1个孩子开始x的所有孩子都往后移动一位
	x.c(j+1) = x.cj
x.ci+1 = z						//x的第i+1个孩子成为z
for j = x.n downto i			//x的关键字也和前面一样
	x.key(j+1) = x.keyj
//提升y的中间关键字到x来分隔y和z
x.keyi = y.keyt
x.n = x.n + 1
//写出所有修改过的磁盘界面
DISK-WRITE(y)
DISK-WRITE(z)
DISK-WRITE(x)

以沿树单程下行方式向B树插入关键字

B-TREE-INSERT(T,k)
r = T.root
if r.n == 2t-1		//处理根结点为满的情况
	s = ALLOCATE-NODE()
	T.root = s
	s.leaf = FALSE
	s.n = 0
	s.c1 = r
	B-TREE-SPLIT-CHILD(s,1)
	B-TREE-INSERT-NONFULL(s,k)
else
	B-TREE-INSERT-NONFULL(r,k)

辅助的递归过程B-TREE-INSERT-NONFULL将关键字插入结点x，要求假定在调用该过程时x是非满的。 *** 作B-TREE-INSERT和递归 *** 作B-TREE-INSERT-NONFULL保证了这个假设成立。

B-TREE-INSERT-NONFULL(x,k)
i = x.n
if x.leaf
	//从尾部开始遍历，当k小于keyi的时候，不断将keyi向后移动一位，直到找到
	while i >= 1 and k < x.keyi
		x.key(i+1) = x.keyi
		i = i-1
	x.key(i+1) = k	//赋值
	x.n = x.n + 1
	DISK-WRITE(x)
else while i >= 1 and k < x.key	//决定向x的哪个子结点递归下降
		i = i - 1
	i = i + 1
	DISK-READ(x,ci)
	if x.ci.n == 2t - 1		//检查是否递归降至了一个满子结点上
		B-TREE-SPLIT-CHILD(x,i)
		if k > x.keyi	//确认向两个孩子中哪一个下降是对的
			i = i + 1
	B-TREE-INSERT-NONFULL(x,ci,k) //递归地将k插入到合适的子树中

四、C++代码

#include 
using namespace std;
static const int m = 3;  //定义最小度为3
static const int key_max = 2 * m - 1;//关键字最大个数
static const int key_min = m - 1;//关键字最小个数
static const int child_max = key_max + 1;//子节点最大个数(这里可以看出子节点数与关键字数有关)
static const int child_min = key_min + 1;//子节点最小个数

template <class T>
class BTree;//前置声明

template <class T>
class BTnode
{
    friend class BTree<T>;//友元函数
public:
    BTnode()
    {
        keyNum = 0;
        parent = NULL;//父节点初始化
        isleaf = true;
        int i;
        for (i = 0; i < child_max; i++)//子树指针数组初始化
        {
            pchild[i] = NULL;
        }
        for (i = 0; i < key_max; i++)//关键字数组初始化
        {
            keyvalue[i] = ';'}
        }
    private
:bool
    ; isleaf//判断节点是否是叶子节点int
    ; keyNum//关键字个数<
    BTnode*T>; parent//指向父节点<
    BTnode*T>[ pchild]child_max;//子树指针数组[
    T   keyvalue]key_max;//关键字数组}
;template

< classT class>
BTree public
{
://构造函数
    BTree
    ()=
    {
        root NULL ;}
    //函数作用:插入关键字

   bool
    BTree_insert ()T valueif
    {
        ( contain()value)//看树中是否有相同的关键字return
        {
            false ;}
        else
        if
        {
            ( ==root NULL )=
            {
                root new BTnode <(T>);}
            if
            ( ==root->keyNum ) key_max<
            {
                BTnode*T>= newnode new BTnode <(T>);[
                newnode->pchild0]= ; root=
                newnode->isleaf false ;//由上步 *** 作可知newnode已经有子节点SplitBlock
                (,newnode0 ,) root;//分块 *** 作=
                root ; newnode//更新根节点}
            Notfull_insert
            (,root) value;//插入块未满的 *** 作return
            true ;}
        }
    //分裂结点

    void
    SplitBlock (<BTnode*T>, node_parentint , child_index< BTnode*T>) node_child<
    {
        BTnode*T>= node_right new BTnode <(T>);=
        node_right->isleaf ; node_child->isleaf=
        node_right->keyNum ; key_minint
        ; i//node_right拷贝关键字
        for
        ( =i 0 ;< i ; key_min++ i)[
        {
            node_right->keyvalue]i= [ node_child->keyvalue+i ] child_min;}
        //判断分裂的节点是否是叶子节点,如果不是的话就要把它的孩子赋值过去
        if
        ( !)node_child->isleaffor
        {
            ( =i 0 ;< i ; child_min++ i)[
            {
                node_right->pchild]i= [ node_child->pchild+i ] child_min;[
                node_child->pchild+i ] child_min=->parent [ node_right->pchild]i;}
            }
        =
        node_child->keyNum ; key_min//更新子节点的关键字数//把父节点关键字和子指针往后移 倒序赋值
        for
        ( =i ; node_parent->keyNum; i > child_index-- i)[
        {
            node_parent->keyvalue]i= [ node_parent->keyvalue-i 1 ];[
            node_parent->pchild+i 1 ]= [ node_parent->pchild]i;[
            node_child->pchild]i=->parent [ node_parent->pchild+i 1 ];}
        ++
        node_parent->keyNum;//更新父节点关键字数[
        node_parent->pchild+child_index 1 ]= ; node_right=
        node_right->parent [ node_parent->pchild+child_index 1 ];//把中间的那个关键字上移到父节点
        [
        node_parent->keyvalue]child_index= [ node_child->keyvalue]key_min;}
    //函数作用:往没有满的节点中增加关键字

    void
    Notfull_insert (<BTnode*T>, node) T valueint
    {

        = node_keynum ; node->keyNum//获取节点关键字数if
        ( )node->isleaf//node是叶子节点while
        {
            ( 0node_keynum > && < value [ node->keyvalue-node_keynum 1 ])[
            {
                node->keyvalue]node_keynum= [ node->keyvalue-node_keynum 1 ];//把关键字往后移动--
                ;node_keynum}
            [
            node->keyvalue]node_keynum= ; value++
            node->keyNum;}
        else
        //node是内部节点while
        {
            ( 0node_keynum > && < value [ node->keyvalue-node_keynum 1 ])--
            {
                ;node_keynum}
            //在比它小和比它大中间那个子节点中找合适位置,
            //如果它比所有的都小则在第一个子节点中寻找
            <
            BTnode*T>= node_child [ node->pchild]node_keynum;if
            ( ==node_child->keyNum ) key_maxSplitBlock
            {
                (,node, node_keynum) node_child;if
                ( [value > node->keyvalue]node_keynum)//插入值和子节点中间的值比较=
                {
                    node_child [ node->pchild+node_keynum 1 ];}
                }
            Notfull_insert
            (,node_child) value;//继续往下寻找合适的位置}
        }
    //查找是否有相同元素在数中

    bool
    contain ()T valueif
    {
        ( BTree_find(,root) value!= NULL )return
            true ;return
        false ;}
    //函数作用:查找是否有相同元素在树中

    <
    BTnode*T>BTree_find (<BTnode*T>, node) T valueif
    {
        ( ==node NULL )//当前节点为空的时候return
        {
            NULL ;}
        else
        //当前节点不为空int
        {
            ; i//在比它小和比它大的中间子节点中寻找相等的
            for
            ( =i 0 ;< i ; node->keyNum++ i)if
            {
                ( <=value [ node->keyvalue]i)break
                {
                    ;}
                }
            //校验当前的关键字是否等于查找的关键字
            if
            ( <i && node->keyNum == value [ node->keyvalue]i)//i是下标最大值keyNum-1return
            {
                ; node}
            else
            //如果之前比查找关键没有相等的关键字并且当前节点是叶子节点的话
            {
                //那么在B树中没有一样的关键字(因为后面比关键字更大)
                if
                ( )node->isleafreturn
                {
                    NULL ;}
                else
                //如果不是叶子节点则在下面的子节点中寻找return
                {
                    BTree_find ([node->pchild]i,) value;//这里的return别忘了}
                }
            }
        }
    //打印元素

    void
    printpoint (<BTnode*T>, nodeint ) countif
    {
        ( !=node NULL )//判断元素是否为空int
        {
            , i; j//每个节点从小到大打印
            for
            ( =i 0 ;< i ; node->keyNum++ i)//判断是否叶节点,不是的话则要往子节点中寻找打印
            {
                if
                ( !)node->isleaf//判断是否是叶子节点printpoint
                {
                    ([node->pchild]i,- count 3 );}
                for
                ( =j ; count0 j >= ;-- j)<<
                {
                    cout "-" ;}
                <<
                cout "|" << [ node->keyvalue]i<< "|" << ; endl}
            if
            ( !)node->isleaf//子节点数比关键字数多一个printpoint
            {
                ([node->pchild]i,- count 3 );}
            }
        }
    //printpoint无参函数传递值过去

    void
    printpoint ()printpoint
    {
        (,root* key_max 5 );}
    private
:<
    BTnode*T>; root//根节点}
;