数据结构与算法

1. 前言 红黑树是一种自平衡二叉查找树（Self-balancing binary search tree）。 如前文所述，根据红黑树的定义去理解其设计思想是非常困难的，但借助 B 树我们却可以更好地理解它，因为红黑树本就是由4阶B树推导而来。 全文较长，但为了完整的阅读体验，所以没有拆分为多篇文章，读者可以根据导图挑选阅读感兴趣的章节。 代码仓库：https://github.com/patricklaux/perfect-code 2. 由来 了解红黑树的由来和变体，有助于更好地理解。 (1) 1972 年，Rudolf Bayer 提出了 “symmetric binary B-tree”，这是B 树的 4 阶情形，也就是 2-3-4树（或称为 2-4 树）1。 (2) 1978 年，Leonidas J. Guibas 和 Robert Sedgewick 从 “symmetric binary B-tree” 推导出红黑树2。 (3) 1993 年，Arne Andersson 引入 “right leaning tree(右倾树)” 的概念来简化插入和删除操作3。 (4) 1999 年，Chris Okasaki 展示了如何使插入操作成为纯函数，只需处理 4 种失衡类型和 1 种默认平衡类型4。 (5) 2001 年，Cormen 等人将原算法的 8 个失衡类型减少为 6 个失衡类型5。 (6) 2008 年，Sedgewick 根据 Andersson 的思想，提出了 “Left leaning red black tree(左倾红黑树)”，这是 2-3 树的等价转换6。 ...

1. 前言 红黑树的实现并不困难，但仅根据其定义去理解背后的设计思想却是相当不容易的。 相比较而言，B树是非常直观且容易理解的，了解B树之后，再去看红黑树，就会发现红黑树其实是4阶B树的一种等价实现，红黑树的查找、插入、删除、着色和旋转都可以在4阶B树中一一找到对应关系。 另外，B树及其变体也广泛地运用于数据库系统，譬如 MySQL、MongoDB……等。 这篇文章中，我会先介绍 B树的由来，接着介绍其定义和概念，然后通过图例和流程图来说明相关操作，最后会给出其代码实现。 代码仓库：https://github.com/patricklaux/perfect-code 2. 由来 B 树是由 Rudolf Bayer 和 Edward McCreight 在波音实验室工作期间提出的，论文 “Organization and maintenance of large ordered indices1” 发表于1972年。 B 树是多叉查找树的一种实现，而多叉查找树是二叉查找树的推广。 与内存相比，磁盘具有持久性、大容量和单位存储价格便宜等优点。 但磁盘相对于内存而言是非常缓慢的，二叉树这种内存数据结构并不能很好地应用于磁盘存储。 磁盘读写以页为单位，分页大小为 4KB 时，读取 1B 数据与 4KB 数据均需一次磁盘I/O，耗时几乎相等。 另外，磁盘顺序读写比随机读写的性能要好得多，当读写连续的数据页时，通常都会有不错的性能表现。 因此，根据磁盘数据读写的这些特点，为减少磁盘I/O，很自然的一个想法就是将多个数据项合并存入到一个节点，节点大小恰好是页大小的整数倍。 如下图所示，多个二叉树节点合并成一个节点，这样二叉查找树就变成了多叉查找树 (M-ary search tree)。 图2.1：节点合并(图片来源于参考资料[2]) 一棵完全二叉树 (complete binary tree) 的层数大约为 \( log_2n \)，一棵完全多叉树 (complete M-ary tree) 的层数大约为 \( log_mn \)，n 为数据记录数。 这意味着，如果有 100万条数据记录，当以二叉树的形式存储到磁盘，搜索一条数据记录约需 20次磁盘I/O： \( log_21000000≈20 \)； 如图2.1 所示，通过将 7个节点合并成一个数据页存储到磁盘，变成一棵 8叉搜索树，那么搜索一条数据记录仅需约 7次磁盘I/O： ...

