查找----基于红黑平衡树
红黑树中修复平衡需要用到旋转：
当连续出现两条红色左链接时，需要进行右旋转：
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);
}红黑树的性质：
- 一棵大小为N的红黑树的高度不会超过2lgN。
- 一颗大小为N的红黑树中，根节点到任意节点的平均路径长度为~lgN.
- 在一棵红黑树中，一下操作在最坏情况下所需操作都是对数级别的：get(), put(), min(), max(), floor(), ceiling(), rank(), select(), delete(), range().
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.12.16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录