#define M 3 
/* B 樹的階，即非根節點中鍵的最小數目*/ 
typedef int typekey; 
typedef struct btnode {    /* B-Tree 節點 */ 
    int d;    /* 節點中鍵的數目 */ 
    typekey k[2*M];    /* 鍵 */ 
    char *v[2*M];    /* 值 */ 
    struct btnode *p[2*M+1];    /* 指向子樹的指針 */ 
} node, *btree; 
/* 
* 每個鍵的左子樹中的所有的鍵都小于這個鍵， 
* 每個鍵的右子樹中的所有的鍵都大于等于這個鍵。 
* 葉子節點中的每個鍵都沒有子樹。 
*/ 

/* 當 M 等于 1 時也稱為 2-3 樹 
*    +----+----+ 
*    | k0 | k1 |                     
*  +-+----+----+--- 
*  | p0 | p1 | p2 | 
*  +----+----+----+ 
*/ 
extern int btree_disp; /* 查找時找到的鍵在節點中的位置 */ 
extern char * InsValue; /* 與要插的鍵相對應的值 */ 

 btree search(typekey, btree); 
 btree insert(typekey,btree); 
 btree deleteB(typekey,btree); 
 int height(btree); 
 int count(btree); 
 double payload(btree); 
 btree deltree(btree); 
/* end of btrees.h */ 

/*******************************************************/ 

/* btrees.c */ 
#include <stdlib.h> 
#include <stdio.h> 


btree search(typekey, btree); 
btree insert(typekey,btree); 
btree deleteB(typekey,btree); 
int height(btree); 
int count(btree); 
double payload(btree); 
btree deltree(btree); 

static void InternalInsert(typekey, btree); 
static void InsInNode(btree, int); 
static void SplitNode(btree, int); 
static btree NewRoot(btree); 

static void InternalDelete(typekey, btree); 
static void JoinNode(btree, int); 
static void MoveLeftNode(btree t, int); 
static void MoveRightNode(btree t, int); 
static void DelFromNode(btree t, int); 
static btree FreeRoot(btree); 

static btree delall(btree); 
static void Error(int,typekey); 

int btree_disp; /* 查找時找到的鍵在節點中的位置 */ 
char * InsValue = NULL; /* 與要插的鍵相對應的值 */ 
static int flag; /* 節點增減標志 */ 
static int btree_level = 0; /* 多路樹的高度 */ 
static int btree_count = 0; /* 多路樹的鍵總數 */ 
static int node_sum = 0;  /* 多路樹的節點總數 */ 
static int level; /* 當前訪問的節點所處的高度 */ 
static btree NewTree; /* 在節點分割的時候指向新建的節點 */ 
static typekey InsKey; /* 要插入的鍵 */ 

btree search(typekey key, btree t) 
{ 
    int i,j,m; 
    level=btree_level-1; 
    while (level >= 0){ 
        for(i=0, j=t->d-1; i<j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m)); 
        if (key == t->k [ i ]){ 
            btree_disp = i; 
            return t; 
        } 
        if (key > t->k [ i ]) /* i == t->d-1 時有可能出現 */ 
            i++; 
        t = t->p[ i ]; 
        level--; 
    } 
    return NULL; 
} 

btree insert(typekey key, btree t) 
{ 
    level=btree_level; 
    InternalInsert(key, t); 
    if (flag == 1)  /* 根節點滿之后，它被分割成兩個半滿節點 */ 
        t=NewRoot(t);    /* 樹的高度增加 */ 
    return t; 
} 

void InternalInsert(typekey key, btree t) 
{ 
    int i,j,m; 

    level--; 
    if (level < 0){ /* 到達了樹的底部: 指出要做的插入 */ 
        NewTree = NULL; /* 這個鍵沒有對應的子樹 */ 
        InsKey = key; /* 導致底層的葉子節點增加鍵值+空子樹對 */ 
        btree_count++; 
        flag = 1; /* 指示上層節點把返回的鍵插入其中 */ 
        return; 
    } 
    for(i=0, j=t->d-1; i<j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m)); 
    if (key == t->k[ i ]) { 
        Error(1,key); /* 鍵已經在樹中 */ 
        flag = 0; 
        return; 
    } 
    if (key > t->k[ i ]) /* i == t->d-1 時有可能出現 */ 
        i++; 
    InternalInsert(key, t->p[ i ]); 

    if (flag == 0) 
        return; 
    /* 有新鍵要插入到當前節點中 */ 
    if (t->d < 2*M) {/* 當前節點未滿 */ 
        InsInNode(t, i); /* 把鍵值+子樹對插入當前節點中 */ 
        flag = 0; /* 指示上層節點沒有需要插入的鍵值+子樹，插入過程結束 */ 
    } 
    else /* 當前節點已滿，則分割這個頁面并把鍵值+子樹對插入當前節點中 */ 
        SplitNode(t, i); /* 繼續指示上層節點把返回的鍵值+子樹插入其中 */ 
} 

