二叉树

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：中序遍历 ...