基于有序链表的二分查找
public class BinarySearchST<Key extends Comparable<Key>, Value> {
private Key[] keys;
private Value[] vals;
private int N;
public BinarySearchST(int capacity) {
keys = (Key[]) new Comparable[capacity];
vals = (Value[]) new Object[capacity];
}
public int size() {
return N;
}
public int rank(Key key) {
int lo = 0, hi = N - 2;
while(lo <= hi) {
int mid = lo + (hi - lo) / 2;
int cmp = key.compareTo(keys[mid]);
if (cmp < 0 ) {
hi = mid - 1;
} else if (cmp > 0) {
lo = mid + 1;
} else {
return mid;
}
}
return lo;
}
public void put(Key key, Value val) {
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0) {
vals[i] = val;
return;
}
for(int j = N; j > i; j--) {
keys[j] = keys[j - 1];
vals[j] = vals[j - 1];
}
keys[i] = key;
vals[i] = val;
N++;
}
}
二叉树查找
public class BST<Key extends Comparable<Key> , Value> {
private class Node {
private Key key;
private Value value;
private Node left, right;
private int N;
public Node(Key key, Value value, int N) {
this.key = key;
this.value = value;
this.N = N;
}
}
private Node root;
public int size() {
return size(root);
}
private int size(Node x) {
if (x == null) {
return 0;
}
return x.N;
}
public Value get(Key key) {
return get(root, key);
}
private Value get(Node x, Key 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(Key key, Value value) {
root = put(root, key, value);
}
private Node put(Node x, Key key, Value 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.N = size(x.left) + size(x.right) + 1;
return x;
}
public Key min() {
return min(root).key;
}
private Node min(Node x) {
if (x.left == null) { return x; }
return min(x.left);
}
public Key max() {
return max(root).key;
}
private Node max(Node x) {
if (x.right == null) {
return x;
}
return max(x.right);
}
public Key floor(Key key) {
Node x = floor(root, key);
if (x == null) { return null; }
return x.key;
}
private Node floor(Node x, Key key) {
if (x == null) { return null; }
int cmp = key.compareTo(x.key);
if (cmp == 0) { return x; }
if (cmp < 0) { return floor(x.left, key); }
Node t = floor(x.right, key);
if (t != null) {
return t;
} else {
return x;
}
}
public Key select(int k) {
return select(root, k).key;
}
private Node select(Node x, int k) {
if (x == null) {return null; }
int t = size(x.left);
if (t > k) {
return select(x.left, k);
} else if(t < k) {
return select(x.right, k);
} else {
return x;
}
}
public int rank(Key key) {
return rank(key, root);
}
private int rank(Key key, Node x) {
if (x == null) {return 0; }
int cmp = key.compareTo(x.key);
if (cmp < 0) {
return rank(key, x.left);
} else if (cmp > 0) {
return rank(key, x.right);
} 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.N = size(x.left) + size(x.right) + 1;
return x;
}
public Iterable<Key> keys() {
return keys(min(), max());
}
private Iterable<Key> keys(Key lo, Key hi) {
Queue<Key> queue = new Queue<Key>();
keys(root, queue, lo, hi);
return queue;
}
private void keys(Node x, Queue<Key> queue, Key lo, Key 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);
}
}
}
红黑二叉查找树
红黑二叉树找背后的基本思想是用标准的二叉查找树和(完全由2-结点构成)和一些额外的信息(替换3-结点)来表示2-3树。将树中的链接分为两种类型：红链接将两个2-结点连接起来构成一个3-结点，黑链接则是2-3树中的普通链接。
另一种定义：
1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
public class RedBlackBST<Key extends Comparable<Key>, Value> {
private Node root;
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node {
Key key;
Value value;
Node left, right;
int N;
boolean color;
public Node(Key key, Value value, int N, boolean color) {
this.key = key;
this.value = value;
this.color = color;
this.N = N;
}
private boolean isRed(Node h) {
if (h == null) {
return false;
}
return h.color == RED;
}
private Node rotateLeft(Node h) {
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
x.N = h.N;
h.N = 1 + size(h.left) + size(h.right);
return x;
}
private Node rotateRight(Node h) {
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = RED;
x.N = h.N;
h.N = 1 + size(h.left) + size(h.right);
return x;
}
private void filpColors(Node h) {
h.color = RED;
h.left.color = BLACK;
h.right.color = BLACK;
}
private int size(Node x) {
return x.N;
}
private Node put(Node h, Key key, Value value) {
if (h == null) {
return new Node(key, value, 1, RED);
}
int cmp = key.compareTo(h.key);
if (cmp < 0) {
h.left = put(h.left, key, value);
} else if (cmp > 0) {
h.right = put(h.right, key, value);
} else {
h.value = value;
}
if (isRed(h.right) && !isRed(h.left)) {
h = rotateLeft(h);
}
if (isRed(h.left) && isRed(h.left.left)) {
h = rotateRight(h);
}
if (isRed(h.left) && isRed(h.right)) {
filpColors(h);
}
h.N = size(h.left) + size(h.right) + 1;
return h;
}
}
}
散列表
基于拉链表的散列表
public class SeparateChainingHashST<Key, Value> {
private int N;
private int M;
private SequentialSearchST<Key, Value>[] st;
public SeparateChainingHashST() {
this(997);
}
public SeparateChainingHashST(int M) {
this.M = M;
st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
for(int i = 0; i < M; i++) {
st[i] = new SequentialSearchST();
}
}
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}
public Value get(Key key) {
return (Value)st[hash(key)].get(key);
}
public void put(Key key, Value value) {
st[hash(key)].put(key, value);
}
}
基于线性探测的符号表
public class LinearProbingHashST<Key, Value> {
private int N;
private int M = 16;
private Key[] keys;
private Value[] values;
public LinearProbingHashST() {
keys = (Key[]) new Object[M];
values = (Value[]) new Object[M];
}
private int hash(Key key) {
return (key.hashCode() & 0x7ffffff) % M;
}
public void resize() {
}
private void resize(int cap) {
LinearProbingHashST<Key, Value> t;
t = new LinearProbingHashST<Key, Value>();
for(int i = 0; i < M; i++) {
if (keys[i] != null) {
t.put(keys[i], values[i]);
}
keys = t.keys;
values = t.values;
M = t.M;
}
}
public void put(Key key, Value value) {
if (N > M / 2) {
resize(2 * M);
}
int i;
for(i = hash(key); keys[i] != null; i = (i + 1) % M) {
if (keys[i].equals(key)) {
values[i] = value;
return;
}
keys[i] = key;
values[i] = value;
N++;
}
}
public Value get(Key key) {
for(int i = hash(key); keys[i] != null; i = (i + 1) % M) {
if (keys[i].equals(key)) {
return values[i];
}
}
return null;
}
public void delete(Key key) {
if (!contains(key)) { return; }
int i = hash(key);
while(!key.equals(keys[i])) {
i = (i + 1) % N;
}
keys[i] = null;
values[i] = null;
i = (i + 1) % M;
while(keys[i] != null) {
Key keyToRedo = keys[i];
Value valueToRedo = values[i];
keys[i] = null;
values[i] = null;
N--;
put(keyToRedo, valueToRedo);
i = (i + 1) % N;
}
N--;
if (N > 0 && N == M / 8) {
resize(M / 2);
}
}
private boolean contains(Key key) {
for(int i = 0; i < M; i++) {
if (keys[i].equals(key)) {
return true;
}
}
return false;
}
}
