데이터 구조 - B - 트 리 찾기 및 삽입

#include < iostream >
#include < math.h >
using namespace std;

#define M 4 // B- ， 4
#define false 0
#define true 1

typedef struct BTNode
{
int keynum; // ，
struct BTNode * parent; //
int key[M + 1 ]; // ，0
struct BTNode * son[M + 1 ]; //
// Record *recptr[M+1]; // ，0 ( )
}BTNode, * BTree; // B- B-

typedef struct
{
BTNode * pt; //
int pos; // 1...m,
int tag; // 1: ，0:
}Result; // B-



//
void init_BTree(BTree & root)
{
root = NULL;
}


int search(BTree & p, int key)
{
int j;
for (j = 1 ; j <= p -> keynum; j ++ )
if (p -> key[j] > key)
{
break ;
}
return j - 1 ; //
}
Result searchBtree(BTree & root, int key)
{
// m B t key， (pt,i,tag)。
// ， tag=1， pt i key；
// ， tag=0, key , pt i i+1
int found = false ;
int i;
BTree p = root,father = NULL; // ，p ，q p
Result result; // SearchBTree

while (p && ! found)
{
i = search(p,key); // p->node[i].key≤K<p->node[i+1].key
if (i > 0 && p -> key[i] == key)
{
found = true ; //
}
else
{
father = p;
p = p -> son[i];
}
}
result.pos = i + 1 ; // pos , 1
if (found) //
{
result.pt = p;
result.tag = 1 ;
}
else // ， key i
{
result.pt = father;
result.tag = 0 ;
}
return result;
} // SearchBTree

//
void split(BTree & q, int s, BTree & ap)
{
// q ， ， ap
int i;
cout << " ! " << " " << q -> key[s] << endl;
ap = (BTree)malloc( sizeof (BTNode)); // ap
ap -> son[ 0 ] = q -> son[s]; // 0
for (i = s + 1 ;i <= M;i ++ ) // ap
{
ap -> key[i - s] = q -> key[i];
ap -> son[i - s] = q -> son[i];
} // for
ap -> keynum = M - s;
ap -> parent = q -> parent;
q -> keynum = s - 1 ; // q ， keynum
} // split

void NewRoot(BTree & root, int x, BTree & ap) //
{
// (root,r,ap) *root， root ap
BTree p;
p = (BTree)malloc( sizeof (BTNode));
if (root) //
root -> parent = p; //
p -> son[ 0 ] = root; //
root = p; // root
root -> parent = NULL; //
root -> keynum = 1 ;
root -> key[ 1 ] = x; //
root -> son[ 1 ] = ap; //
if (ap) //
ap -> parent = root; //
} // NewRoot

void insert(BTree & q, int i, int key, BTree & ap) //
{
int j;
for (j = q -> keynum; j >= i; j -- )
{
q -> key[j + 1 ] = q -> key[j];
}
q -> key[i] = key;
for (j = q -> keynum; j >= i; j -- )
{
q -> son[j + 1 ] = q -> son[j];
}
q -> son[i] = ap;
q -> keynum ++ ;
} // insert
void insertBtree(BTree & root, int key, BTree & q, int i)
{
// B- T q key[i] key[i+1] key
// ， ， T M B-
BTree ap = NULL;
int x = key;
int finished = false ;
int s;
while (q && ! finished)
{
insert(q, i, x, ap); // key ap q->key[i+1] q->son[i+1]
if (q -> keynum < M)
finished = true ; //
else
{ // *q
s = ceil(M / 2 );
x = q -> key[s];
split(q, s, ap); // q->key[s+1...M],q->son[s...M] q->recptr[s+1...M] *ap
q = q -> parent;
if (q)
i = search(q,x) + 1 ; // *q x , 1， search()
} // else
} // while
if ( ! finished) // root ( q NULL) *q *ap
NewRoot(root, x, ap); // (root,x,ap) *root， root ap
} // insertBtree

void SearchInsertBTree(BTree & root, int key) //
{
// m B *t *q key[i],key[i+1] key
// ， ， *t m B
Result rs;
rs = searchBtree(root,key);
if ( ! rs.tag) // tag=0 ，
{
cout << " ， ! " << endl;
insertBtree(root, key, rs.pt, rs.pos); // B- T re.pt key[i] key[i+1] key
}
else
{
cout << " ! " << endl;
}
} // InserBTree