/**
* 红黑树
*
* 部分代码参考自TreeMap源码
*/
public class RedBlackTree<T> {
protected TreeNode<T> root = null;
private final Comparator<? super T> comparator;
private int size = 0;
private static final boolean RED = false;
private static final boolean BLACK = true;
public RedBlackTree() {
this.comparator = null;
}
public RedBlackTree(Comparator<? super T> comparator) {
this.comparator = comparator;
}
public void insert(T key) {
TreeNode<T> x = root;
TreeNode<T> y = null;
TreeNode<T> z = new TreeNode<T>(key, null);
int cmp;
if (x == null) {
root = z;
size = 1;
return;
}
while (x != null) {
y = x;
cmp = compareKey(z.key, x.key);
if (cmp < 0)
x = x.left;
else
x = x.right;
}
z.parent = y;
cmp = compareKey(z.key, y.key);
if (cmp < 0)
y.left = z;
else
y.right = z;
z.left = z.right = null;
fixAfterInsertion(z);
size++;
}
public T remove(T key) {
TreeNode<T> p = find(key);
if (p == null)
return null;
T oldValue = p.key;
deleteNode(p);
return oldValue;
}
public boolean isEmpty() {
return size() == 0;
}
public int size() {
return size;
}
public TreeNode<T> firstNode() {
return getFirstNode(root);
}
public TreeNode<T> lastNode() {
return getLastNode(root);
}
public TreeNode<T> find(T t) {
TreeNode<T> p = root;
while (p != null) {
int cmp = compareKey(t, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
public Set<TreeNode<T>> nodeSet() {
return new NodeSet();
}
public static final class TreeNode<T> {
T key;
TreeNode<T> left = null;
TreeNode<T> right = null;
TreeNode<T> parent;
boolean color = BLACK;
TreeNode(T key, TreeNode<T> parent) {
this.key = key;
this.parent = parent;
}
public T getKey() {
return key;
}
public boolean equals(Object o) {
if (!(o instanceof TreeNode))
return false;
TreeNode<?> e = (TreeNode<?>) o;
return keyEquals(key, e.getKey());
}
public String toString() {
return "[" + key + " : " + (color ? "BLACK" : "RED") + "]";
}
}
private static <T> TreeNode<T> successor(TreeNode<T> t) {
if (t == null)
return t;
else if (t.right != null)
return getFirstNode(t.right);
else {
TreeNode<T> p = t.parent;
TreeNode<T> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
private static <T> TreeNode<T> predecessor(TreeNode<T> t) {
if (t == null)
return t;
else if (t.left != null)
return getLastNode(t.left);
else {
TreeNode<T> p = t.parent;
TreeNode<T> ch = t;
while (p != null && ch == p.left) {
ch = p;
p = p.parent;
}
return p;
}
}
private static <T> TreeNode<T> getFirstNode(TreeNode<T> t) {
TreeNode<T> p = t;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
private static <T> TreeNode<T> getLastNode(TreeNode<T> t) {
TreeNode<T> p = t;
if (p != null)
while (p.right != null)
p = p.right;
return p;
}
private static boolean keyEquals(Object o1, Object o2) {
return (o1 == null ? o2 == null : o1.equals(o2));
}
private int compareKey(T key1, T key2) {
int cmp;
if (comparator != null)
cmp = comparator.compare(key1, key2);
else {
if (key1 == null || key2 == null)
throw new NullPointerException();
Comparable<? super T> k = (Comparable<? super T>) key1;
cmp = k.compareTo(key2);
}
return cmp;
}
private void rotateLeft(TreeNode<T> p) {
if (p != null) {
TreeNode<T> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}
private void rotateRight(TreeNode<T> p) {
if (p != null) {
TreeNode<T> l = p.left;
p.left = l.right;
if (l.right != null)
l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else
p.parent.left = l;
l.right = p;
p.parent = l;
}
}
private void fixAfterInsertion(TreeNode<T> x) {
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
TreeNode<T> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
TreeNode<T> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
private void deleteNode(TreeNode<T> p) {
size--;
TreeNode<T> y = p;
TreeNode<T> x;
boolean y_original_color = colorOf(y);
if (leftOf(p) == null) {
x = rightOf(p);
transplant(p, rightOf(p));
} else if (rightOf(p) == null) {
x = leftOf(p);
transplant(p, leftOf(p));
} else {
y = getFirstNode(rightOf(p));
y_original_color = colorOf(y);
x = rightOf(y);
if (parentOf(y) == p)
x.parent = y;
else {
transplant(y, rightOf(y));
y.right = rightOf(p);
y.right.parent = y;
}
transplant(p, y);
y.left = leftOf(p);
y.left.parent = y;
y.color = colorOf(p);
}
if (y_original_color == BLACK)
fixAfterDeletion(x);
}
private void fixAfterDeletion(TreeNode<T> x) {
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
TreeNode<T> sib = rightOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK
&& colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // symmetric
TreeNode<T> sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK
&& colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
private void transplant(TreeNode<T> u, TreeNode<T> v) {
if (parentOf(u) == null)
root = v;
else if (u == leftOf(parentOf(u)))
u.parent.left = v;
else
u.parent.right = v;
if (v != null)
v.parent = u.parent;
}
/**
* 树的平衡操作
*
* 树的实现没有使用哨兵元素，而是使用下列方法处理null的情况
*/
private static <T> boolean colorOf(TreeNode<T> p) {
return (p == null ? BLACK : p.color);
}
private static <T> TreeNode<T> parentOf(TreeNode<T> p) {
return (p == null ? null : p.parent);
}
private static <T> void setColor(TreeNode<T> p, boolean c) {
if (p != null)
p.color = c;
}
private static <T> TreeNode<T> leftOf(TreeNode<T> p) {
return (p == null) ? null : p.left;
}
private static <T> TreeNode<T> rightOf(TreeNode<T> p) {
return (p == null) ? null : p.right;
}
final class NodeSet extends AbstractSet<TreeNode<T>> {
public Iterator<TreeNode<T>> iterator() {
return new NodeIterator(firstNode());
}
public int size() {
return RedBlackTree.this.size();
}
}
/**
* 红黑树的迭代器
*/
final class NodeIterator extends PrivateNodeIterator<TreeNode<T>> {
NodeIterator(TreeNode<T> first) {
super(first);
}
public TreeNode<T> next() {
return nextNode();
}
public void remove() {
}
}
abstract class PrivateNodeIterator<E> implements Iterator<E> {
TreeNode<T> next;
PrivateNodeIterator(TreeNode<T> first) {
next = first;
}
public boolean hasNext() {
return next != null;
}
final TreeNode<T> nextNode() {
TreeNode<T> e = next;
if (e == null)
throw new NoSuchElementException();
next = successor(e);
return e;
}
}
}