```java
package ds.impl;
import java.util.NoSuchElementException;
public class RedBlackBST<K extends Comparable<K>, V> {
private Node root;
private class Node {
private K key;
private V value;
private Node left;
private Node right;
private boolean isRed;
private int size;
public Node(K key, V value, boolean isRed, int size) {
this.isRed = isRed;
this.key = key;
this.value = value;
this.size = size;
}
}
private boolean isRed(Node x) {
return x == null ? false : x.isRed;
}
private int size(Node x) {
return x == null ? 0 : x.size;
}
public int size() {
return size(root);
}
public boolean isEmpty() {
return root == null;
}
public V get(K key) {
if (key == null) {
throw new IllegalArgumentException();
}
return get(root, key);
}
private V get(Node x, K key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
return get(x.left, key);
} else if (cmp > 0) {
return get(x.right, key);
} else {
return x.value;
}
// while (x != null) {
// int cmp = key.compareTo(x.key);
// if (cmp < 0) {
// x = x.left;
// } else if (cmp > 0) {
// x = x.right;
// } else {
// return x.value;
// }
// }
// return null;
}
public boolean containsKey(K key) {
return get(key) != null;
}
private void delete(K key) {
if (key == null) {
throw new IllegalArgumentException();
}
if (!containsKey(key)) {
return;
}
if (!isRed(root.left) && !isRed(root.right)) {
root.isRed = true;
}
root = delete(root, key);
if (!isEmpty()) {
root.isRed = false;
}
}
private Node delete(Node x, K key) {
int cmp = key.compareTo(x.key);
if (cmp < 0) {
if (!isRed(x.left) && !isRed(x.left.left)) {
x = moveRedLeft(x);
}
x.left = delete(x.left, key);
} else {
if (isRed(x.left)) {
x = rotateRight(x);
}
if (key.compareTo(x.key) == 0 && x.right == null) {
return null;
}
if (!isRed(x.right) && !isRed(x.right.left)) {
x = moveRedRight(x);
}
if (key.compareTo(x.key) == 0) {
Node rightMinNode = min();
x.key = rightMinNode.key;
x.value = rightMinNode.value;
x.right = deleteMin(x.right);
} else {
x.right = delete(x.right, key);
}
}
return balance(x);
}
public void put(K key, V value) {
if (key == null) {
throw new IllegalArgumentException();
}
if (value == null) {
delete(key);
return;
}
root = put(root, key, value);
root.isRed = false;
}
private Node put(Node x, K key, V value) {
if (x == null) {
return new Node(key, value, true, 1);
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = put(x.left, key, value);
} else if (cmp > 0) {
x.right = put(x.right, key, value);
} else {
x.value = value;
}
if (isRed(x.right) && !isRed(x.left)) {
x = rotateLeft(x);
} else if (isRed(x.left) && !isRed(x.right)) {
x = rotateRight(x);
} else if (isRed(x.left) && isRed(x.right)) {
flipColors(x);
}
x.size = size(x.left) + size(x.right) + 1;
return x;
}
private Node rotateLeft(Node x) {
Node result = x.right;
x.right = result.left;
result.left = x;
result.isRed = result.left.isRed;
result.left.isRed = true;
result.size = x.size;
x.size = size(x.left) + size(x.right) + 1;
return result;
}
private Node rotateRight(Node x) {
Node result = x.left;
x.left = result.right;
result.right = x;
result.isRed = result.right.isRed;
result.right.isRed = true;
result.size = x.size;
x.size = size(x.left) + size(x.right) + 1;
return result;
}
private void flipColors(Node x) {
x.isRed = !x.isRed;
x.left.isRed = !x.left.isRed;
x.right.isRed = !x.right.isRed;
}
private Node moveRedLeft(Node x) {
flipColors(x);
if (isRed(x.right.left)) {
x.right = rotateRight(x.right);
x = rotateLeft(x);
flipColors(x);
}
return x;
}
private Node moveRedRight(Node x) {
flipColors(x);
if (isRed(x.left.left)) {
x = rotateRight(x);
flipColors(x);
}
return x;
}
private Node min() {
throw new UnsupportedOperationException();
}
private Node deleteMin(Node right) {
throw new UnsupportedOperationException();
}
private Node balance(Node x) {
if (isRed(x.right)) {
x = rotateLeft(x);
}
if (isRed(x.left) && isRed(x.left.left)) {
x = rotateRight(x);
}
if (isRed(x.left) && isRed(x.right)) {
flipColors(x);
}
x.size = size(x.left) + size(x.right) + 1;
return x;
}
public int height() {
return height(root);
}
private int height(Node x) {
if (x == null) {
return -1;
}
return 1 + mathMax(height(x.left), height(x.right));
}
private int mathMax(int a, int b) {
return a > b ? a : b;
}
public K minKey() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return minKey(root).key;
}
private Node minKey(Node x) {
return x.left == null ? x : minKey(x.left);
}
public K maxKey() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return maxKey(root).key;
}
private Node maxKey(Node x) {
return x.right == null ? x : maxKey(x.right);
}
public Iterable<K> keys() {
if (isEmpty()) {
return new LinkedQueue<K>();
}
return keys(minKey(), maxKey());
}
public Iterable<K> keys(K lo, K hi) {
if (lo == null) {
throw new IllegalArgumentException("first argument to keys() is null");
}
if (hi == null) {
throw new IllegalArgumentException("second argument to keys() is null");
}
LinkedQueue<K> queue = new LinkedQueue<>();
// if (isEmpty() || lo.compareTo(hi) > 0) return queue;
keys(root, queue, lo, hi);
return queue;
}
private void keys(Node x, LinkedQueue<K> queue, K lo, K hi) {
if (x == null) {
return;
}
int cmplo = lo.compareTo(x.key);
int cmphi = hi.compareTo(x.key);
if (cmplo < 0) {
keys(x.left, queue, lo, hi);
}
if (cmplo <= 0 && cmphi >= 0) {
queue.enqueue(x.key);
}
if (cmphi > 0) {
keys(x.right, queue, lo, hi);
}
}
public static void main(String[] args) {
RedBlackBST<String, Integer> st = new RedBlackBST<>();
for (int i = 0; i < 100000; i++) {
String key = "key" + i;
Integer value = (int) (Math.random() * 10000);
st.put(key, value);
}
for (String s : st.keys()) {
System.out.println(s + " " + st.get(s));
}
System.out.println();
}
}
```
- 1 設計接口
- 1.1 容器接口Container
- 1.2 背包接口Bag
- 1.3 棧接口Stack
- 1.4 隊列接口Queue
- 1.5 Union-Find算法接口UF
- 2 實現接口
- 2.1 結點類Node
- 2.2 數組迭代器ArrayIterator
- 2.3 鏈表迭代器ListIterator
- 2.4 背包(Bag)的實現
- 2.4.1 能動態調整數組大小的Bag
- 2.4.2 鏈式Bag的實現
- 2.5 棧(Stack)的實現
- 2.5.1 能動態調整數組大小的Stack
- 2.5.2 鏈式Stack的實現
- 2.6 隊列(Queue)的實現
- 2.6.1 能動態調整數組大小的Queue
- 2.6.2 鏈式Queue的實現
- 2.7 Union-Find算法的實現
- 2.7.1 DefaultUF
- 2.7.2 QuickFindUF
- 2.7.3 QuickUnionUF
- 2.7.4 WeightedQuickUnionUF
- 2.8 測試
- 2.8.1 測試Stack
- 2.8.2 測試Union-Find
- 3 排序算法
- 3.1 定義排序工具的類結構
- 3.2 選擇排序
- 3.3 插入排序
- 3.4 希爾排序
- 3.5 歸并排序
- 3.5.1 歸并排序的合并方法
- 3.5.2 自頂向下的歸并排序
- 3.5.3 自底向上的歸并排序
- 3.6 快速排序
- 3.6.1 常規快速排序
- 3.6.2 排序前先洗牌
- 3.6.3 快速排序的改進方法-小數據量轉成插入排序
- 3.6.4 快速排序的改進方法-三向切分
- 3.7 堆排序
- 3.8 最終的排序工具
- 4 搜索
- 4.1 二分搜索(binarySearch)
- 4.2 優先隊列(MaxPriorityQueue)
- 4.3 二叉查找樹(BST)
- 4.4 紅黑二叉查找樹(RedBlackBST)
- 4.5 B-樹(BTree)
- 5 圖
- 5.1 無向圖(Graph)
- 5.2 有向圖(Digraph)
- 6 貪心
- Dijkstra算法-單元最短路徑
- 7 動態規劃
- 7.1 最長公共子序列問題
- 7.2 0-1背包問題
- 7.3 加工順序問題
- 8 搜索法
- 8.1 圖的著色問題
- 8.2 深度優先搜索
- 8.3 回溯法
- 8.3.1 回溯法的算法框架
- 8.3.2 子集樹
- 8.3.3 排列樹
- 8.3.4 滿m叉樹(組合樹)
- 8.4 廣度優先搜索
- 8.5 分支限界法
- 9 隨機化算法
- 9.1 數值隨機化算法
- 9.2 蒙特卡羅算法
- 9.3 拉斯維加斯算法
- 9.4 舍伍德算法
- 10 數論算法
- 10.1 Stein求最大公約數
- 10.2 矩陣求斐波那切數列
- LeetCode刷題筆記