红黑树中修复平衡需要用到旋转:
当连续出现两条红色左链接时,需要进行右旋转:
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;
}
当出现一条红色右链接时,需要进行左旋转:
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(right);
return x;
}
查询操作完全同与二叉查找树的操作。
新插入的节点都是用的红色链接。所以向红黑平衡树中插入一个新节点时,可能出现需要进行旋转的情况。这时候需要从底向上旋转修正颜色。
只要谨慎地使用左旋转、右旋转和颜色转换,就能保持红黑树的平衡。在沿着插入点到根节点的过程中顺序完成以下操作:
根节点总是黑色。严格的说,红色的根节点说明根节点是一个3-节点的一部分,这和实际情况不符,所以我们在每次插入之后都会将根节点设置为黑色。注意,根节点每次由红变黑树的黑色链接高度会加一。
插入实现:
public void put(Key key, Value val) {
if (key == null) throw new IllegalArgumentException("first argument to put() is null");
if (val == null) {
delete(key);
return;
}
root = put(root, key, val);
root.color = BLACK;
}
private Node put(Node h, Key key, Value val) {
if (h == null) return new Node(key, val, RED, 1);
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.size = size(h.left) + size(h.right) + 1;
return h;
}
如果被查找的键在树底部,可以直接删除它。如果不在,则将它替换为它的后继节点,然后将后继节点删除,这样问题就转化为在一棵根节点不是2-节点的子树中删除最小的键的问题。删除之后需要向前回溯调整平衡。
public void delete(Key key) {
if (key == null) throw new IllegalArgumentException("argument to delete() is null");
if (!contains(key)) return;
// if both children of root are black, set root to red
if (!isRed(root.left) && !isRed(root.right))
root.color = RED;
root = delete(root, key);
if (!isEmpty()) root.color = BLACK;
}
// delete the key-value pair with the given key rooted at h
private Node delete(Node h, Key key) {
if (key.compareTo(h.key) < 0) {
if (!isRed(h.left) && !isRed(h.left.left))
h = moveRedLeft(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) {
Node x = min(h.right);
h.key = x.key;
h.val = x.val;
h.right = deleteMin(h.right);
}
else h.right = delete(h.right, key);
}
return balance(h);
}
红黑树的性质: