MENU

AVL树

一:背景

AVL树是一棵平衡的二叉查找树,于1962年,G. M. Adelson-Velsky和E. M. Landis在他们的论文《An algorithm for the organization of information》中发表。

所谓的平衡之意,就是树中任意一个结点下左右两个子树的高度差不超过1。(本文对于树的高度约定为:空结点高度是0,叶子结点高度是1。)

那AVL树和普通的二叉查找树有何区别呢?如图,如果我们插入的是一组有序上升或下降的数据,则一棵普通的二叉查找树必然会退化成一个单链表,其查找效率就降为$O(n)$。而AVL树因其平衡的限制,可以始终保持$O(logn)$的时间复杂度。

阅读全文

二叉查找树

一:背景

二叉查找树(Binary Search Tree,简称BST),也称二叉搜索树、有序二叉树、排序二叉树,是指一棵空树或者具有下列性质的二叉树:

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;

  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;

  3. 任意节点的左、右子树也分别为二叉查找树;

  4. 没有键值相等的节点。

阅读全文

Aho-Corasick算法

一:背景

Aho–Corasick算法(也称AC算法,AC自动机)是由Alfred V. Aho和Margaret J.Corasick 发明的字符串搜索算法,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。

一个典型应用就是:给出$k$个单词,再给出一段文章(长度是$n$),让你找出有多少个单词在文章里出现过。

与其它模式串匹配不同,KMP算法是单模式串的匹配算法,AC算法是多模式串的匹配算法,匹配所需的时间复杂度是$O(n)$。

AC算法建立在字典树基础上,如果您还不了解字典树,可以参考字典树入门

阅读全文

Sparse Table算法

一:背景

Sparse Table算法(以下简称ST算法)是用来解决以下问题的,

区间最值查询(Range Minimum/Maximum Query,简称RMQ问题):对于长度为n的数组array[],回答若干询问RMQ(array, i, j)$(0 ≤ i, j < n)$,返回数组array[]中下标在i,j之间的最小或最大值。

找一个区间最值,最简单的直接比较,复杂度是$O(n)$,所以如果查找次数很少,用ST算法没有意义。ST算法的应用场景就是要对一个数串查询多次的情况。

算法的基本思想就是对串中所有可能的区间组合的最值用二维数组保存,也就是所谓的预处理,查询时直接通过数组下标获取,$O(1)$的时间。下面采用动态规划来对数串进行预处理,也就是填充二维数组。

阅读全文

Sunday算法

一:背景

Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其效率在匹配随机的字符串时比其他匹配算法还要更快。Sunday算法的实现可比KMP,BM的实现容易太多。

阅读全文

BFS和DFS

我们首次接触BFS和DFS时,应该是在数据结构课上讲的“图的遍历”。它们的实现都很简单,这里我就不哆嗦去贴代码了。我觉得读者更想知道的是,这两者“遍历”的序列到底有何差别?

那本篇文章就单纯来讲讲它们的区别和各自的应用,不会涉及任何代码。

广度优先搜索算法(Breadth-First-Search,缩写为BFS),是一种利用队列实现的搜索算法。简单来说,其搜索过程和“湖面丢进一块石头激起层层涟漪”类似。

深度优先搜索算法(Depth-First-Search,缩写为DFS),是一种利用递归实现的搜索算法。简单来说,其搜索过程和“不撞南墙不回头”类似。

BFS的重点在于队列,而DFS的重点在于递归。这是它们的本质区别。

举个典型例子,如下图,灰色代表墙壁,绿色代表起点,红色代表终点,规定每次只能走一步,且只能往下或右走。求一条绿色到红色的最短路径。

阅读全文