时隔多年又重新实现了一遍 AVL树，并且进行了深度优化，所以有些心得。 首先，我会介绍6种失衡类型和4种旋转； 然后，重点描述插入和删除的优化实现，并将给出严谨的分析和证明，解释为什么可以这么优化； 最后，我会用 AVL 树与 Java 的 TreeMap (红黑树)进行性能对比，以验证优化结果。 代码仓库：https://github.com/patricklaux/perfect-code 1. 简介 AVL 树是一种自平衡二叉查找树（Self-balancing binary search tree），得名于其两位作者的首字母1： Georgy Adelson-Velsky 和 Evgenii Landis。 相比于二叉查找树最坏情况下时间复杂度为 \( O(n) \)，AVL树查找、插入和删除的平均时间复杂度和最坏时间复杂度均为 \( O(log_2n) \)，其中 n 为树的节点数。 2. 高度与平衡因子 AVL树的平衡性质：其任意节点的左子树和右子树的高度差的绝对值小于等于1。 2.1. AVL节点 private class AvlNode<K, V> { K key; // 键 V val; // 值 byte height; // 高度 AvlNode<K, V> left; // 左孩子 AvlNode<K, V> right; //右孩子 } 2.2. 获取高度 // 空树的高度定义为 -1。 private byte height(AvlNode<K, V> node) { return (node == null) ? -1 : node.height; } 2.3. 更新高度 // 取左右子树的高度的大者再加1，即为父节点的高度 private void updateHeight(AvlNode<K, V> parent) { parent.height = (byte) (Math.max(height(parent.left), height(parent.right)) + 1); } 2.4. 平衡因子 二叉查找树的平衡因子 BF (Balance Factor) 的定义为两棵子树的高度之差。 ...

1. 概述 IDDFS (Iterative deepening depth-first search)：迭代加深搜索，是一种状态空间/图的搜索策略。 其空间复杂度仅为 \( O(d) \)，相比用队列实现层序遍历所需的 \( O(b^d) \) 空间复杂度，极大地节约了空间开销，b 为分支因子，d 为深度。 从三个维度来分析，空间开销、时间性能和求解路径的代价，IDDFS 都接近最优，是一个非常优秀的算法。 本文主要介绍用 IDDFS 算法实现二叉树的层序遍历，如对其它方面的搜索运用感兴趣，可阅读参考资料1。 代码仓库：https://github.com/patricklaux/perfect-code 2. 使用队列实现层序遍历 层序遍历：即为按层顺序访问，所有深度为 d 的节点在深度为 d+1 的节点之前访问——（d, b, f, a, c, e, g）。 使用队列实现层序遍历并不复杂，代码如下： public void levelOrderTraversal(List<Tuple2<K, V>> kvs) { if (root == null) { return; } ArrayDeque<Node<K, V>> queue = new ArrayDeque<>(size.get() / 2); queue.push(root); while (!queue.isEmpty()) { Node<K, V> p = queue.poll(); kvs.add(Tuples.of(p.key, p.val)); if (p.left != null) { queue.offer(p.left); } if (p.right != null) { queue.offer(p.right); } } } 常见的算法书在介绍层序遍历时都采用队列来实现，这种算法被称为标准 BFS。 ...

1. 概述 前一篇文章介绍了深度优先遍历的递归实现和迭代实现，这两种方式的时间复杂度都是 \( O(n) \)，空间复杂度都是 \( O(h) \)，本文将要介绍的 Morris 遍历的时间复杂度依然为 \( O(n) \)，但空间复杂度仅为 \( O(1) \)，其中 n 为节点数，h 为树的高度。 算法来历 1968年，《计算机程序设计艺术》的作者 Knuth 提出了一个问题：设计一个无需堆栈和额外标志域的非递归的中序遍历算法，且当遍历结束时树结构不变。此后，诞生了许多解决方案，而Morris 遍历是其中最优雅的一种（见参考资料1）1。 此算法由 Joseph M. MORRIS 在1979年的论文 “Traversing Binary Trees Simply and Cheaply2” 中首次提出。顺便再说一句，这个 MORRIS 正是大名鼎鼎的 KMP 算法的作者之一。 代码仓库：https://github.com/patricklaux/perfect-code 2. 算法解析 线索二叉树 如果了解线索二叉树的话，肯定对前驱和后继非常熟悉。 通过在二叉树节点增加前驱和后继指针，可以非常方便地进行向前查找、向后查找和遍历等线性化操作，相当于是二叉树和链表的结合。这其中指向前驱和后继的指针称之为线索，而包含线索的二叉树则称之为线索二叉树(Threaded Binary Tree)3。 譬如 Java 的 HashMap 中的 红黑树节点，就增加了 prev 和 next 指针，其节点结构类似如下： class TreeNode<K,V> { TreeNode<K,V> parent; // 父节点 TreeNode<K,V> left; // 左孩子 TreeNode<K,V> right; // 右孩子 TreeNode<K,V> prev; // 前驱 TreeNode<K,V> next; // 后继 boolean red; // 颜色 } 这种方式需要额外内存来保存前驱和后继指针，那么是不是有一些其它方式来避免这个问题呢？ ...

