红黑树

红黑树是一棵二叉搜索树, 它在每个结点上增加了一个存储位来表示结点的颜色, 可以使 RED 或 BLACK. 红黑树中没有一条路径会比其他路径长出 2 倍, 所以是近似平衡的. 树中的每个结点包含 5 个属性: color, key, left, right 和 parent. »

二叉搜索树

二叉搜索树是以一棵二叉树来组织的, 其中每一个结点都是一个对象, 每个结点都包含属性 left right 和 p, 它们分别指向结点的 left child, right child 和 parent. 如果某个 child 结点不存在, 那么相应的属性就为 nil. 二叉搜索 »

散列表

散列表(hash table)是实现字典操作的一种有效的数据结构. 尽管在最坏情况下, 散列表中查找一个元素的时间与链表中查找的时间相同, 达到了 $\Theta(n)$. 然而在实际的应用中, 散列表的性能是极好的, 查找元素的平均时间是 $O(1)$. 直接寻址表 当关键字的 »

基本数据结构

在这一次的 post 中, 我们将要介绍一些简单的数据结构: 栈, 队列, 链表和树. 栈和队列 栈和队列都是动态集合, 在这两种数据结构上进行 DELETE 操作所移除的元素都是预先设定的. 它们是两种最常用的数据结构. 栈 在栈中, 被删除的元素是最近插入的元素. 它实现的是 »

中位数和顺序统计量

顺序统计量 在一个由 $n$ 个元素组成的集合中, 第 $i$ 个顺序统计量 (order statistic) 是该集合中第 $i$ 小的元素. 最小值是第 $1$ 个顺序统计量 $i=1$. 最大值是第 $n$ 个顺序统计量 $i=n$. 中位数是所属集合的中点元素. 当 $ »

线性时间排序

我们把在排序的最终结果中, 各元素的次序依赖于它们的比较的排序算法称为比较排序. 而我们在这里介绍的排序将不依赖于元素之间的比较. 第一次听到这种说法感觉非常的神奇和震惊, 而在以前的认识中, 排序都是基于比较的. 不经过比较怎么排序, 而这一章线性时间排序就改变了我过去对排序的 »

快速排序

快速排序使用分治法策略把一个数组分成两个子数组, 并对两个子数组递归排序. 快速排序的分治过程有三步: 分解 数组 A[p..r] 被分解为两个可能为空的子数组 A[p..q-1] 和 A[q+1..r], 使 A[p..q-1] 中的所有元素都小于或等于 A[q], A[q+1 »

堆排序

一种时间复杂度为 Ο(nlgn) 的排序算法. 堆 二叉堆 是一个数组, 它可以被看成一个近似的完全二叉树, 除了最底层外, 该树是完全充满的, 而且是从左向右填充. int parent(int i) { return i / 2; } int left(int i »

分治策略

在计算机科学中, 分治法是基于多项分支递归的一种很重要的算法范式. 字面上的解释是"分而治之", 就是把一个复杂的问题分成两个或更多的相同或相似的子问题, 知道最后子问题可以简单的直接求解, 原问题的解就是子问题的解的合并. 分治法的步骤 分解: 将问题划分为一些子问题, »