2020-04-06

geek

《数据结构与算法之美》-2-树（Tree）

学习数据结构和算法，要学习它的由来、特性、适用的场景以及它能解决的问题。¹

每个元素我们叫作“节点”；用来连线相邻节点之间的关系，我们叫作“父子关系”。

A节点就是B节点的父节点，B节点是A节点的子节点。B、C、D这三个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。我们把没有父节点的节点叫作根节点，也就是图中的节点E。我们把没有子节点的节点叫作叶子节点或者叶节点，比如图中的G、H、I、J、K、L都是叶子节点。

高度（Height）
深度（Depth）
层（Level）

二叉树（Binary Tree）

两个子节点，分别是 左子节点 和 右子节点。

概念解释

节点：树中的每个元素称为节点
父子关系：相邻两节点的连线，称为父子关系
根节点：没有父节点的节点
叶子节点：没有子节点的节点
父节点：指向子节点的节点
子节点：被父节点指向的节点
兄弟节点：具有相同父节点的多个节点称为兄弟节点关系
节点的高度：节点到叶子节点的最长路径所包含的边数
节点的深度：根节点到节点的路径所包含的边数
节点的层数：节点的深度+1（根节点的层数是1）
树的高度：等于根节点的高度

编号2 的二叉树中，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作 满二叉树。

编号3的二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作 完全二叉树。

如何表示（或者存储）一棵二叉树？

基于指针或者引用的 链式存储法

基于数组的 顺序存储法
- 根节点存储在下标 i = 1 的位置
- 那左子节点存储在下标 2 * i 的位置
- 右子节点存储在 2 * i + 1 的位置。

堆其实就是一种完全二叉树，最常用的存储方式就是数组

二叉树的遍历

深度优先
- 前序遍历
- 中序遍历
- 后序遍历

递推公式

前序遍历的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)

中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)

后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

代码

void preOrder(Node* root) {
  if (root == null) return;
  print root // 此处为伪代码，表示打印root节点
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  print root // 此处为伪代码，表示打印root节点
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  print root // 此处为伪代码，表示打印root节点
}

二叉树遍历的时间复杂度是 \(O(n)\)。

树是非线性表数据结构。关于树，有几个比较常用的概念你需要掌握，那就是：根节点、叶子节点、父节点、子节点、兄弟节点，还有节点的高度、深度、层数，以及树的高度。

我们平时最常用的树就是二叉树。二叉树的每个节点最多有两个子节点，分别是左子节点和右子节点。二叉树中，有两种比较特殊的树，分别是满二叉树和完全二叉树。满二叉树又是完全二叉树的一种特殊情况。

二叉树既可以用链式存储，也可以用数组顺序存储。数组顺序存储的方式比较适合完全二叉树，其他类型的二叉树用数组存储会比较浪费存储空间。除此之外，二叉树里非常重要的操作就是前、中、后序遍历操作，遍历的时间复杂度是 \(O(n)\)，你需要理解并能用递归代码来实现。

二叉查找树 / 二叉搜索树（Binary Search Tree）

快速

查找
插入
删除

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

查找操作

public class BinarySearchTree {
  private Node tree;

  public Node find(int data) {
    Node p = tree;
    while (p != null) {
      if (data < p.data) p = p.left;
      else if (data > p.data) p = p.right;
      else return p;
    }
    return null;
  }

  public static class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
      this.data = data;
    }
  }
}

插入操作

public void insert(int data) {
  if (tree == null) {
    tree = new Node(data);
    return;
  }

  Node p = tree;
  while (p != null) {
    if (data > p.data) {
      if (p.right == null) {
        p.right = new Node(data);
        return;
      }
      p = p.right;
    } else { // data < p.data
      if (p.left == null) {
        p.left = new Node(data);
        return;
      }
      p = p.left;
    }
  }
}

删除操作

public void delete(int data) {
  Node p = tree; // p指向要删除的节点，初始化指向根节点
  Node pp = null; // pp记录的是p的父节点
  while (p != null && p.data != data) {
    pp = p;
    if (data > p.data) p = p.right;
    else p = p.left;
  }
  if (p == null) return; // 没有找到

  // 要删除的节点有两个子节点
  if (p.left != null && p.right != null) { // 查找右子树中最小节点
    Node minP = p.right;
    Node minPP = p; // minPP表示minP的父节点
    while (minP.left != null) {
      minPP = minP;
      minP = minP.left;
    }
    p.data = minP.data; // 将minP的数据替换到p中
    p = minP; // 下面就变成了删除minP了
    pp = minPP;
  }

  // 删除节点是叶子节点或者仅有一个子节点
  Node child; // p的子节点
  if (p.left != null) child = p.left;
  else if (p.right != null) child = p.right;
  else child = null;

  if (pp == null) tree = child; // 删除的是根节点
  else if (pp.left == p) pp.left = child;
  else pp.right = child;
}