/* 
* 把一個鍵和對應的右子樹插入一個節點中 
*/ 
void InsInNode(btree t, int d) 
{ 
    int i; 
    /* 把所有大于要插入的鍵值的鍵和對應的右子樹右移 */ 
    for(i = t->d; i > d; i--){ 
        t->k[ i ] = t->k[i-1]; 
        t->v[ i ] = t->v[i-1]; 
        t->p[i+1] = t->p[ i ]; 
    } 
    /* 插入鍵和右子樹 */ 
    t->k[ i ] = InsKey; 
    t->p[i+1] = NewTree; 
    t->v[ i ] = InsValue; 
    t->d++; 
} 
/* 
* 前件是要插入一個鍵和對應的右子樹，并且本節點已經滿 
* 導致分割這個節點，插入鍵和對應的右子樹， 
* 并向上層返回一個要插入鍵和對應的右子樹 
*/ 
void SplitNode(btree t, int d) 
{     
    int i,j; 
    btree temp; 
    typekey temp_k; 
    char *temp_v; 
    /* 建立新節點 */ 
    temp = (btree)malloc(sizeof(node)); 
    /* 
     *   +---+--------+-----+-----+--------+-----+ 
     *   | 0 | ...... |  M  | M+1 | ...... |2*M-1| 
     *   +---+--------+-----+-----+--------+-----+ 
     *   |<-      M+1     ->|<-        M-1     ->|   
     */ 
    if (d > M) { /* 要插入當前節點的右半部分 */ 
        /* 把從 2*M-1 到 M+1 的 M-1 個鍵值+子樹對轉移到新節點中, 
         * 并且為要插入的鍵值+子樹空出位置 */ 
        for(i=2*M-1,j=M-1; i>=d; i--,j--) { 
            temp->k[j] = t->k[ i ]; 
            temp->v[j] = t->v[ i ]; 
            temp->p[j+1] = t->p[i+1]; 
        } 
        for(i=d-1,j=d-M-2; j>=0; i--,j--) { 
            temp->k[j] = t->k[ i ]; 
            temp->v[j] = t->v[ i ]; 
            temp->p[j+1] = t->p[i+1]; 
        } 
        /* 把節點的最右子樹轉移成新節點的最左子樹 */ 
        temp->p[0] = t->p[M+1]; 
        /* 在新節點中插入鍵和右子樹 */ 
        temp->k[d-M-1] = InsKey; 
        temp->p[d-M] = NewTree; 
        temp->v[d-M-1] = InsValue; 
        /* 設置要插入上層節點的鍵和值 */ 
        InsKey = t->k[M]; 
        InsValue = t->v[M]; 

    } 
    else { /* d <= M */ 
        /* 把從 2*M-1 到 M 的 M 個鍵值+子樹對轉移到新節點中 */ 
        for(i=2*M-1,j=M-1; j>=0; i--,j--) { 
            temp->k[j] = t->k[ i ]; 
            temp->v[j] = t->v[ i ]; 
            temp->p[j+1] = t->p[i+1]; 
        } 
        if (d == M) /* 要插入當前節點的正中間 */ 
            /* 把要插入的子樹作為新節點的最左子樹 */ 
            temp->p[0] = NewTree; 
            /* 直接把要插入的鍵和值返回給上層節點 */ 
        else { /* (d<M) 要插入當前節點的左半部分 */ 
            /* 把節點當前的最右子樹轉移成新節點的最左子樹 */ 
            temp->p[0] = t->p[M]; 
            /* 保存要插入上層節點的鍵和值 */ 
            temp_k = t->k[M-1]; 
            temp_v = t->v[M-1]; 
            /* 把所有大于要插入的鍵值的鍵和對應的右子樹右移 */ 
            for(i=M-1; i>d; i--) { 
                t->k[ i ] = t->k[i-1]; 
                t->v[ i ] = t->v[i-1]; 
                t->p[i+1] = t->p[ i ]; 
            } 
/* 在節點中插入鍵和右子樹 */ 
            t->k[d] = InsKey; 
            t->p[d+1] = NewTree; 
            t->v[d] = InsValue; 
            /* 設置要插入上層節點的鍵和值 */ 
            InsKey = temp_k; 
            InsValue = temp_v; 
        } 
    } 
    t->d =M; 
    temp->d = M; 
    NewTree = temp; 
    node_sum++; 
} 

