數據結構

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}