2-3ツリーのC実装

詳細
B木の1つのノードはN個のkeyがあって、N+1個の下級ノードがあって、二叉木は簡略化版で、1個のkeyの2個の下級node
2-3ツリーと2-3-4ツリーの領域は大きくなく、2-3ツリーは挿入時に葉ノード(サブノードがない)を見つけてから挿入し、過程ですでに3 Node(2 key)であれば分裂し、上に泡を立て、ずっと上に泡を立てる可能性がある.
2-3-4木は葉ノードを下に探す時に調整を行い、4 Node(3 key)を早めに分裂させ、下級ノードのために空間を空けるので、葉ノードが挿入された後も上に泡が立ち続けることはありません.
2-3-4ツリーは冗長性が高く、事前に分裂しなければ2-3ツリー
赤黒樹は2−3−4樹の2ノード表現であり,左傾と回転を用いて簡略化と泡立ちを行い,Rober Segwickのpptは古典的である.
B+ツリー感覚は、データベース内のデータとインデックスの関係です.インデックスはなくてもいいです.ある検索を加速させるために使用されます.
データの削除時にインデックスのメンテナンス時に問題が発生しました.
ちなみにskip listでは,並べ替えたデータに対してN個をインデックスとして抽出し,N個に対して同様のサンプリングインデックスを行い,上へ繰り返す.大量のデータに対してよく理解し、実現しやすい.インデックスとデータが分離されます.
2-3ツリー削除アルゴリズムは複雑で、ここでは実現していません.挿入と検索のみが実現され、テスト結果:

E A R C H X M P L 
A C E H L M P R X 
		(A
		C)
	(E)
		(H
		L)
(M)
		(P)
	(R)
		(X)
16 7 15 15 18 3 6 15 5 11 9 12 7 10 19 18 12 14 2 12 
2 3 5 6 7 9 10 11 12 14 15 16 18 19 
		(2)
	(3
		(5)
	6)
		(7)
(9
		(10)
	(11)
		(12
		14)
15)
		(16)
	(18)
		(19)

#include 
#include 
#include 
#include 
#include 

typedef int T;

typedef struct TreeNodeT {
	T v; //value left
	T v2; //value right
	int twins;
	struct TreeNodeT *up;
	struct TreeNodeT *left;
	struct TreeNodeT *center; //center if twins node
	struct TreeNodeT *right;
} TreeNode;

typedef int Callback(TreeNode *node, int n, int level, void *ctx); //return stop or not

TreeNode *tree_del(TreeNode *node, T v); //TODO

TreeNode *tree_top(TreeNode *e) {
	TreeNode *top = NULL;
	while (e && e->up)
		top = e->up;
	return top;
}

int tree_callback_locate(TreeNode *node, int n, int level, void *ctx) {
	T v = n == 0 ? node->v : node->v2;
	T t = (T) ctx;
	return v == t;
}

int tree_callback_verify(TreeNode *node, int n, int level, void *ctx) {
	assert(ctx);
	T v = n == 0 ? node->v : node->v2;
	T *last = (T *) ctx;
	assert(v > *last);
	*last = v;
	return 0;
}

int tree_callback_print_h(TreeNode *node, int n, int level, void *ctx) {
	printf("%d ", n == 0 ? node->v : node->v2);
	return 0;
}

int tree_callback_print_hc(TreeNode *node, int n, int level, void *ctx) {
	printf("%c ", n == 0 ? node->v : node->v2);
	return 0;
}