btree deleteB(typekey key, btree t) 
{ 
    level=btree_level; 
    InternalDelete(key, t); 
    if (t->d == 0) 
    /* 根節點的子節點合并導致根節點鍵的數目隨之減少， 
     * 當根節點中沒有鍵的時候，只有它的最左子樹可能非空 */ 
        t=FreeRoot(t); 
    return t; 
} 

void InternalDelete(typekey key, btree t) 
{ 
    int i,j,m; 
    btree l,r; 
    int lvl; 

    level--; 
    if (level < 0) { 
        Error(0,key); /* 在整個樹中未找到要刪除的鍵 */ 
        flag = 0; 
        return; 
    } 
    for(i=0, j=t->d-1; i<j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m)); 
    if (key == t->k[ i ]) { /* 找到要刪除的鍵 */ 
        if (t->v[ i ] != NULL) 
            free(t->v[ i ]); /* 釋放這個節點包含的值 */ 
        if (level == 0) { /* 有子樹為空則這個鍵位于葉子節點 */ 
            DelFromNode(t,i); 
            btree_count--; 
            flag = 1; 
            /* 指示上層節點本子樹的鍵數量減少 */ 
            return; 
        } else { /* 這個鍵位于非葉節點 */ 
            lvl = level-1; 
            /* 找到前驅節點 */ 
            r = t->p[ i ]; 
            while (lvl > 0)  { 
                r = r->p[r->d]; 
                lvl--; 
            } 
            t->k[ i ]=r->k[r->d-1]; 
            t->v[ i ]=r->v[r->d-1]; 
            r->v[r->d-1]=NULL; 
            key = r->k[r->d-1]; 
        } 
    } 
    else if (key > t->k[ i ]) /* i == t->d-1 時有可能出現 */ 
        i++;          
    InternalDelete(key,t->p[ i ]); 
    /* 調整平衡 */ 
    if (flag == 0) 
        return; 
    if (t->p[ i ]->d < M) { 
        if (i == t->d) /* 在最右子樹中發生了刪除 */ 
            i--; /* 調整最右鍵的左右子樹平衡 */ 
        l = t->p [ i ]; 
        r = t->p[i+1]; 
        if (r->d > M) 
            MoveLeftNode(t,i); 
        else if(l->d > M) 
            MoveRightNode(t,i); 
        else { 
            JoinNode(t,i); 
            /* 繼續指示上層節點本子樹的鍵數量減少 */ 
            return; 
        } 
        flag = 0; 
        /* 指示上層節點本子樹的鍵數量沒有減少，刪除過程結束 */ 
    } 
} 

