先转摘一段网上关于旋转卡壳算法的历史
1978年， M.I. Shamos's Ph.D. 的论文"Computational Geometry"标志着计算机科学的这一领域的诞生。 当时他发表成果的是一个寻找凸多边形直径的一个非常简单的算法， 即根据多边形的一对点距离的最大值来确定。 后来直径演化为由一对对踵点对来确定。 Shamos提出了一个简单的 O(n) 时间的算法来确定一个凸 ...
凸包用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有的点。
如下图(图片来看网络)：
算法的主要方法是先排序，然后扫描。
代码如下
/*
* Name: getdist ...B+树可以看作是B树的一种变形，通常用于数据库和操作系统的文件系统中。
B+树的定义基本与B树相同。区别如下。
插入删除操作与B树有些区别 ...
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树的定义：
红黑树是比较复杂的一种平衡树结构。容易看得云里雾里，让人望而却步。或是强记下来，终究不能理解而很快忘记了。
感觉开始最让人困惑的就是平白无故就得出了一堆性质，然后根据性质很不明所以地推导各种奇怪的操作步骤。这样几乎不可能理解其中的含义。
这是一个充斥着迷茫和痛苦的过程，我花了20多天的所有空余时间，画了二十几页的草稿。
红黑树来源于2-3-4树，是2-3-4树的一种表现形式。当节点为红色时，即表示此节点和父节点连结为2-3-4树中的一个节点，如下图。
在我的学习中，分析过程大约是：先理解2-3-4树的增加删除 ...
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树是根据它的发明者G.M.Adelson-Velsky和E.M.Landis命名的。 它是最先发明的自平衡二叉查找杩，也被称为高度平衡树。AVL树中任何节点的两个子树的高度最大差别为1。 AVL树的查找，插入，和删除在平均和最坏情况下都是O(log(n))。
AVL树的一般定义：
typedef struct avl_tree_s* avl_tree_pt;
typedef struct ...哈夫曼树是最优二叉树。定义：给定n个权值作为n个叶子节点，构造一棵二叉树，若树的带树路径长度最小，则这棵树被称为哈夫曼树。如下图。
哈夫曼树涉及的几个概念
路径和路径长度：在一棵树中，从一个结点往下可以到达孩子或孙子结点之间的通路，称为路径。通路中结点的数目称为路径长度。如15的路径长度是1；5,6,7,8的路径长度是3。
结点的权及带权路径长度: 若将树中结点赋给一个有着某种含义的数值 ...
斐波那契堆编程实现难度较大并且效率没有理论的快(由于它的存储结构和四个指针)。pairing堆可以弥补斐波那契堆的缺点，编程比较简单且时间复杂度跟斐波那契堆相同。
pairing堆是一棵多路树，类似于左倾堆和斜堆，与二项堆和斐波那契堆不同。它的基本操作是两个多路树的连接，所以取名叫pairing堆。
关于pairing堆的完整中文资料比较少，但国外还是挺容易找到的。以下的实现参考cise.ufl.edu一些公开课资料的讲解。
pairing堆的数据结构一般如下：
typedef struct pairing_heap_s *pairing_heap_pt ...斐波那契堆同二项堆一样,也是一种可合并堆。斐波那契堆的优势是：不涉及删除元素的操作仅需要O（1）的平摊运行时间。和二项堆一样，斐波那契堆由一组树构成。这种堆松散地基于二项堆，说松散是因为：如果不对斐波那契堆做任何DECREASE-KEY 或 DELETE 操作，则堆中每棵树就和二项树一样；但是如果执行这两种操作，在一些状态下必须要破坏二项树的特征，比如DECREASE-KEY或DELETE 后，有的树高为k ...