CS61B Data Structure 从ADTs到红黑树再到Hashing - 仿生鱼会梦到电子池塘吗

ADT (抽象数据类型)#

ADT 是一种设计层面抽象的数据类型，在设计或构思一个 ADT 时，我们关心的是这个 ADT 的行为是什么，我们关注它是做什么(What)的，而不关注它们是怎么做的(How)。总而言之，我们关注的是 ADT 的行为和特征，而不关注 ADT 是如何实现的，ADT 就好比接口(Interface)，一种 ADT 规定了这种抽象数据类型可以做什么，但是并不关注这些操作是如何**实现(implementation)**的。

所以，ADT 实际上就是数据类型版的接口，它是基于那些具体的数据类型(链表，数组)来实现自身的结构和功能，并且更高一层次的抽象概念。

例如： 一个 Set (集合)，规定了自己可以进行 add, contains, remove 等操作，并且 Set 中的元素不能有重复的。

对于 Set 的实现，可以通过数组，链表，二叉搜索树或者是哈希表等具体数据结构来实现。

ADT 的实现有着一种天然的封装性，使用者在使用时只需要调用 ADT 规定的行为方法即可，而不用关心底层的具体数据结构是如何 work 的。这种封装性也能简化思考，基于这种 ADT 去实现其他功能时，使用 ADT 的设计者只需要站在 ADT 的角度去思考即可，而不用管底层的数据结构时怎么样的。

常用的两种 ADT: Maps(映射/字典) 与 Sets(集合)#

Sets (集合)#

用于存储一组不重复的元素，且不关心元素的顺序。

主要方法:
1. add(element): 添加新元素，若元素已存在则不进行任何操作。
2. contains(element): 检查集合中是否包含某个元素。
3. remove(element): 移除一个元素。

Maps (映射/字典)#

用于存储一组从键(Key)到值(Value)的映射关系，其中键是唯一的，不可重复的。

主要方法:
1. put(key, value): 将一对键值对存入 Map，如果 key 已存在，则会用新 value 覆盖掉旧 value。
2. get(key): 根据键获取对应的值。
3. containsKey(key): 检查 Map 中是否包含某个 key。

Maps 可以通过 key 来对 value 进行快速的查找。

一种高效的底层数据结构: BST (Binary Search Tree)#

BST 通过二叉树结构，存储了一系列已经排序好的数据，这种结构可以通过简单的逻辑规则对已存储的数据进行查找：

其左子树中的所有节点的值，都小于 X 的值。
其右子树中的所有节点的值，都大于 X 的值。
它的左、右子树本身也都是二叉搜索树。

如果要查找的值比该节点的值大，则访问该节点的右子树；如果比该节点的值小，则访问左子树。每次访问都可以排除掉一半的元素。

通过树结构对元素进行查找时，查找所需要的步数等于元素在树中的高度。

性能#

当树平衡(左右子树的高度基本相同): O(log N)
当树不平衡(按顺序插入元素，此时树会退化成链表): O(N)

从 BST 到 B-Trees#

为了解决上述 BST 的不平衡问题，B 树(B-Trees)被提出。B 树是一种能做到自平衡的树，常用的有 2-3 树和 2-3-4 树，B 树通过一系列的规则来实现自平衡。

以 2-3 树为例：

一个 2-3 树的节点，最多可以存储 2 个元素(假设为 A, B)，当第三个元素(C)被存入时，节点(A, B, C)的中间元素(B)会从该节点分裂出去，存入该节点的父节点。这种分裂的操作，仍然使得 B 树中的元素是有序的。

由此可见，B 树是一种自下而上构建的树，树的父节点依靠于底下节点的不断分裂和上推而来。由此可得到以下的 2-3 树性质：