还有个非常简单、取巧的方法，就是单纯将要删除的节点标记为“已删除”。

快速地查找 最大节点 和 最小节点、前驱节点 和 后继节点。

中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 \(O(n)\)，非常高效。因此，二叉查找树也叫作 二叉排序树。

支持重复数据的二叉查找树

对象中的其他字段叫作卫星数据。
对象的某个字段作为键值（key）来构建二叉查找树。
1. 链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。
2. 插入的数据放到这个节点的右子树。

时间复杂度分析

完全二叉树的高度小于等于 \(\log_{2} n\)

散列表 vs 二叉查找树

散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 \(O(1)\)，非常高效。
叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度才是O(logn)。

第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 \(O(n)\) 的时间复杂度内，输出有序的数据序列。

第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 \(O(\log n)\)。

第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比logn小，所以实际的查找速度可能不一定比 \(O(\log n)\) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。

第四，散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。

最后，为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。

二叉查找树小结

它支持快速地查找、插入、删除操作。

二叉查找树中，每个节点的值都大于左子树节点的值，小于右子树节点的值。不过，这只是针对没有重复数据的情况。

对于存在重复数据的二叉查找树，两种构建方法，一种是让每个节点存储多个值相同的数据；另一种是，每个节点中存储一个数据。针对这种情况，我们只需要稍加改造原来的插入、删除、查找操作即可。

在二叉查找树中，查找、插入、删除等很多操作的时间复杂度都跟树的高度成正比。两个极端情况的时间复杂度分别是O(n)和O(logn)，分别对应二叉树退化成链表的情况和完全二叉树。

为了避免时间复杂度的退化，针对二叉查找树，我们又设计了一种更加复杂的树，平衡二叉查找树，时间复杂度可以做到稳定的 \(O(logn)\)。

红黑树（Red-Black Tree）

平衡二叉查找树

Splay Tree（伸展树）
Treap（树堆）
红黑树（简称 R-B Tree）

二叉树中任意一个节点的左右子树的高度相差不能大于1。

从这个定义来看，完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。

最先被发明的平衡二叉查找树是 AVL树。

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

红黑树中的节点，一类被标记为黑色，一类被标记为红色。

根节点是黑色的；
每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

画图将黑色的、空的叶子节点都省略

为什么说红黑树是“近似平衡”的？

“平衡”的意思可以等价为性能不退化。
“近似平衡”就等价为性能不会退化的太严重。

红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比AVL树要低。

所以，红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。

红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似 \(\log_{2} n\)，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 \(O(\log n)\)。

因为红黑树是一种性能非常稳定的二叉查找树，所以，在工程中，但凡是用到动态插入、删除、查找数据的场景，都可以用到它。不过，它实现起来比较复杂，如果自己写代码实现，难度会有些高，这个时候，我们其实更倾向用跳表来替代它。

实现红黑树的基本思想

在插入、删除节点的过程中，第三、第四点要求可能会被破坏，而我们今天要讲的“平衡调整”，实际上就是要把被破坏的 3、4 点恢复过来。

左旋（rotate left）：围绕某个节点的左旋
右旋（rotate right）：围绕某个节点的右旋

插入操作的平衡调整

红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。

如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。
如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。

红黑树的平衡调整过程是一个迭代的过程。我们把正在处理的节点叫作 关注节点。关注节点会随着不停地迭代处理，而不断发生变化。最开始的关注节点就是新插入的节点。

CASE 1：如果关注节点是a，它的叔叔节点 d 是红色，我们就依次执行下面的操作：

将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑ß色；
将关注节点 a 的祖父节点 c 的颜色设置成红色；
关注节点变成 a 的祖父节点 c；
跳到 CASE 2 或者 CASE 3。

CASE 2：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的右子节点，我们就依次执行下面的操作：

关注节点变成节点 a 的父节点 b；
围绕新的关注节点 b 左旋；
跳到 CASE 3。

CASE 3：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的左子节点，我们就依次执行下面的操作：

围绕关注节点 a 的祖父节点 c 右旋；
将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换。
调整结束。

删除操作的平衡调整

第一步：针对删除节点初步调整

初步调整只是保证整棵红黑树在一个节点删除之后，仍然满足最后一条定义的要求，也就是说，每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点。

