```java
package ds.impl;
import ds.Queue;
public class BST<K extends Comparable<K>, V> {
private Node root;
private class Node {
private K key;
private V value;
private Node left, right;
private int size;
public Node(K key, V value, int size) {
this.key = key;
this.value = value;
this.size = size;
}
}
public int size() {
return size(root);
}
private int size(Node x) {
return x == null ? 0 : x.size;
}
public V get(K key) {
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;
}
}
public void put(K key, V value) {
root = put(root, key, value);
}
private Node put(Node x, K key, V value) {
if (x == null) {
return new Node(key, value, 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;
}
x.size = size(x.left) + size(x.right) + 1;
return x;
}
public K minKey() {
return minKey(root).key;
}
private Node minKey(Node x) {
return x.left == null ? x : minKey(x.left);
}
public K maxKey() {
return maxKey(root).key;
}
private Node maxKey(Node x) {
return x.right == null ? x : maxKey(x.right);
}
public K floorKey(K key) {
Node x = floorKey(root, key);
return x == null ? null : x.key;
}
private Node floorKey(Node x, K key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp == 0) {
return x;
}
if (cmp < 0) {
return floorKey(x, key);
}
Node t = floorKey(x.right, key);
return t != null ? t : x;
}
public K ceilKey(K key) {
Node x = ceilKey(root, key);
return x == null ? null : x.key;
}
private Node ceilKey(Node x, K key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp == 0) {
return x;
}
if (cmp > 0) {
return ceilKey(x, key);
}
Node t = ceilKey(x.left, key);
return t != null ? t : x;
}
public K selectKey(int k) {
return selectKey(root, k).key;
}
private Node selectKey(Node x, int k) {
if (x == null) {
return null;
}
int t = size(x.left);
if (t > k) {
return selectKey(x.left, k);
} else if (t < k) {
return selectKey(x.right, k - t - 1);
} else {
return x;
}
}
public int rankKey(K key) {
return rankKey(root, key);
}
private int rankKey(Node x, K key) {
if (x == null) {
return 0;
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
return rankKey(x.left, key);
} else if (cmp > 0) {
return 1 + size(x.left) + rankKey(x.right, key);
} else {
return size(x.left);
}
}
public void deleteMin() {
root = deleteMin(root);
}
private Node deleteMin(Node x) {
if (x.left == null) {
return x.right;
}
x.left = deleteMin(x.left);
x.size = size(x.left) + size(x.right) + 1;
return x;
}
public void deleteMax() {
root = deleteMax(root);
}
private Node deleteMax(Node x) {
if (x.right == null) {
return x.left;
}
x.right = deleteMax(x.right);
x.size = size(x.left) + size(x.right) + 1;
return x;
}
public void delete(K key) {
root = delete(root, key);
}
private Node delete(Node x, K key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = delete(x.left, key);
} else if (cmp > 0) {
x.right = delete(x.right, key);
} else {
if (x.right == null) {
return x.left;
}
if (x.left == null) {
return x.right;
}
Node t = x;
x = minKey(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
x.size = size(x.left) + size(x.right) + 1;
return x;
}
public Iterable<K> keys() {
return keys(minKey(), maxKey());
}
private Iterable<K> keys(K lowKey, K highKey) {
LinkedQueue<K> queue = new LinkedQueue<>();
keys(root, queue, lowKey, highKey);
return queue;
}
private void keys(Node x, Queue<K> queue, K lowKey, K highKey) {
if (x == null) {
return;
}
int cmpLow = lowKey.compareTo(x.key);
int cmpHigh = highKey.compareTo(x.key);
if (cmpLow < 0) {
keys(x.left, queue, lowKey, highKey);
}
if (cmpLow <= 0 && cmpHigh >= 0) {
queue.enqueue(x.key);
}
if (cmpHigh > 0) {
keys(x.right, queue, lowKey, highKey);
}
}
}
```
- 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刷題筆記