#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define m 3
typedef struct _BTree{
int keynum;
struct _BTree *parent;
//Record *data[m+1]; /* Begin from 1 */
int key[m+1]; /* Begin from 1 */
struct _BTree *child[m+1]; /* Begin from 0 */
}BTree;
/* Search key from T, return the i if founded or return the maxinum i
* which T->key[i] little than key */
int Search(BTree *T, int key)
{
int i = 0;
while(++i<=T->keynum && key >= T->key[i]);
return i-1;
}
int SearchBTree(BTree *T, int key, BTree **retT, int *idx, int *ret)
{
int i=0;
BTree *p = T;
BTree *q = NULL;
int found = 0;
while(p && !found){
i=Search(p, key); // key[i] < key < key[i+1]
if(i>0 && p->key[i] == key){
found = 1;
}else{
q = p;
p = p->child[i]; // key[i] < child[i] < key[i+1]
}
}
if(found){
*retT = p;
*idx = i;
*ret = 1;
return 1;
}else{
*retT = q;
*idx = i;
*ret = 0;
return 0;
}
}
/* Insert key to T->key[i+1], insert p to T->child[i+1]
* It means the key[i] < key < key[i+1],
* child[i+1] is the point into which you can insert */
void Insert(BTree *T, int i, int key, BTree *p)
{
int j;
if(i == T->keynum){
j = i+1;
}else{
for(j=T->keynum; j>i; j--){
T->key[j+1] = T->key[j];
T->child[j+1] = T->child[j];
}
j++;
}
T->key[j] = key;
T->child[j] = p;
T->keynum++;
if(p){
p->parent = T;
}
}
void Split(BTree *T, int s, BTree **p)
{
BTree *q = malloc(sizeof(BTree));
int i;
int j = 0;
for(i=0;i<=m;i++){
q->child[i] = NULL;
q->key[i] = 0;
}
q->parent = NULL;
q->keynum = 0;
for(i=s+1, j=1; i<=T->keynum; i++, j++){
q->key[j] = T->key[i];
q->child[j-1] = T->child[i-1];
T->child[i-1] = NULL;
T->key[i] = 0;
}
q->child[j-1] = T->child[i-1];
T->child[i-1] = NULL;
T->key[i] = 0;
j--;
q->keynum = j;
T->keynum -= j;
(*p) = q;
}
/* It will be divided if the node fulfilled with keys after insertion */
int InsertBTree(BTree **T, int key, BTree *q, int i)
{
int x = key;
BTree *ap = NULL;
int finished = 0;
int s = (int)ceil((double)m/2);
BTree *p = NULL;
BTree *f = NULL;
while(q && !finished){
Insert(q, i, x, ap);
if(q->keynum < m){
finished = 1;
}else{
Split(q, s, &ap);
x = q->key[s];
q->keynum--;
f = q;
q = q->parent;
}
}
if(!finished){ //q is NULL
p = malloc(sizeof(BTree));
for(i=0;i<=m;i++){
p->child[i] = NULL;
p->key[i] = 0;
}
p->parent = NULL;
p->keynum = 1;
p->child[0] = f;
p->key[1] = x;
p->child[1] = ap;
p->parent = NULL;
*T = p;
if(ap){
ap->parent = *T;
}
}
return 1;
}
void printTree(BTree *T)
{
int i;
if(T == NULL){
return;
}
for(i=1;i<=T->keynum;i++){
printf("(");
printTree(T->child[i-1]);
printf(")");
printf("%d", T->key[i]);
}
printf("(");
printTree(T->child[i-1]);
printf(") ");
}
void main()
{
int seq[] = { 0, 13, 24, 37, 90, 53 };
int n = sizeof(seq)/sizeof(int);
int i;
BTree *T = NULL;
BTree *p = NULL;
int idx;
int found;
printf("log.anycle.com\n\n");
printf("Original data:\n");
for (i=0; i<n; i++) {
printf("%d\t", seq[i]);
}
printf("\n");
printf("Insert balance tree:\n");
for(i=1;i<n;i++){
SearchBTree(T, seq[i], &p, &idx, &found);
if(!found){
InsertBTree(&T, seq[i], p, idx);
}
}
printf("Print the tree:\n");
printTree(T);
printf("\n");
}