我是小曼巴

无权最短路径 概念图9-10表示一个无权图G。使用某个顶点s作为输入参数，我们想要找出从s到所有其它顶点的最短路径。对于无权图，最短路径即路径的边数。记录实际的路径，只需要对...

我是小曼巴

数据处理中最基础的问题之一是从文本T中找到一段模式P所在的位置。而后缀数组与后缀树就是解决这类问题的数据结构（两者基本等价，就是用空间换时间）。 后缀数组的定义 关于一段文本...

我是小曼巴

伸展树性质 伸展树（splay tree），它保证从空树开始连续M次对树的操作最多花费O(MlogN)时间。虽然这种保证并不排除任意单次操作花费O(N)时间的可能，但是保证了...

我是小曼巴

定义 AVL树（Adelson-Velskii 和 Landis）是一种带有平衡条件的二叉查找树。它的平衡条件是：一颗AVL树的每个节点的左子树和右子树的高度最多差1。如下图...

我是小曼巴

算法描述 像归并排序一样，快速排序也是一种分治的递归算法。经典快速排序，输入存放在数组里，且算法不产生额外的数组。将数组S排序的基本算法由下列简单的四步组成： 如果数组S中的...

我是小曼巴

定义 它是设计用来处理数量很大的输入数据。当输入数据无法全部读入主存，可使用外部排序对数据进行排序。对于外部排序而言，排序的时间主要花费在对数据的读取和写入（例如对磁盘的读写...