苗火 Nicholas

[Data structures]B-Tree

2019-7-12 萧 写技术

#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");
}

标签: Data Structures data_structures