CASE 1：如果要删除的节点是 a，它只有一个子节点 b

删除节点 a，并且把节点 b 替换到节点 a 的位置，这一部分操作跟普通的二叉查找树的删除操作一样；
节点 a 只能是黑色，节点 b 也只能是红色，其他情况均不符合红黑树的定义。这种情况下，我们把节点 b 改为黑色；
调整结束，不需要进行二次调整。

CASE 2：如果要删除的节点 a 有两个非空子节点，并且它的后继节点就是节点 a 的右子节点 c 。我们就依次进行下面的操作：

如果节点 a 的后继节点就是右子节点 c，那右子节点 c 肯定没有左子树。我们把节点 a 删除，并且将节点 c 替换到节点 a 的位置。这一部分操作跟普通的二叉查找树的删除操作无异；
然后把节点 c 的颜色设置为跟节点 a 相同的颜色；
如果节点 c 是黑色，为了不违反红黑树的最后一条定义，我们给节点 c 的右子节点 d 多加一个黑色，这个时候节点 d 就成了“红-黑”或者“黑-黑”；
这个时候，关注节点变成了节点 d，第二步的调整操作就会针对关注节点来做。

CASE 3：如果要删除的是节点 a，它有两个非空子节点，并且节点 a 的后继节点不是右子节点，我们就依次进行下面的操作：

找到后继节点 d，并将它删除，删除后继节点 d 的过程参照 CASE 1；
将节点 a 替换成后继节点 d ；
把节点 d 的颜色设置为跟节点 a 相同的颜色；
如果节点 d 是黑色，为了不违反红黑树的最后一条定义，我们给节点 d 的右子节点 c 多加一个黑色，这个时候节点 c 就成了“红-黑”或者“黑-黑”；
这个时候，关注节点变成了节点 c，第二步的调整操作就会针对关注节点来做。

第二步：针对关注节点进行二次调整

让它满足红黑树的第三条定义，即不存在相邻的两个红色节点。

经过初步调整之后，关注节点变成了“红-黑”或者“黑-黑”节点。针对这个关注节点，我们再分四种情况来进行二次调整。二次调整是为了让红黑树中不存在相邻的红色节点。

CASE 1：如果关注节点是a，它的兄弟节点 c 是红色的，我们就依次进行下面的操作：

围绕关注节点 a 的父节点 b 左旋；
关注节点 a 的父节点 b 和祖父节点 c 交换颜色；
关注节点不变；
继续从四种情况中选择适合的规则来调整。

CASE 2：如果关注节点是a，它的兄弟节点 c 是黑色的，并且节点 c 的左右子节点 d 、e都是黑色的，我们就依次进行下面的操作：

将关注节点 a 的兄弟节点 c 的颜色变成红色；
从关注节点 a 中去掉一个黑色，这个时候节点 a 就是单纯的红色或者黑色；
给关注节点 a 的父节点 b 添加一个黑色，这个时候节点 b 就变成了“红-黑”或者“黑-黑”；
关注节点从a变成其父节点 b ；
继续从四种情况中选择符合的规则来调整。

CASE 3：如果关注节点是a，它的兄弟节点 c 是黑色，c的左子节点 d 是红色，c的右子节点e是黑色，我们就依次进行下面的操作：

围绕关注节点 a 的兄弟节点 c 右旋；
节点 c 和节点 d 交换颜色；
关注节点不变；
跳转到 CASE 4，继续调整。

CASE 4：如果关注节点 a 的兄弟节点 c 是黑色的，并且c的右子节点是红色的，我们就依次进行下面的操作：

围绕关注节点 a 的父节点 b 左旋；
将关注节点 a 的兄弟节点 c 的颜色，跟关注节点 a 的父节点 b 设置成相同的颜色；
将关注节点 a 的父节点 b 的颜色设置为黑色；
从关注节点 a 中去掉一个黑色，节点 a 就变成了单纯的红色或者黑色；
将关注节点 a 的叔叔节点e设置为黑色；
调整结束。

为什么要求叶子节点是黑色的空节点？

为了实现起来方便。

假设红黑树的定义中不包含刚刚提到的那一条“叶子节点必须是黑色的空节点”

加上 “叶子节点必须是黑色的空节点”

会不会比较浪费存储空间呢？答案是不会的。

Trie树 / 字典树

它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

Trie树 的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

how，hi，her，hello，so，see

其中，根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（注意：红色节点并不都是叶子节点）。

构造过程的每一步，都相当于往Trie树中插入一个字符串。当所有字符串都插入完成之后，Trie树就构造好了。

“her”