/* 
* 合并一個節點的某個鍵對應的兩個子樹 
*/ 
void JoinNode(btree t, int d) 
{ 
    btree l,r; 
    int i,j; 
    l = t->p[d]; 
    r = t->p[d+1]; 

    /* 把這個鍵下移到它的左子樹 */ 
    l->k[l->d] = t->k[d]; 
    l->v[l->d] = t->v[d]; 
    /* 把右子樹中的所有鍵值和子樹轉移到左子樹 */ 
    for (j=r->d-1,i=l->d+r->d; j >= 0 ; j--,i--) { 
        l->k[ i ] = r->k[j]; 
        l->v[ i ] = r->v[j]; 
        l->p[ i ] = r->p[j]; 
    } 
    l->p[l->d+r->d+1] = r->p[r->d]; 
    l->d += r->d+1; 
    /* 釋放右子樹的節點 */ 
    free(r); 
    /* 把這個鍵右邊的鍵和對應的右子樹左移 */ 
    for (i=d; i < t->d-1; i++) { 
        t->k[ i ] = t->k[i+1]; 
        t->v[ i ] = t->v[i+1]; 
        t->p[i+1] = t->p[i+2]; 
    } 
    t->d--; 
    node_sum--; 
} 
/* 
* 從一個鍵的右子樹向左子樹轉移一些鍵，使兩個子樹平衡 
*/ 
void MoveLeftNode(btree t, int d) 
{ 
    btree l,r; 
    int m; /* 應轉移的鍵的數目 */ 
    int i,j; 
    l = t->p[d]; 
    r = t->p[d+1]; 
    m = (r->d - l->d)/2; 

    /* 把這個鍵下移到它的左子樹 */ 
    l->k[l->d] = t->k[d]; 
    l->v[l->d] = t->v[d]; 
    /* 把右子樹的最左子樹轉移成左子樹的最右子樹 
     * 從右子樹向左子樹移動 m-1 個鍵+子樹對 */ 
    for (j=m-2,i=l->d+m-1; j >= 0; j--,i--) { 
        l->k[ i ] = r->k[j]; 
        l->v[ i ] = r->v[j]; 
        l->p[ i ] = r->p[j]; 
    } 
    l->p[l->d+m] = r->p[m-1]; 
    /* 把右子樹的最左鍵提升到這個鍵的位置上 */ 
    t->k[d] = r->k[m-1]; 
    t->v[d] = r->v[m-1]; 
    /* 把右子樹中的所有鍵值和子樹左移 m 個位置 */ 
    r->p[0] = r->p[m]; 
    for (i=0; i<r->d-m; i++) { 
        r->k[ i ] = r->k[i+m]; 
        r->v[ i ] = r->v[i+m]; 
        r->p[ i ] = r->p[i+m]; 
    } 
    r->p[r->d-m] = r->p[r->d]; 
    l->d+=m; 
    r->d-=m; 
} 
/* 
* 從一個鍵的左子樹向右子樹轉移一些鍵，使兩個子樹平衡 
*/ 
void MoveRightNode(btree t, int d) 
{ 
    btree l,r; 
    int m; /* 應轉移的鍵的數目 */ 
    int i,j; 
    l = t->p[d]; 
    r = t->p[d+1]; 

    m = (l->d - r->d)/2; 
    /* 把右子樹中的所有鍵值和子樹右移 m 個位置 */ 
    r->p[r->d+m]=r->p[r->d]; 
    for (i=r->d-1; i>=0; i--) { 
        r->k[i+m] = r->k[ i ]; 
        r->v[i+m] = r->v[ i ]; 
        r->p[i+m] = r->p[ i ]; 
    } 
    /* 把這個鍵下移到它的右子樹 */ 
    r->k[m-1] = t->k[d]; 
    r->v[m-1] = t->v[d]; 
    /* 把左子樹的最右子樹轉移成右子樹的最左子樹 */ 
    r->p[m-1] = l->p[l->d]; 
    /* 從左子樹向右子樹移動 m-1 個鍵+子樹對 */ 
    for (i=l->d-1,j=m-2; j>=0; j--,i--) { 
        r->k[j] = l->k[ i ]; 
        r->v[j] = l->v[ i ]; 
        r->p[j] = l->p[ i ]; 
    } 
    /* 把左子樹的最右鍵提升到這個鍵的位置上 */ 
    t->k[d] = l->k[ i ]; 
    t->v[d] = l->v[ i ]; 
    l->d-=m; 
    r->d+=m; 
} 
/* 
* 把一個鍵和對應的右子樹從一個節點中刪除 
*/ 
void DelFromNode(btree t, int d) 
{ 
    int i; 
    /* 把所有大于要刪除的鍵值的鍵左移 */ 
    for(i=d; i < t->d-1; i++) { 
        t->k[ i ] = t->k[i+1]; 
        t->v[ i ] = t->v[i+1]; 
    } 
    t->d--; 
} 
/* 
* 建立有兩個子樹和一個鍵的根節點 
*/ 
btree NewRoot(btree t) 
{ 
    btree temp; 
    temp = (btree)malloc(sizeof(node)); 
    temp->d = 1; 
    temp->p[0] = t; 
    temp->p[1] = NewTree; 
    temp->k[0] = InsKey; 
    temp->v[0] = InsValue; 
    btree_level++; 
    node_sum++; 
    return(temp); 
} 
/* 
* 釋放根節點，并返回它的最左子樹 
*/ 
btree FreeRoot(btree t) 
{ 
    btree temp; 
    temp = t->p[0]; 
    free(t); 
    btree_level--; 
    node_sum--; 
    return temp; 
} 

void Error(int f,typekey key) 
{ 
    if (f) 
        printf("Btrees error: Insert %d!\n",key); 
    else 
        printf("Btrees error: delete %d!\n",key); 
} 

int height(btree t) 
{ 
    return btree_level; 
} 

int count(btree t) 
{ 
    return btree_count; 
} 
double payload(btree t) 
{ 
    if (node_sum==0) 
        return 1; 
    return (double)btree_count/(node_sum*(2*M)); 
} 
btree deltree (btree t) 
{     
    level=btree_level; 
    btree_level = 0; 
    return delall(t); 

} 
btree delall(btree t) 
{ 
    int i; 
    level--; 
    if (level >= 0) { 
        for (i=0; i < t->d; i++) 
            if (t->v[ i ] != NULL) 
                free(t->v[ i ]); 
        if (level > 0) 
            for (i=0; i<= t->d ; i++) 
                t->p[ i ]=delall(t->p[ i ]); 
        free(t); 
    } 
    return NULL; 
} 

/* end of btrees.c */