每个节点可以存有 1 个或 2 个元素。
B 树是自下而上构建的，所以所有的非树叶节点，一定存在左右分支，不存在只有一个分支的节点。
如果一个节点有 1 个元素，它有 2 个子节点（称为 2-节点）。
如果一个节点有 2 个元素，它有 3 个子节点（称为 3-节点）。若一个节点含有两个元素，则说明其下面的子节点(左节点或右节点)发生了分裂和上推，分裂使得该子节点由一个变成了两个，最终使得该节点有三个分支。
所有的叶子节点都在同一层，保证了树的完美平衡。

LLRBT (Left-Leaning Red-Black Trees) - 左倾红黑树#

B 树实现了一个很优雅的自平衡，但是在实际的数据结构的实现上，B 树并不容易实现。

LLRBT 可以通过红色链接来模拟一个 B 树：一个红色的链接将其子节点“粘合”到父节点上，表示它们在 B 树中实际上属于同一个节点。LLRBT 本质上是一个二叉树。

核心操作：旋转 (Rotate) 与颜色翻转 (Flip)#

旋转 (rotate): 有右旋(顺时针旋转)和左旋(逆时针旋转)
- 右旋： 将某一个元素右旋，就是 h 的左子节点 x 上升为新的根，h 变成 x 的右子节点，x 原来的右子树成为 h 的新的左子树，x 继承 h 原来的颜色，h 变为红色。
```
1
```java
  2
      h (color)           x (color)
  3
     /          =>         \
  4
    x (red)                 h (red)
  5
   /
  6
  z (red)
  7
```
```
- 左旋： 将 h 和 x 之间的链接像绳子一样向上提，x 成为了新的根。h 变成了 x 的左子节点。x 原来的左子树(在 h 和 x 之间)现在成为了 h 的新的右子树。x 继承 h 原来的颜色，h 变为红色。
```
1
```java
  2
      h (black)           x (black)
  3
       \         =>        /
  4
        x (red)           h (red)
  5
```
```
颜色反转 (flip): 顾名思义，将与某一节点链接的红色链接变为黑色链接，黑色链接变为红色链接。

LLRB 的三大不变性 (Invariants)#

为了让 LLRBT 能够完全模拟 B 树的结构，它需要满足以下的条件：

红色链接左倾 (Red links lean left)： 不允许存在红色右链接。如果出现，必须通过左旋 (rotate left) 来修正。这是 LLRB 的核心简化规则，它将 3-节点（一个黑节点一个红节点）的表示方式从两种（红左或红右）统一为一种，大大减少了需要处理的情况。
不允许连续红色链接 (No two red links in a row)： 一个节点的父链接和其自身的左链接不能同时为红色。这相当于禁止了在 B 树的一个节点中存储超过 3 个键（即模拟的 4-节点已经是极限）。如果出现这种情况，需要通过右旋 (rotate right) 来修正。
完美黑色平衡 (Perfect black balance)： 从根节点到任意 null 链接的路径上，黑色链接的数量必须完全相同。这是对 B 树“所有叶子在同一层”这一性质的直接模拟。这个平衡是通过颜色翻转 (color flip) 来维持的。当一个节点（例如 h）的左右子链接都为红色时，就意味着我们形成了一个临时的 4-节点。颜色翻转操作会将 h.left 和 h.right 的颜色变为黑色，同时将 h 自身的颜色变为红色。这本质上就是 B 树中将中间元素“向上推”的操作。

为了实现这三条规则，有如下的操作：

存在右边的红色链接，则把该父节点左旋。
某节点同时存在两个连续的左向红色链接：将该节点右旋。
某节点同时存在左向红色链接和右向红色链接：反转颜色。

通过红色链接的定义以及三条规则，LLRBT 就实现了对 B 树的模拟，这就是红黑树的由来 (LLRBT 只是一种简化版的红黑树，实际情况中的红黑树设计还需要考虑大量的对称性等问题，但本门课只要求掌握 LLRBT 即可)。

Hashing 的部分明天再写，胃炎我****。