MENU

跳跃表

一:背景

跳跃表(英文名:Skip List),于1990年William Pugh发明,是一个可以在有序元素中实现快速查询的数据结构,其插入,查找,删除操作的平均效率都为$O(logn)$。

跳跃表的整体性能可以和二叉查找树(AVL树,红黑树等)相媲美,其在RedisLevelDB中都有广泛的应用。

阅读全文

AVL树和红黑树的对比

前面已经分别介绍了两种平衡二叉树:AVL树红黑树,先让我们来简单回顾下。

AVL树,规定其任一结点下左右子树高度不超过1。

红黑树,规定其必须满足四个性质:

  1. 每个结点要么是红的,要么是黑的;
  2. 根结点是黑色的;
  3. 如果一个结点是红色的,则它的两个孩子都是黑色的;
  4. 对于任意一个结点,其到叶子结点的每条路径上都包含相同数目的黑色结点。

阅读全文

红黑树

一:背景

红黑树(英语:Red–Black Tree,简称RB-Tree)是一种平衡的二叉查找树,用途广泛。例如:

  • Java中的:java.util.TreeMap,java.util.TreeSet;
  • C++ STL中的:map,multimap,multiset。

它是在1972年由Rudolf Bayer发明的,他称之为"对称二叉B树",它现代的名字(即"红黑树")是Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。

红黑树的实现比较复杂,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的,它可以在$O(logn)$时间内做查找,插入和删除操作。

阅读全文

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)$的时间。下面采用动态规划来对数串进行预处理,也就是填充二维数组。

阅读全文