书上的文字描述是这样的：
在沿着左链接向下的过程中，保证以下情况之一成立：
1、如果当前节点的左子节点不是2-节点，完成；
2、如果当前节点的左子节点时2-节点，而他的亲兄弟节点不是2-节点，将左子节点的兄弟节点中的一个键移动到左子节点中；
3、如果当前节点的左子节点和它的亲兄弟节点都是2-节点，将左子节点，父亲节点中的最小键和左子节点最近的兄弟节点合并一个4-节点。
这样的话删除后仍可以保持红黑树的状态。上面这段话我是看懂了，但是放到代码里就不知道哪里有对应上面这段话中的操作，代码如下：
代码我贴了红黑树的全部API,只要看删除最小键那就好了。
package unit3_3;
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 val;
Node left, right;
int N;
boolean color;
Node(Key key, Value val, int N, boolean color) {
this.key = key;
this.val = val;
this.N = N;
this.color = color;
}
}
private boolean isRed(Node x) {
if (x == null)
return false;
return x.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;
x.N = h.N;
h.N = 1 + size(h.left) + size(h.right);
return x;
}
// 改变颜色
void flipColors(Node h) {
h.color = !h.color;
h.left.color = !h.left.color;
h.right.color = !h.right.color;
}
public int size() {
return size(root);
}
private int size(Node x) {
if (x == null) {
return 0;
} else
return x.N;
}
public void put(Key key, Value val) {
root = put(root, key, val);
root.color = BLACK;
}
public Node put(Node h, Key key, Value val) {
if (h == null)
return new Node(key, val, 1, RED);
int cmp = key.compareTo(h.key);
if (cmp < 0)
h.left = put(h.left, key, val);
else if (cmp > 0)
h.right = put(h.right, key, val);
else
h.val = val;
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))
flipColors(h);
h.N = size(h.left) + size(h.right) + 1;
return h;
}
public boolean isEmpty() {
return size() == 0;
}
private Node balance(Node h) {
if (isRed(h.right))
h = rotateLeft(h);
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))
flipColors(h);
h.N = size(h.left) + size(h.right) + 1;
return h;
}
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.val;
}
// 求最小值
public Key min() {
return min(root).key;
}
private Node min(Node x) {
if (x.left == null)
return x;
return min(x.left);
}
// 删除最小键
private Node removeRedLeft(Node h) {
flipColors(h);
if (isRed(h.right.left)) {
h.right = rotateRight(h.right);
h = rotateLeft(h);
}
return h;
}
public void deleteMin() {
if (!isRed(root.left) && !isRed(root.right))
root.color = RED;
root = deleteMin(root);
if (!isEmpty())
root.color = BLACK;
}
private Node deleteMin(Node h) {
if (h.left == null)
return null;
if (!isRed(h.left) && !isRed(h.left.left))
h = removeRedLeft(h.left);
h.left = deleteMin(h.left);
return balance(h);
}
// 删除最大键
private Node moveRedRight(Node h) {
flipColors(h);
if (!isRed(h.left.left))
h = rotateRight(h);
return h;
}
public void deleteMax() {
if (!isRed(root.left) && !isRed(root.right))
root.color = RED;
root = deleteMax(root);
if (!isEmpty())
root.color = BLACK;
}
private Node deleteMax(Node h) {
if (isRed(h.left))
h = rotateRight(h);
if (h.right == null)
return null;
if (!isRed(h.right) && !isRed(h.right.left))
h = moveRedRight(h);
h.right = deleteMax(h.right);
return balance(h);
}
// 删除任意键
public void delete(Key key) {
if (!isRed(root.left) && !isRed(root.right))
root.color = RED;
root = delete(root, key);
if (!isEmpty())
root.color = BLACK;
}
private Node delete(Node h, Key key) {
if (key.compareTo(h.key) < 0) {
if (!isRed(h.left) && !isRed(h.left.left))
h = removeRedLeft(h);
h.left = delete(h.left, key);
} else {
if (isRed(h.left))
h = rotateRight(h);
if (key.compareTo(h.key) == 0 && (h.right == null))
return null;
if (!isRed(h.right) && !isRed(h.right.left))
h = moveRedRight(h);
if (key.compareTo(h.key) == 0) {
h.val = get(h.right, min(h.right).key);
h.key = min(h.right).key;
h.right = deleteMin(h.right);
} else
h.right = delete(h.right, key);
}
return balance(h);
}
}sunbohan00
相关分类