int tree_callback_print_v(TreeNode *node, int n, int level, void *ctx) {
	int i;
	for (i = 0; i < level; ++i) {
		printf("\t");
	}
	if (n == 0)
		printf("(");
	printf("%d", n == 0 ? node->v : node->v2);
	if ((node->twins && n == 1) || !node->twins)
		printf(")");
	printf("
");
	return 0;
}

int tree_callback_print_vc(TreeNode *node, int n, int level, void *ctx) {
	int i;
	for (i = 0; i < level; ++i) {
		printf("\t");
	}
	if (n == 0)
		printf("(");
	printf("%c", n == 0 ? node->v : node->v2);
	if ((node->twins && n == 1) || !node->twins)
		printf(")");
	printf("
");
	return 0;
}

/* return stop or not */
int tree_walk(TreeNode *node, int level, Callback cb, void *ctx) {
	if (node->left && tree_walk(node->left, level + 1, cb, ctx))
		return 1;
	if (cb(node, 0, level, ctx))
		return 1;
	if (node->twins) {
		if (node->center && tree_walk(node->center, level + 1, cb, ctx))
			return 1;
		if (cb(node, 1, level, ctx))
			return 1;
	}
	if (node->right && tree_walk(node->right, level + 1, cb, ctx))
		return 1;
	return 0;
}

static void tree_node_init_single(TreeNode* node, T v, TreeNode* left,
		TreeNode* right) {
	//shrink left to Single Node
	node->v = v;
	node->twins = 0;
	node->v2 = 0;
	node->left = left;
	if (left)
		left->up = node;
	node->center = NULL;
	node->right = right;
	if (right)
		right->up = node;
}

static TreeNode* tree_node_alloc(TreeNode* up, T v, TreeNode* left,
		TreeNode* right) {
	// new upper Single Node
	TreeNode* node = (TreeNode*) calloc(sizeof(TreeNode), 1);
	tree_node_init_single(node, v, left, right);
	node->up = up;
	return node;
}

static TreeNode *tree_node_insert(TreeNode *node, T v, TreeNode *left,
		TreeNode *right);

static TreeNode *tree_node_split(TreeNode *node, T v1, T v2, T v3, //
		TreeNode *n1, TreeNode *n2, TreeNode *n3, TreeNode *n4) {
	TreeNode *left = node; //reuse node
	//shrink left to Single Node
	tree_node_init_single(left, v1, n1, n2);

	//Create new right Single Node
	TreeNode *right = tree_node_alloc(node->up, v3, n3, n4);

	TreeNode *up = node->up;
	if (up == NULL) { // new upper Single Node
		up = tree_node_alloc(NULL, v2, left, right);
		return up;
	} else { //upper node exist, escalate
		return tree_node_insert(up, v2, left, right);
	}
}

/* insert v to up:
 * if up is single, make it twins
 * if up is twins, split
 * return NULL if no new top tree node created;
 */
static TreeNode *tree_node_insert(TreeNode *node, T v, TreeNode *left,
		TreeNode *right) {
	if (!node->twins) { //Single node -> Twins
		node->twins = 1;
		if (v < node->v) {
			node->v2 = node->v;
			node->v = v;
			node->left = left;
			node->center = right;
		} else {
			node->v2 = v;
			node->center = left;
			node->right = right;
		}
		return NULL;
	} else { //twins, must have 3 child, split and escalate the middle one
		if (v < node->v) {
			node = tree_node_split(node, v, node->v, node->v2, left, right,
					node->center, node->right);
		} else if (v < node->v2) {
			node = tree_node_split(node, node->v, v, node->v2, node->left, left,
					right, node->right);
		} else {
			node = tree_node_split(node, node->v, node->v2, v, node->left,
					node->center, left, right);
		}
		return node;
	}
}

static void tree_node_check(TreeNode* node) {
	assert(node);
	assert(
			(node->left && node->right) || (node->left == NULL && node->right == NULL));
	if (node->left)
		assert(node->left->up == node);
	if (node->center)
		assert(node->center->up == node);
	if (node->right)
		assert(node->right->up == node);
}

/* NULL: v exists, no action */
static TreeNode *tree_search_leaf_add(TreeNode *node, T v) {
	tree_node_check(node);

	if (v == node->v || (node->twins && node->v2 == v))
		return NULL;

	if (node->left) { // has children, 2 or 3
		if (v < node->v)  //less than v
			return tree_search_leaf_add(node->left, v);
		if (node->twins && v < node->v2) //twins node
			return tree_search_leaf_add(node->center, v);
		else
			return tree_search_leaf_add(node->right, v);
	}
	return node;
}

/* TreeNode grow strategy:
 * 	1. Grow up from leaf!
 * 	2. Single -> Twins, so each twins node must have 3 children
 * 	3. Twins -> 3 Single, so each new parent must have 2 children
 * 	4. left and right must exist!
 * 	5. if twins, center must exist!
 */
TreeNode *tree_add(TreeNode *tree, T v) {

	if (tree == NULL)
		return tree_node_alloc(NULL, v, NULL, NULL);

	tree_node_check(tree);

	TreeNode *leaf = tree_search_leaf_add(tree, v);
	if (!leaf)  //already exits on tree
		return tree;

	TreeNode *node = tree_node_insert(leaf, v, NULL, NULL);
	return node ? node : tree;
}

void tree_test_number(int n, int random) {
	TreeNode* t;
	int i;
	T last = 0;
	T v;
	for (i = 1; i <= n; ++i) {
		v = random ? ((double) rand() * n) / RAND_MAX : i;
		printf("%d ", v);
		t = tree_add(t, v);
//		tree_walk(t, 0, tree_callback_print_v, 0);
//		printf("===================
");
	}
	printf("
");
	tree_walk(t, 0, tree_callback_verify, &last);
	tree_walk(t, 0, tree_callback_print_h, NULL);
	printf("
");
	tree_walk(t, 0, tree_callback_print_v, 0);
}

void tree_test_chars() {
	TreeNode *t = NULL;
	int i;
	T last = 0;
	char c;
// http://blog.csdn.net/yang_yulei/article/details/26066409
	char* str = "EARCHXMPL";
	for (i = 0; i < strlen(str); ++i) {
		c = str[i]; //random();
		printf("%c ", c);
		t = tree_add(t, c);
	}
	printf("
");

	tree_walk(t, 0, tree_callback_verify, &last);
	tree_walk(t, 0, tree_callback_print_hc, NULL);
	printf("
");
	tree_walk(t, 0, tree_callback_print_vc, NULL);
}

int main(int argc, char **argv) {
	tree_test_chars();
	tree_test_number(20, 1);
	return EXIT_SUCCESS;
}