数据结构

Doubly Linked List

什么是双向链表

双向链表是一种特殊的链表，其中的每个节点都包含前一个和后一个节点的引用。下面是一个双向链表的简单示例：

 1// Class for Doubly Linked List
 2public class DLL {
 3    // Head of list
 4    Node head;
 5    // Doubly Linked list Node
 6    class Node {
 7        int data;
 8        Node prev;
 9        Node next;
10        // Constructor to create a new node
11        // next and prev is by default initialized as null
12        Node(int d) { data = d; }
13    }
14}

1# Node of a doubly linked list
2class Node:
3    def __init__(self, next=None, prev=None, data=None):
4        # reference to next node in DLL
5        self.next = next
6         
7        # reference to previous node in DLL
8        self.prev = prev
9        self.data = data

 1type Node struct {
 2    Value    int
 3    Previous *Node
 4    Next     *Node
 5}
 6
 7type LinkedList struct {
 8    Head  *Node
 9    Length int
10}

对比普通链表的优势

可以向前或者向后遍历
给定一个节点，如果需要删除它，双向链表比单向链表更快一些，因为你可以执行以下逻辑即可删除，而不需要再次查找一次节点的 prev
```
1node.prev.next = node.next
2node.next.prev = node.prev
```
同理，给定一个节点，在其前面插入一个新的节点更快

对比普通链表的劣势

空间浪费：每个节点都要保存上一个节点的引用。使用 C++ 的一个示例可以解决空间浪费的问题，见此 https://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-1/
因为多了一个引用，每次操作都需要更多的动作

应用场景

浏览器的前进和后退
很多程序的 undo 和 redo 功能
LRU ( Least Recently Used ) / MRU ( Most Recently Used ) Cache

2-3 Search Tree

建议看 Coursera 上的视频 https://www.coursera.org/learn/algorithms-part1/lecture/wIUNW/2-3-search-trees，本章节的动画文件均由该视频截屏后转换。

概念和图每个 node 允许 1-2 个元素
- 2-node: 1 元素，2个子 node
- 3-node: 2 元素，3个子 node
- 从 root 到 null link 的每条路径都等长
2-3 tree demo 搜索的过程
2-3 tree demo 插入
插入到一个 3-node 会发生什么？
2-3 tree 构造过程
属性
始终维护对称和平衡。
性能
1. 完美的平衡：每条从根节点到 null links 的路径都有相同的长度
2. 树的高度：
  1. 最差情况：log₂N，全部是 2-node
  2. 最好情况：log₃N，全部是 3-node
  3. 12-20（100万node）
  4. 18-30（10亿node）
3. 查询和插入操作对数级性能

Red Black BSTs

BST means binary search tree.

Left-leaning read-black BSTs

左倾红黑树：通过红色胶水（红线）将 3-node 中的两个元素粘起来

一个等价的定义

如果一个 BST 满足以下几个条件，那么它就是一个左倾红黑树（LLRB）：

没有节点同时连接了两条红线
每条从 root 到 null link 的路径有相同数量的黑线（2-3树的特性）
红线向左倾斜

实际上，从任意一个节点到其子树的叶子节点经过的黑线都是相同的。

搜索忽略颜色，和普通的 BST 一致，但是因为其保持较好的平衡，通常更快。

 1public Val get(Key key){
 2     Node x = root;
 3     while (x != null){
 4         int cmp = key.compareTo(x.key);
 5         if (cmp < 0) x = x.left;
 6         else if (cmp > 0) x = x.right;
 7         else if (cmp == 0) return x.val;
 8     }
 9     return null;
10}

因为每个节点和父节点相连的只有一条线，因此可以将颜色编码到代码里面

 1 private static final boolean RED = true;
 2 private static final boolean BLACK = false;
 3 private class Node {
 4    Key key;
 5    Value val;
 6    Node left, right;
 7    boolean color; // 注意这里 color 是指连接父节点的线的颜色
 8 }
 9 private boolean isRed(Node x) {
10    if (x == null) return false; // null links are black
11    return x.color == RED;
12 }

上面的代码用图来解释，就是：

左旋（右旋同理，不变的是要维持树的平衡和对称）

1private Node rotateLeft(Node h) {
2    assert isRed(h.right);
3    Node x = h.right;
4    h.right = x.left;
5    x.left = h;
6    x.color = h.color;
7    h.color = RED;
8    return x;
9}