“he”是某个字符串的前缀子串，但并不能完全匹配任何字符串。

如何实现一棵 Trie树？

将字符串集合构造成 Trie树
在 Trie树 中查询一个字符串

Trie树 是一个多叉树

// 二叉树
class BinaryTreeNode {
  char data;
  BinaryTreeNode left;
  BinaryTreeNode right;
}

class TrieNode {
  char data;
  TrieNode children[26];
}

字符串中只有从 a 到 z 这26个小写字母
组中下标为 0 的位置，存储指向子节点 a 的指针
下标为 1 的位置存储指向子节点 b 的指针
某个字符的子节点不存在，对应的下标的位置存储 null

public class Trie {
  private TrieNode root = new TrieNode('/'); // 存储无意义字符

  // 往Trie树中插入一个字符串
  public void insert(char[] text) {
    TrieNode p = root;
    for (int i = 0; i < text.length; ++i) {
      int index = text[i] - 'a';
      if (p.children[index] == null) {
        TrieNode newNode = new TrieNode(text[i]);
        p.children[index] = newNode;
      }
      p = p.children[index];
    }
    p.isEndingChar = true;
  }

  // 在Trie树中查找一个字符串
  public boolean find(char[] pattern) {
    TrieNode p = root;
    for (int i = 0; i < pattern.length; ++i) {
      int index = pattern[i] - 'a';
      if (p.children[index] == null) {
        return false; // 不存在pattern
      }
      p = p.children[index];
    }
    if (p.isEndingChar == false) return false; // 不能完全匹配，只是前缀
    else return true; // 找到pattern
  }

  public class TrieNode {
    public char data;
    public TrieNode[] children = new TrieNode[26];
    public boolean isEndingChar = false;
    public TrieNode(char data) {
      this.data = data;
    }
  }
}

构建Trie树的过程，需要扫描所有的字符串，时间复杂度是O(n)（n表示所有字符串的长度和）。但是一旦构建成功之后，后续的查询操作会非常高效。

每次查询时，如果要查询的字符串长度是k，那我们只需要比对大约k个节点，就能完成查询操作。跟原本那组字符串的长度和个数没有任何关系。所以说，构建好Trie树后，在其中查找字符串的时间复杂度是O(k)，k表示要查找的字符串的长度。

缩点优化

Trie树与散列表、红黑树的比较

Trie树比较适合的是查找前缀匹配的字符串

应用

自动输入补全
- 输入法自动补全功能
- IDE代码编辑器自动补全功能
- 浏览器网址输入的自动补全功能

内容小结

“红黑树一向都很难学”，有这种想法的人很多。其实主要原因是，很多人试图去记忆它的平衡调整策略。

第一点，把红黑树的平衡调整的过程比作魔方复原，不要过于深究这个算法的正确性。你只需要明白，只要按照固定的操作步骤，保持插入、删除的过程，不破坏平衡树的定义就行了。
第二点，找准关注节点，不要搞丢、搞错关注节点。因为每种操作规则，都是基于关注节点来做的，只有弄对了关注节点，才能对应到正确的操作规则中。在迭代的调整过程中，关注节点在不停地改变，所以，这个过程一定要注意，不要弄丢了关注节点。
第三点，插入操作的平衡调整比较简单，但是删除操作就比较复杂。针对删除操作，我们有两次调整，第一次是针对要删除的节点做初步调整，让调整后的红黑树继续满足第四条定义，“每个节点到可达叶子节点的路径都包含相同个数的黑色节点”。但是这个时候，第三条定义就不满足了，有可能会存在两个红色节点相邻的情况。第二次调整就是解决这个问题，让红黑树不存在相邻的红色节点。

Trie树是一种解决字符串快速匹配问题的数据结构。如果用来构建Trie树的这一组字符串中，前缀重复的情况不是很多，那Trie树这种数据结构总体上来讲是比较费内存的，是一种空间换时间的解决问题思路。

尽管比较耗费内存，但是对内存不敏感或者内存消耗在接受范围内的情况下，在 Trie树中做字符串匹配还是非常高效的，时间复杂度是 \(O(k)\)，k表示要匹配的字符串的长度。

但是，Trie树的优势并不在于，用它来做动态集合数据的查找，因为，这个工作完全可以用更加合适的散列表或者红黑树来替代。Trie树最有优势的是查找前缀匹配的字符串，比如搜索引擎中的关键词提示功能这个场景，就比较适合用它来解决，也是 Trie树比较经典的应用场景。

高级

实战

https://time.geekbang.org/column/intro/126 ↩︎

Game 2020

https://2020.iosdevlog.com