1. 概述 图1：二叉树遍历 遍历二叉树，即按照某条搜索路径巡访树中的每个结点，使得每个节点均被访问一次，而且仅被访问一次1。 深度优先遍历，常见的有递归方式和用栈实现的迭代方式， Morris 遍历虽然空间复杂度很好，但因需在遍历期间改变树结构而不常用。 广度优先遍历，常见的是用队列实现的迭代方式，但需耗费大量内存，而 IDDFS 算法则更节省内存空间。 本文将主要讲述深度优先遍历的递归和迭代的实现方式，其它见后续文章。 代码仓库：https://github.com/patricklaux/perfect-code 2. 递归 先序遍历、中序遍历和后序遍历的过程完全相同，都是从根到左子树再到右子树，差别仅在于何时访问值。 看后面的代码实现，会发现三段递归程序几乎完全相同，仅仅是调整了访问值的次序。 2.1. 先序遍历 先序遍历 (pre-order traversal)：根，左，右 图2：先序遍历 代码实现 private void preorderTraversalR(List<Tuple2<K, V>> kvs, Node<K, V> p) { // visit，添加到结果集 kvs.add(Tuples.of(p.key, p.val)); if (p.left != null) { preorderTraversalR(kvs, p.left); } if (p.right != null) { preorderTraversalR(kvs, p.right); } } 2.2. 中序遍历 中序遍历(in-order traversal)：左，根，右 中序遍历正好是按键的大小排序。 图3：中序遍历 ...

前文实现了 Patricia Trie，但用的是字符比较，而原论文则采用的是二进制位比较。 然后，我们心里可能会有疑问：二进制位比较是如何推广到字符比较的呢？二进制位比较相比于字符比较，又有哪些优点或缺点呢？ 相关代码：https://github.com/patricklaux/perfect-code 1. 基数 让我们先从基数说起吧。 1.1. 基数(radix) 基数(radix)，在定位数系(positional numeral system) 中表示不重复编码(digit) 的数量。 譬如在10进制中，有 {0, 1, 2, … ,8, 9} 共 10 个编码，那么基数就是 10； 譬如在16进制中，有 {0, 1, 2, … ,e, f} 共 16 个编码，那么基数就是 16； ………… 如果我们用 EASCII 字符编码来作为集合，那么其基数就是 256； 如果我们用 UTF-16 字符编码来作为集合，那么其基数就是 65536； ………… 如果我们用小写英文字母 {a, b, c, … , y, z} 来作为集合，那么其基数就是26。 也就是说，我们可以根据需要定义一套编码集，而基数就是这套编码集的元素数量。 注：基数(radix) 也可以看作是集合论中的基数(cardinal)，而编码集是有限良序集。 1.2. 基数树(radix tree) 基数概念推广到树中，那么这个基数就是 R 的大小。 我们在前两篇文章的节点定义就有一个 R，用来指定数组容量。类似于如下定义： class RadixNode{ // 值 V val; // 子节点数组 RadixNode<V>[] table; // R为数组容量 public RadixNode(int R) { this.table = new RadixNode[R]; } } 这棵树会有 R 个分支，又因为编码集是有限良序集，所以可将数组索引映射为唯一编码。 ...

