```java
package ds.impl;
import ds.Container;
public class BTree<K extends Comparable<K>, V> implements Container {
private static final int M = 4;
private Node root;
private int height;
private int size;
private static class Node {
private int m;
private final Entry[] children = new Entry[M];
public Node(int k) {
m = k;
}
}
private static class Entry {
private Comparable key;
private final Object value;
private Node next;
public Entry(Comparable key, Object value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
public BTree() {
root = new Node(0);
}
@Override
public int size() {
return size;
}
public int height() {
return height;
}
public V get(K key) {
if (key == null) {
throw new IllegalArgumentException();
}
return search(root, key, height);
}
private V search(Node node, K key, int height) {
Entry[] children = node.children;
if (height == 0) {
for (int i = 0; i < node.m; i++) {
if (eq(key, children[i].key)) {
return (V) children[i].value;
}
}
} else {
for (int i = 0; i < node.m; i++) {
if (i + 1 == node.m || less(key, children[i + 1].key)) {
return search(children[i].next, key, height - 1);
}
}
}
return null;
}
private boolean eq(Comparable k1, Comparable k2) {
return k1.compareTo(k2) == 0;
}
private boolean less(Comparable k1, Comparable k2) {
return k1.compareTo(k2) < 0;
}
public void put(K key, V value) {
if (key == null) {
throw new IllegalArgumentException();
}
Node u = insert(root, key, value, this.height);
size++;
if (u == null) {
return;
}
Node t = new Node(2);
t.children[0] = new Entry(root.children[0].key, null, root);
t.children[1] = new Entry(u.children[0].key, null, u);
root = t;
height++;
}
private Node insert(Node node, K key, V value, int height) {
int i;
Entry entry = new Entry(key, value, null);
if (height == 0) {
for (i = 0; i < node.m; i++) {
if (less(key, node.children[i].key)) {
break;
}
}
} else {
for (i = 0; i < node.m; i++) {
if ((i + 1 == node.m) || less(key, node.children[i + 1].key)) {
Node next = node.children[i++].next;
Node u = insert(next, key, value, height - 1);
if (u == null) {
return null;
}
entry.key = u.children[0].key;
entry.next = u;
break;
}
}
}
for (int j = node.m; j > i; j--) {
node.children[j] = node.children[j - 1];
}
node.children[i] = entry;
node.m++;
if (node.m < M) {
return null;
} else {
return split(node);
}
}
private Node split(Node node) {
int m = M / 2;
Node result = new Node(m);
node.m = m;
for (int j = 0; j < m; j++) {
result.children[j] = node.children[m + j];
}
return result;
}
@Override
public String toString() {
return toString(root, height, "") + "\n";
}
private String toString(Node node, int height, String indent) {
StringBuilder s = new StringBuilder();
Entry[] children = node.children;
if (height == 0) {
for (int j = 0; j < node.m; j++) {
s.append(indent)
.append(children[j].key)
.append('=')
.append(children[j].value)
.append('\n');
}
} else {
for (int j = 0; j < node.m; j++) {
if (j > 0) {
s.append(indent)
.append('(')
.append(children[j].key)
.append(')')
.append('\n');
}
s.append(toString(children[j].next, height - 1, indent + "#"));
}
}
return s.toString();
}
public static void main(String[] args) {
BTree<String, String> st = new BTree<>();
st.put("www.cs.princeton.edu", "128.112.136.12");
st.put("www.cs.princeton.edu", "128.112.136.11");
st.put("www.princeton.edu", "128.112.128.15");
st.put("www.yale.edu", "130.132.143.21");
st.put("www.simpsons.com", "209.052.165.60");
st.put("www.apple.com", "17.112.152.32");
st.put("www.amazon.com", "207.171.182.16");
st.put("www.ebay.com", "66.135.192.87");
st.put("www.cnn.com", "64.236.16.20");
st.put("www.google.com", "216.239.41.99");
st.put("www.nytimes.com", "199.239.136.200");
st.put("www.microsoft.com", "207.126.99.140");
st.put("www.dell.com", "143.166.224.230");
st.put("www.slashdot.org", "66.35.250.151");
st.put("www.espn.com", "199.181.135.201");
st.put("www.weather.com", "63.111.66.11");
st.put("www.yahoo.com", "216.109.118.65");
System.out.println("cs.princeton.edu: " + st.get("www.cs.princeton.edu"));
System.out.println("hardvardsucks.com: " + st.get("www.harvardsucks.com"));
System.out.println("simpsons.com: " + st.get("www.simpsons.com"));
System.out.println("apple.com: " + st.get("www.apple.com"));
System.out.println("ebay.com: " + st.get("www.ebay.com"));
System.out.println("dell.com: " + st.get("www.dell.com"));
System.out.println();
System.out.println("size: " + st.size());
System.out.println("height: " + st.height());
System.out.println(st);
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刷題筆記