B树一个Node可以有N个key, N+1个下级Node, 二叉树就是简化版,一个key两个下级node
2-3树和2-3-4树的区不大,2-3树在插入时先找到叶子节点(没有子节点),然后插入,过程中如果已经是3Node(2 key)就分裂,向上冒泡,一直可能冒泡到顶上。
2-3-4树则在向下找叶子节点时就做调整,把4Node(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 <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <assert.h>
#include <string.h>
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("\n");
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("\n");
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("===================\n");
}
printf("\n");
tree_walk(t, 0, tree_callback_verify, &last);
tree_walk(t, 0, tree_callback_print_h, NULL);
printf("\n");
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("\n");
tree_walk(t, 0, tree_callback_verify, &last);
tree_walk(t, 0, tree_callback_print_hc, NULL);
printf("\n");
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;
}
分享到:
相关推荐
基于C语言实现了红黑树及用户测试程序源码+详细注释+exe执行程序.zip数据结构课程作业-基于C语言实现了红黑树及用户测试程序源码+详细注释+exe执行程序.zip数据结构课程作业-基于C语言实现了红黑树及用户测试程序...
1. 采用类C语言定义相关的数据类型 3 2. 各模块的伪码算法 7 3. 函数的调用关系图 13 4. 调试分析 13 5. 测试结果 14 6. 源程序(带注释) 14 总 结 20 参考文献 20 附件Ⅰ 部分源程序代码 21 摘 要 哈夫曼编译码...
基于Python实现蒙特卡洛树搜索以及极大极小+α-β剪枝算法实现五子棋AI源码.zip 基于Python实现蒙特卡洛树搜索以及极大极小+α-β剪枝算法实现五子棋AI源码.zip 基于Python实现蒙特卡洛树搜索以及极大极小+α-β剪枝...
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 表达式树4.3 查找树ADT——二叉查找树4.3.1 MakeEmpty4.3.2 Find4.3.3 FindMin和FindMax4.3.4 Insert4.3.5 Delete4.3.6 平均情形分析...
Age sex region income married children car mortgage pep 1 2 1 1 2 1 ...3 2 1 2 1 1 1 2 2 1 1 1 2 1 1 1 2 1 1 1 3 2 2 2 1 2 1 3 1 2 2 1 2 2 2 1 3 2 3 3 1 1 1 2 1 3 2 2 3 1 2 1 1 2 3 1 3 3 1 1 2 2 1 3 2 1 ...
Entropy = 系统的凌乱程度,使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。 决策树是一种树形结构,其中每个内部节点表示一个属性上的测试,每个分支代表一个测试输出,每个叶节点...
设计一个系统实现对学生成绩的管理。要求系统应具有以下基本功能: (1)学生注册登记; (2)增加、删除某一班级的学生; (3)成绩录入:输入学生的考试成绩; 要求采用二叉排序树存放学生成绩,一门课程对应一...
3. 实现链表的增、删功能; 4. 遍历链表,将链表的前两个节点中权重相加,生成新节点,然后将新节点插入到有序链表中; 5. 直到链表中只剩一个节点时,将此节点赋给哈夫曼树头; 6. 利用创建的哈夫曼树得到编码; 用...
26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36哈希与映射的概述 37B树有什么用 38B树的概念 39图_邻接矩阵 40图_邻接表 41图_DFS 42图_BFS
算法:C语言实现 (第1-4部分)基础知识、数据结构、排序及搜索(原书第3版) 本书是Sedgewick彻底修订和重写的C算法系列的第一本。全书分为四部分,共16章。第一部分“基础知识”(第1—2章)介绍基本算法分析原理。...
2.掌握如何实现决策树算法,并用其完成预测。 二、实验原理 决策树,信息熵,信息增益。 决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目...
C4.5 算法是用于生成决策树的一种经典算法,是 ID3 算法的一种延伸和优化。 C4.5 算法对 ID3 算法主要做了一下几点改进: 1.通过信息增益率选择分裂属性,克服了 ID3 算法中通过信息增益倾向于选择拥有多个属性值...
实验1:实现红黑树的基本算法, 对n的取值分别为 12、24、36、48、60,随机生成n ...实验2:对上述生成的红黑树,找出树中的第n/3小的节点和第n/4小的节点,并删除这两个节点,统计算法运行所需时间 , 画出时间曲线。
书中详细讨论了栈、队列、链表以及查找结构、高级树结构等功能,对裴波那契堆、伸展树、红黑树、2-3树、2-3-4树、二项堆、最小-最大堆、双端堆等新的数据结构进行了有效分析。《数据结构》(C语言版)对一些特殊形式的...
(2)掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现方法。 (3)掌握散列存储结构的思想,能选择合适散列函数,实现不同冲突处理方法的散列表的查找、建立。 (4)能运用线性表的查找方法...
本系统是个学生成绩管理系统 ... 在出队的同时将学生成绩入树,调用创建2叉树,便进行中序遍历。 5.任意输入一个学生的学号,用一种查询方法查询该学生的成绩。 思想: 直接查找学生学号,找到就输出。
(3)当队列⾮空时,循环执⾏步骤(3.a-3.c); (3.a)出队列取得⼀个结点指针,访问该结点; (3.b)若该结点的左⼦树⾮空,则将该结点的左⼦树指针⼊队列; (3.c)若该结点的右⼦树⾮空,则将该结点的右⼦树指针...
2) 判断该文法是否为算符文法; 3) 对文法中的每个非终结符自动生成并打印输出: ① FIRSTVT集; ② LASTVT集; 4)判断该文法是否为算符优先文法, 如果是自动生成并打印输出其算符优先矩阵; 5) 模拟分析过程...
本书细腻讲解计算机算法的c语言实现。全书分为四部分,共16章。包括基本算法分析原理,基本数据结构、抽象数据结构、递归和树等数据结构知识,选择排序、插入排序、冒泡排序、希尔排序、快速排序方法、归并和归并...
数据结构完整实验报告 实验3:树和二叉树的应用-哈夫曼编码设计