bintree.c

#include <stdio.h>
#include <stdlib.h>
#include "bintree.h"


bintree_t *newBT(int i)
{
    bintree_t *t =  (bintree_t *)malloc(sizeof(bintree_t));
    t->left = t->right = NULL;
    t->node = i;
    return t;
}


int Bsearch(bintree_t *t, int i)
{
    if (t->node==i) {
        return 1;
    }else if (t->node>i) {
        /* left */
        if (t->left==NULL) {
            return 0;
        }else {
            return search(t->left, i);
        }
    }else {
        /* right */
        if (t->right==NULL) {
            return 0;
        }else {
            return search(t->right, i);
        }
    }
}


void Binsert(bintree_t *t, int i)
{
    if (t->node>i) {
        if (t->left==NULL)
            t->left = newBT(i);
        else
            Binsert(t->left, i);
    }else if (t->node<i) {
        if (t->right==NULL)
            t->right = newBT(i);
        else
            Binsert(t->right, i);
    }
}


void Bdelete(bintree_t *t)
{
    if (t!=NULL) {
        bintree_t *right = t->right;
        bintree_t *left = t->left;
        free(t);
        delete(left);
        delete(right);
    }
}

bintree.h

#ifndef __BINTREE_H__
#define __BINTREE_H__

/* left>right unbalanced tree */
typedef struct bintree_t {
    struct bintree_t *left;
    struct bintree_t *right;
    int               node;
} bintree_t;


bintree_t *newBT(int i);
int Bsearch(bintree_t *t, int i);
void Binsert(bintree_t *t, int i);
void Bdelete(bintree_t *t);


#endif  /* __BINTREE_H__ */

Bplustree.c

#include <stdio.h>
#include <stdlib.h>
#include "bintree.h"
#include "Bplustree.h"




int main(void)
{
    return 0;
}


record_t *newREC(char *rec_val)
{
}


Bplustree_t *newBPtree(void)
{
}


Bplustree_t BPinsert(Bplustree_t *tree, record_t *r)
{
}


char *BPselect(Bplustree_t *tree, int key)
{
}


void BPdelete(Bplustree_t *tree, int key)
{
}

Bplustree.h

#ifndef __BPLUSTREE_H__
#define __BPLUSTREE_H__

#define LENGTH 3                   /* the length of each node */

/* from Wikipedia -- B+ tree */
/* If nodes of the B+ tree are organised as arrays of elements, then it may take a considerable time to insert or delete an element as half of the array will need to be shifted on average. To overcome this problem elements inside a node can be organized in a binary tree or a B+ tree instead of an array. */

/* note */
/* the leaves of the B+ trees don't have a link to another leaf */




/* record */
typedef struct {
    int key;
    char *rec_value;
} record_t;


/* B+ tree */
typedef struct Bplustree_t {
    struct bintree_t *keynode; /* keys are managed as a binary tree */
    struct Bplustree_t *child[LENGTH]; /* child trees */
    struct record_t *records[LENGTH]; /* records */
} Bplustree_t;




record_t *newREC(char *rec_val);
Bplustree_t *newBPtree(void);
Bplustree_t BPinsert(Bplustree_t *tree, record_t *r);
char *BPselect(Bplustree_t *tree, int key);          /* return rec_value */
void BPdelete(Bplustree_t *tree, int key);


#endif  /* __BPLUSTREE_H__ */

Makefile

Bplustree: Bplustree.c bintree.c
	gcc Bplustree.c bintree.c