詳細はこちら
B木 - Wikipedia
#include <stdio.h> #include <stdlib.h> #include <ctype.h> #define M 2 /* 1ページのデータ数の上限の半分 */ typedef int keytype; /* 探索のキーの型 */ typedef enum {FALSE, TRUE} boolean; typedef struct page { int n; /* データ数 */ keytype key[2 * M]; /* キー */ struct page *branch[2 * M + 1]; /* 他ページへのポインタ */ } *pageptr; pageptr root = NULL; /* B木の根 */ keytype key; boolean done, deleted, undersize; pageptr newp; /* {\tt insert()} の生成した新しいページ */ char *message; void search(void){ pageptr p; int k; p = root; while (p != NULL) { k = 0; while (k < p->n && p->key[k] < key) k++; if (k < p->n && p->key[k] == key) { message = "find"; return; } p = p->branch[k]; } message = "not find"; } pageptr newpage(void){ pageptr p; if ((p = malloc(sizeof *p)) == NULL) { printf("memory error\n"); exit(EXIT_FAILURE); } return p; } void insertitem(pageptr p, int k){ int i; for (i = p->n; i > k; i--) { p->key[i] = p->key[i - 1]; p->branch[i + 1] = p->branch[i]; } p->key[k] = key; p->branch[k + 1] = newp; p->n++; } /* {\tt key} を {\tt p->key[k]} に挿入し, ページ {\tt p} を割る */ void split(pageptr p, int k){ int j, m; pageptr q; if (k <= M) m = M; else m = M + 1; q = newpage(); for (j = m + 1; j <= 2 * M; j++) { q->key[j - m - 1] = p->key[j - 1]; q->branch[j - m] = p->branch[j]; } q->n = 2 * M - m; p->n = m; if (k <= M) insertitem(p, k); else insertitem(q, k - m); key = p->key[p->n - 1]; q->branch[0] = p->branch[p->n]; p->n--; newp = q; /* 新しいページを {\tt newp} に入れて戻る */ } /* {\tt p} から木を再帰的にたどって挿入 */ void insertsub(pageptr p){ int k; if (p == NULL) { done = FALSE; newp = NULL; return; } k = 0; while (k < p->n && p->key[k] < key) k++; if (k < p->n && p->key[k] == key) { message = "already"; done = TRUE; return; } insertsub(p->branch[k]); if (done) return; if (p->n < 2 * M) { /* ページが割れない場合 */ insertitem(p, k); done = TRUE; } else { /* ページが割れる場合 */ split(p, k); done = FALSE; } } /* キー {\tt key} をB木に挿入 */ void insert(void){ pageptr p; message = "ok"; insertsub(root); if (done) return; p = newpage(); p->n = 1; p->key[0] = key; p->branch[0] = root; p->branch[1] = newp; root = p; } /* {\tt p->key[k]}, {\tt p->branch[k+1]} を外す. */ void removeitem(pageptr p, int k){ while (++k < p->n) { p->key[k - 1] = p->key[k]; p->branch[k] = p->branch[k + 1]; } undersize = --(p->n) < M; } void moveright(pageptr p, int k){ int j; pageptr left, right; left = p->branch[k - 1]; right = p->branch[k]; for (j = right->n; j > 0; j--) { right->key[j] = right->key[j - 1]; right->branch[j + 1] = right->branch[j]; } right->branch[1] = right->branch[0]; right->n++; right->key[0] = p->key[k - 1]; p->key[k - 1] = left->key[left->n - 1]; right->branch[0] = left->branch[left->n]; left->n--; } void moveleft(pageptr p, int k){ int j; pageptr left, right; left = p->branch[k - 1]; right = p->branch[k]; left->n++; left->key[left->n - 1] = p->key[k - 1]; left->branch[left->n] = right->branch[0]; p->key[k - 1] = right->key[0]; right->branch[0] = right->branch[1]; right->n--; for (j = 1; j <= right->n; j++) { right->key[j - 1] = right->key[j]; right->branch[j] = right->branch[j + 1]; } } void combine(pageptr p, int k) /* {\tt p->branch[k - 1]}, {\tt p->branch[k]} を結合する */ { int j; pageptr left, right; right = p->branch[k]; left = p->branch[k - 1]; left->n++; left->key[left->n - 1] = p->key[k - 1]; left->branch[left->n] = right->branch[0]; for (j = 1; j <= right->n; j++) { left->n++; left->key[left->n - 1] = right->key[j - 1]; left->branch[left->n] = right->branch[j]; } removeitem(p, k - 1); free(right); } void restore(pageptr p, int k) /* 小さくなりすぎたページ {\tt p->branch[k]} を修復する */ { undersize = FALSE; if (k > 0) { if (p->branch[k - 1]->n > M) moveright(p, k); else combine(p, k); } else { if (p->branch[1]->n > M) moveleft(p, 1); else combine(p, 1); } } void deletesub(pageptr p){ int k; pageptr q; if (p == NULL) return; /* 見つからなかった */ k = 0; while (k < p->n && p->key[k] < key) k++; if (k < p->n && p->key[k] == key) { /* 見つかった */ deleted = TRUE; if ((q = p->branch[k + 1]) != NULL) { while (q->branch[0] != NULL) q = q->branch[0]; p->key[k] = key = q->key[0]; deletesub(p->branch[k + 1]); if (undersize) restore(p, k + 1); } else removeitem(p, k); } else { deletesub(p->branch[k]); if (undersize) restore(p, k); } } void delete(void){ pageptr p; deleted = undersize = FALSE; deletesub(root); /* 根から再帰的に木をたどり削除する */ if (deleted) { if (root->n == 0) { /* 根が空になった場合 */ p = root; root = root->branch[0]; free(p); } message = "erase"; } else message = "not find"; } void printtree(pageptr p) { static int depth = 0; int k; if (p == NULL) { printf("."); return; } printf("("); depth++; for (k = 0; k < p->n; k++) { printtree(p->branch[k]); printf("%d", p->key[k]); } printtree(p->branch[p->n]); printf(")"); depth--; } int main(void){ char s[2]; for ( ; ; ) { printf("挿入 I, 検索 S, 削除 D (n:整数) :"); if (scanf("%1s%d", s, &key) != 2) break; switch (s[0]) { case 'I': case 'i': insert(); break; case 'S': case 's': search(); break; case 'D': case 'd': delete(); break; default : message = "???"; break; } printf("%s\n\n", message); printtree(root); printf("\n\n"); } return 0; }