这篇文章我将介绍 StandardTrie 的简单变体： PatriciaTrie1。 PatriciaTrie 或 PatriciaTree， 在一些论文中又被称为 CompactTrie（紧凑 trie）或 CompressedTrie（压缩 trie）。 相关代码：https://github.com/patricklaux/perfect-code 1. 导引 PatriciaTrie 的显著优化是合并单路分支：如果一个非根无值节点有且仅有一个子节点，则将其子节点与该节点合并。 文字描述稍有点抽象，还是看图： 节点合并 图1：节点合并 节点分裂 如果需要添加键 “da”，该如何来处理哪？我们需要将 “dad” 分裂成两个节点，效果见下图： 图2：节点分裂 相信，这两张图已足以说明一切😀 同时，我们也可以看到合并后节点数变少，因此减少了可能的内存消耗。 2. 代码实现 依照惯例，还是写代码来实现它。 2.1. 节点定义 package com.igeeksky.perfect.nlp.trie; private static class PatriciaNode<V> { // key 的子串 String subKey; // 值（支持泛型，可以是非字符串） V val; // 子节点 PatriciaNode<V>[] table; public PatriciaNode(int R) { this.table = new PatriciaNode[R]; } public PatriciaNode(int R, String subKey) { this.subKey = subKey; this.table = new PatriciaNode[R]; } public PatriciaNode(String subKey, V value) { this.subKey = subKey; this.val = value; } public PatriciaNode(int R, String subKey, V value) { this.subKey = subKey; this.val = value; this.table = new PatriciaNode[R]; } } 对比前文的 StandardNode，多了一个 String 类型的 subKey 字段，该字段用于存储节点合并之后的字符串，其它无变化。 ...

这篇文章将介绍最简单的 Trie 结构，即 StandardTrie，常被称为 标准 Trie，或朴素 Trie。 相关代码：https://github.com/patricklaux/perfect-code 1. 导引 假设有一个关键词集，其中有 6 个单词：bad, bade, bed, ca, cad, dad。 当输入 “b” 时，输出以 “b” 为前缀的所有单词； 输入一段文本，输出文本中存在这六个单词的哪几个，以及单词出现的起止位置…… 我们可以建立如下图所示的树形结构。 图1：字典树示例 每个字符一个节点，节点之间用边相连； 有特殊标记（有值）则代表一个完整的关键词。 2. 基本性质与操作 通过观察 ”图1：字典树示例“，我们可以发现一些性质和规律。 基本性质 根节点无字符； 兄弟节点的字符互异； 非根节点有且仅有一个字符； 非根节点有且仅有一个父节点； 根节点到其它节点的每条路径代表一个唯一的字符串。 根据以上性质，我们又可以得到一个有意思的推论：6. 兄弟节点都具有同一前缀； 键查找 从根节点沿着序列路径递归查找子节点，最后一个字符对应节点如果有特殊标记，则命中。 譬如要查找 bad，root → b → a → d，命中，返回 bad；譬如查找 cup，root → c → NULL，未命中，返回空。 前缀匹配 先找到前缀节点，然后遍历其子节点。 譬如查找以 b 为前缀的关键词：1. 先找到 b 对应的节点，root → b，找到 b 节点；2. 遍历 b 节点的所有子节点。 ...

Trie1 通常被称为字典树（或前缀树、单词搜索树），是一种用于存储和检索字符串的树型数据结构。 Trie 是英文单词 retrieval 的一部分，名称最早由 E. Fredkin2 提出，发音同 “try”。 图1：关键词推荐列表 典型的应用场景是搜索引擎的输入框：譬如当输入 “trie” 时，会列出以 “trie” 为前缀的关键词推荐列表。 此外，还有诸如拼写检查、词典分词、词频统计、数据压缩、倒排索引、字符串排序、关键词过滤……等等众多应用场景。 技术演化 由于字典树相关算法的应用广泛，所以演化出大量的数据结构和优化技术，其进化史就是一个脑洞大开的过程。 我之前画过一张复杂的演进图，现在看来并无必要，事实上只要了解关键脉络即可。删繁就简，最终留下了这张比较简单的图。 图2：技术演化 文章目录 字典树之旅01：开篇（本文） 字典树之旅02：Trie 的标准实现 字典树之旅03：Patricia Trie(一) 字典树之旅04：Patricia Trie(二) 未完待续…… 参考资料 https://en.wikipedia.org/wiki/Trie ↩︎ Fredkin, E. . “Trie memory.” Communications of the Acm 3(1960). ↩︎