李哥发布的文章

字符串匹配1：BF算法和RK算法

字符串匹配可分为单模式串匹配和多模式串匹配，单模式串匹配就是一个串和一个子串匹配，多模式串匹配可以一个串同时查找多个字串。

堆非常适合用来实现优先队列。优先队列每次取出都是优先级最高的元素，十分契合堆的性质。

堆分为大顶堆和小顶堆，堆是一颗完全二叉树。

规定如下：

第一点，堆必须是一个完全二叉树。完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。

第二点，堆中的每个节点的值必须大于等于（或者小于等于）其子树中每个节点的值。实际上，我们还可以换一种说法，堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫做“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做“小顶堆”。

二分查找的思想很常见也很简单，使用分治思想从左边（中间元素大于目标元素）或者从右边（中间元素小于目标元素）查找元素。在一个顺序表中查找等于X的元素的index，从中间元素开始匹配，如果等于则直接返回，如果小于目标元素，则向左边区间查找，如果大于目标元素则向右边查找。

平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。从这个定义来看，上一节我们讲的完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。

平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。

所以，平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。

常见的平衡二叉查找树有：AVL树、Splay Tree（伸展树）、Treap（树堆）和红黑树等等。使用最广泛的是红黑树，从linux内核到jdk的HashMap等等都被广泛使用到。