db.jpg
概念:
红黑树或者是一颗空树,或者是一颗具有以下性质的二叉查找树.
- 结点非红即黑.
- 根结点为黑.
- 所有的NULL为叶子结点,且认为颜色为黑
- 所有红结点的子结点为黑
- 任一结点到其叶子结点的所有路径,经过的黑结点数量相同
-
任意一个结点,他的左右子树层次不超过一倍.
image.png
结点插入:
先按照二叉排序树的方式插入一个节点(红色).
插入的是黑结点>直接将结点涂黑.
插入结点的父节点是黑色>不违背任何性质,不用调整.
-
插入结点的父结点是红色>
4.1 父结点是祖父结点的左孩子
4.1.1 祖父节点的另一个子结点(叔叔结点)是红色>
将当前节点的父结点和叔叔结点涂黑,祖父结点涂红,将当前节点指定为祖父结点,从新的当前节点开始算法.
image.png
4.1.2 叔叔结点是黑色>
4.1.2.1 当前节点是其父结点的右孩子>当前节点的父结点作为新的当前节点,以新的当前节点为支点进行左旋
image.png
4.1.2.2 当前节点是其父结点的左孩子>父结点变为黑色,祖父结点变为红色,再以祖父结点为支点进行右旋
image.png4.2 父结点是祖父结点右孩子>和上面一样,只是把左全部换成右.
image.png
删除结点
先进行二叉排序树的删除操作,然后将替换结点作为新的当前节点进行后面的平衡操作.
当前节点是红色>直接把当前节点染黑,结束.
-
当前节点是黑色>
2.1 被删除节点是父结点的左孩子>
2.1.1 当前节点是根结点>什么都不做
2.1.2 当前节点X的兄弟结点是红色(此时,父结点和兄弟节点的子结点为黑)>把父结点染红,兄弟节点染黑,以父结点为支点进行左旋,重新设置X的兄弟节点.
image.png
2.1.3 当前节点X的兄弟节点是黑色>
2.1.3.1 兄弟节点的两个孩子都为黑色>将当前节点的兄弟节点染黑,父结点染红,然后以父结点作为新的当前节点,从新开始算法.
image.png
2.1.3.2 兄弟的右孩子是黑色,左孩子是红色>将X兄弟节点的左孩子置黑,将X节点的兄弟节点置红,将X节点的兄弟节点进行右旋,然后重置x节点的兄弟节点.
image.png
2.1.3.3 兄弟节点的右孩子是红色>兄弟节点染成当前节点父结点的颜色,兄弟节点的右孩子染成黑色,父结点染成黑色,以当前节点的父结点为支点,进行左旋,算法结束.
image.png2.2 被删除节点是父结点的右孩子>把上边的左置为右
代码
红黑树的插入删除规则就讲完了,是有点复杂,但其实不难.
那么,我们来看看红黑树的代码吧,jdk1.8之后,为了适用大数据时代,很多数据结构都用到了红黑树
比如:HashTable,TreeSet,TreeMap
我们以TreeMap为例,来看看红黑树的源码,对照上面的插入规则和删除规则来一步步看
- TreeMap插入操作
public V put(K key, V value) {
TreeMapEntry<K,V> t = root;
if (t == null) {//根结点为空
// BEGIN Android-changed: Work around buggy comparators. http://b/34084348
// We could just call compare(key, key) for its side effect of checking the type and
// nullness of the input key. However, several applications seem to have written comparators
// that only expect to be called on elements that aren't equal to each other (after
// making assumptions about the domain of the map). Clearly, such comparators are bogus
// because get() would never work, but TreeSets are frequently used for sorting a set
// of distinct elements.
//
// As a temporary work around, we perform the null & instanceof checks by hand so that
// we can guarantee that elements are never compared against themselves.
//
// **** THIS CHANGE WILL BE REVERTED IN A FUTURE ANDROID RELEASE ****
//
// Upstream code was:
// compare(key, key); // type (and possibly null) check
if (comparator != null) {//这个comparator表示传进来的比较器
if (key == null) {
comparator.compare(key, key);
}
} else {
if (key == null) {
throw new NullPointerException("key == null");
} else if (!(key instanceof Comparable)) {
throw new ClassCastException(
"Cannot cast" + key.getClass().getName() + " to Comparable.");
}
}
// END Android-changed: Work around buggy comparators. http://b/34084348
root = new TreeMapEntry<>(key, value, null);//插入结点作为根结点
size = 1;
modCount++;//表示TreeMap被修改一次
return null;
}
int cmp;
TreeMapEntry<K,V> parent;
// split comparator and comparable paths
//这里是确认插入结点的位置,分为comparator为空和不为空两种情况
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
//插入节点,平衡操作
TreeMapEntry<K,V> e = new TreeMapEntry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
/** From CLR */
private void fixAfterInsertion(TreeMapEntry<K,V> x) {
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {//4
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {//4.1
TreeMapEntry<K,V> y = rightOf(parentOf(parentOf(x)));//x的叔叔结点y
if (colorOf(y) == RED) {//4.1.1
setColor(parentOf(x), BLACK);//父结点置黑
setColor(y, BLACK);//叔叔结点置黑
setColor(parentOf(parentOf(x)), RED);//祖父结点置红
x = parentOf(parentOf(x));//祖父结点作为当前节点
} else {//4.1.2
if (x == rightOf(parentOf(x))) {//4.1.2.1
x = parentOf(x);
rotateLeft(x);
}
//4.1.2.2
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {//4.2
TreeMapEntry<K,V> 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;//2
}
- TreeMap删除操作
/**
* Delete node p, and then rebalance the tree.
*/
private void deleteEntry(TreeMapEntry<K,V> p) {
modCount++;
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
if (p.left != null && p.right != null) {
TreeMapEntry<K,V> s = successor(p);//找到替换结点,并替换
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
TreeMapEntry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// Link replacement to parent
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null;
// Fix replacement
if (p.color == BLACK)//2
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else { // No children. Use self as phantom replacement and unlink.
if (p.color == BLACK)//2
fixAfterDeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
/** From CLR */
private void fixAfterDeletion(TreeMapEntry<K,V> x) {
while (x != root && colorOf(x) == BLACK) {//2
if (x == leftOf(parentOf(x))) {//2.1
TreeMapEntry<K,V> sib = rightOf(parentOf(x));//sib,当前节点的兄弟结点
if (colorOf(sib) == RED) {//2.1.2
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {//2.1.3.1
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(rightOf(sib)) == BLACK) {//2.1.3.2
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
//2.1.3.3
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // symmetric
//2.2
TreeMapEntry<K,V> 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);//1
}
/**
* Returns the successor of the specified Entry, or null if no such.
*/
static <K,V> TreeMapEntry<K,V> successor(TreeMapEntry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {//右子树不为空时,得到删除结点右子树的左子树中最小的结点,替换被删除的结点
TreeMapEntry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {//右子树为空,从当前节点一直右上找,找到头
TreeMapEntry<K,V> p = t.parent;
TreeMapEntry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
ok,红黑树就介绍到这里了,如果对这些树感兴趣呢,其实在计算科学中还有很多有趣的树
比如:
image.png
大家感兴趣可以自行去学习下.
日拱一卒,贵在坚持.
