B+树的C语言实现
Date 2016-12-18(星期日) 21:36 By Ming In 算法 Tags 算法,
B+树可以看作是B树的一种变形，通常用于数据库和操作系统的文件系统中。
B+树的定义基本与B树相同。区别如下。
- 非叶子结点的子树指针与关键字个数相同
- 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）
- 为所有叶子结点增加一个链指针
- 所有关键字都在叶子结点出现
插入删除操作与B树有些区别 ...
B树的C语言实现
Date 2016-12-11(星期日) 02:03 By Ming In 算法 Tags 算法,
B树是2-3-4树的延伸，或者说2-3-4树是B树的一种情况。
所以B树的基本操作与2-3-4树相同。2-3-4树其实还是挺重要的一种数据结构，理解2-3-4树更理解了B树和红黑树。前两篇文章作2-3-4树分析时画过图，B树便不再画了，画图其实挺累的。
B树的查询，插入，删除的时间复杂度都是O(lgn)
B树的定义：
- 每个节点最多有m个元素(m + 1个孩子)
- 每个非叶节点(除根节点)有最少m/2个元素 ...
红黑树的分析与C语言实现
Date 2016-11-10(星期四) 21:14 By Ming In 算法 Tags 算法,
前言
红黑树是比较复杂的一种平衡树结构。容易看得云里雾里，让人望而却步。或是强记下来，终究不能理解而很快忘记了。
感觉开始最让人困惑的就是平白无故就得出了一堆性质，然后根据性质很不明所以地推导各种奇怪的操作步骤。这样几乎不可能理解其中的含义。
这是一个充斥着迷茫和痛苦的过程，我花了20多天的所有空余时间，画了二十几页的草稿。
红黑树来源于2-3-4树，是2-3-4树的一种表现形式。当节点为红色时，即表示此节点和父节点连结为2-3-4树中的一个节点，如下图。
在我的学习中，分析过程大约是：先理解2-3-4树的增加删除 ...
2-3-4树的分析
Date 2016-10-25(星期二) 08:49 By Ming In 算法 Tags 算法,
2-3-4树在大部分资料中都简单带过，也很少会去实现。但是对于理解红黑树和B树来说，2-3-4树有非常重要的作用。
我被红黑树的算法折磨了几天，终于转到2-3-4树的学习，才搞明白了红黑树的来由。虽然一般2-3-4树不必实现，但是了解其原理还是很重要的。
2-3-4树是阶为4的B树，同时2-3-4树与红黑树等效。
2-3-4树的名称意味着树的每个节点带着2，3或4个孩子节点。
-
2节点有1个数据元素，有2个子节点
-
3节点有2个数据元素，有3个子节点
-
4节点有3个数据元素，有4个子节点
2-3-4树的特性 ...
AVL树的C语言实现
Date 2016-10-10(星期一) 20:55 By Ming In 算法 Tags 算法,
AVL树是根据它的发明者G.M.Adelson-Velsky和E.M.Landis命名的。 它是最先发明的自平衡二叉查找杩，也被称为高度平衡树。AVL树中任何节点的两个子树的高度最大差别为1。 AVL树的查找，插入，和删除在平均和最坏情况下都是O(log(n))。
AVL树的一般定义：
typedef struct avl_tree_s* avl_tree_pt;
typedef struct ...哈夫曼树的C语言实现
Date 2016-10-07(星期五) 22:10 By Ming In 算法 Tags 算法,
哈夫曼树是最优二叉树。定义：给定n个权值作为n个叶子节点，构造一棵二叉树，若树的带树路径长度最小，则这棵树被称为哈夫曼树。如下图。
哈夫曼树涉及的几个概念
路径和路径长度：在一棵树中，从一个结点往下可以到达孩子或孙子结点之间的通路，称为路径。通路中结点的数目称为路径长度。如15的路径长度是1；5,6,7,8的路径长度是3。
结点的权及带权路径长度: 若将树中结点赋给一个有着某种含义的数值 ...
pairing堆的C语言实现
Date 2016-10-07(星期五) 16:31 By Ming In 算法 Tags 算法,
斐波那契堆编程实现难度较大并且效率没有理论的快(由于它的存储结构和四个指针)。pairing堆可以弥补斐波那契堆的缺点，编程比较简单且时间复杂度跟斐波那契堆相同。
pairing堆是一棵多路树，类似于左倾堆和斜堆，与二项堆和斐波那契堆不同。它的基本操作是两个多路树的连接，所以取名叫pairing堆。
关于pairing堆的完整中文资料比较少，但国外还是挺容易找到的。以下的实现参考cise.ufl.edu一些公开课资料的讲解。
pairing堆的数据结构定义
pairing堆的数据结构一般如下：
typedef struct pairing_heap_s *pairing_heap_pt ...斐波那契堆的C语言实现
Date 2016-10-06(星期四) 01:01 By Ming In 算法 Tags 算法,
斐波那契堆同二项堆一样,也是一种可合并堆。斐波那契堆的优势是：不涉及删除元素的操作仅需要O（1）的平摊运行时间。和二项堆一样，斐波那契堆由一组树构成。这种堆松散地基于二项堆，说松散是因为：如果不对斐波那契堆做任何DECREASE-KEY 或 DELETE 操作，则堆中每棵树就和二项树一样；但是如果执行这两种操作，在一些状态下必须要破坏二项树的特征，比如DECREASE-KEY或DELETE 后，有的树高为k ...
二项堆的C语言实现
Date 2016-10-01(星期六) 16:41 By Ming In 算法 Tags 算法,
二项堆是一种比较复杂的堆结构，这种数据结构在"算法-c语言实现(第3版)"中有讲解，可惜这本书实在把二项堆说得云山雾罩。
二项堆是二项树的集合。下面先说明二项树再说明二项堆及其各种操作。
二项树
二项树是一种递归定义的树，它的定义如下：
- 二项树B0只有一个节点。
- 二项树Bk由两棵二项树B(K-1)组成，其中一棵树是另一棵树的最左孩子。
如下图所示：
上图的B0,B1,B2 ...
斜堆的C语言实现
Date 2016-09-25(星期日) 21:16 By Ming In 算法 Tags 算法,
斜堆(skew heap)是左倾堆的一个变种，与左倾堆一样，合并的时间复杂度也是O(lgn)。相对于左倾堆来说，斜堆没有零距离这个概念，而是在合并操作的时候，每次交换左右子树。
斜堆的定义
typedef struct skew_heap_s *skew_heap_pt;
typedef struct skew_heap_s {
skew_heap_pt ...