## 2-3 树

Allow 1 or 2 keys per node.

- 2-node: one key, two children.
- 3-node: two keys, three children.

Symmetric order. Inorder traversal yields keys in ascending order.

Perfect balance. Every path from root to null link has same length.

### Global properties in a 2-3 tree

Invariants. Maintains symmetric order and perfect balance.

### 2-3 树性能

## 红黑树

### 使用红黑树代表2-3树

### An equivalent definition

A BST such that:

- No node has two red links connected to it.
- Every path from root to null link has the same number of black links(perfect black balance).
- Red links lean left.

### 红黑树和2-3树的一一对应关系

### Search implementation for red-black BSTs

Observation. Search is the same as for elementary BST (ignore color).

1 | public Val get(Key key) |

### Red-black BST representation

Each node is pointed to by precisely one link(from its parent) => can encode color of links in nodes.

1 | private static final boolean RED = true; |

### Elementary red-black BST operations

#### Left rotation.

Orient a (temporarily) right-leaning red link to lean left.

1 | private Node rotateLeft(Node h) |

#### Right rotation.

Orient a left-leaning red link to (temporarily) lean right.

1 | private Node rotateRight(Node h) |

#### Color flip.

Recolor to split a (temporary) 4-node.

1 | private void flipColors(Node h) |

### 向红黑树插入一个新节点

#### Warmup 1: Insert into a tree with exactly 1 node.

#### Case 1: Insert into a 2-node at the bottom.

- Do standard BST insert; color new link red.
- If new red link is right link, rotate left.

#### Warmup 2: Insert into a tree with exactly 2 node.

#### Case 2: Insert into a 3-node at the bottom.

- Do standard BST insert; color new link red.
- Rotate to balance the 4-node (if needed).
- Flip colors to pass red link up one level.
- Rotate to make lean left (if needed).
- Repeat case 1 or case 2 up the tree (if needed).

#### Same code for all cases.

- Right child red, left child black: rotate left.
- Left child, left-left grandchild red: rotate right.
- Both child red: flip colors.

1 | private Node put(Node h, Key key, Value val) |