数据结构08-红黑树
一、红黑树的介绍
红黑树(RBT)是每个节点都带有颜色属性的自平衡二叉查找树,颜色或红色或黑色。具备以下性质:
性质1:节点是红色或黑色;
性质2:根节点是黑色。
性质3:所有的NULL节点都为叶子节点,且颜色为空。
性质4:每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5:从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
由于AVL的树增删效率很低,所以出现了红黑树。红黑树的查找效率比一般的二叉查找树高,比AVL树低,但是增删效率比AVL树高,比一般的二叉查找树低。
红黑树的应用:TreeMap、TreeSet
二、红黑树的插入
红黑树的插入分为两步:添加、修正平衡。
这里把新增节点记作A,把A的父节点记作B,把找到的最小不平衡子树记作C。
1.添加
第一步的添加跟二叉搜索树的插入一样。
2.修正平衡
将当前节点记作A,将A的父节点记作B,将B的兄弟节点记作C,将B的父结点记作D。
修正过程如下:
- 将A设为红色,这样对整颗树的平衡影响较小;
- 如果A为根节点,则将根节点改成黑色即可,修正结束;
- 如果B是黑色,那么树就是平衡的,修正结束;
- 如果B是红色,并且B是D的左孩子,则判断C的颜色:
- 如果C是红色,则将B和C涂黑,D涂红,把当前节点(A)指向D,然后继续比较A;
- 如果C是黑色,并且A是B的左孩子,则把B涂黑,D涂红,然后对D右旋,然后继续比较A;
- 如果C是黑色,并且A是B的右孩子,则把当前节点(A)指向B,然后对新的A左旋。然后把B指向新A的父亲,把D指向新B的父亲,然后把B涂黑,D涂红,对D右旋,然后继续比较A。
- 如果B是红色,并且B是D的右孩子,则判断C的颜色:
- 如果C是红色,则将B和C涂黑,D涂红,把当前节点(A)指向D,然后继续比较A;
- 如果C是黑色,并且A是B的右孩子,则把B涂黑,D涂红,然后对D左旋,然后继续比较A;
- 如果C是黑色,并且A是B的左孩子,则把当前节点(A)指向B,然后对新的A右旋。然后把B指向新A的父亲,把D指向新B的父亲,然后把B涂黑,D涂红,对D左旋,然后继续比较A。
添加元素:
public void put(E data) {
Node<E> now = new Node<E>(data);
if (root == null) {
root = now;
return;
}
Node<E> parent = root;
// 像二叉查找树一样添加
while (parent != null) {
if (data.compareTo(parent.data) < 0) {
if (parent.left == null) {
parent.left = now;
now.parent = parent;
break;
} else {
parent = parent.left;
}
} else if (data.compareTo(parent.data) > 0) {
if (parent.right == null) {
parent.right = now;
now.parent = parent;
break;
} else {
parent = parent.right;
}
} else {
return;
}
}
//修正位置
fixAfterInsertion(now);
}
修正位置:
private void fixAfterInsertion(Node<E> node) {
node.color = RED;
Node<E> parent = null;
Node<E> brother = null;
while (node != null && node != root && node.parent.color == RED) {
parent = node.parent;
if (parent.parent != null && parent.parent.left == parent) {
brother = parent.parent.right;
if (getColor(brother) == RED) {
setColor(parent, BLACK);
setColor(brother, BLACK);
setColor(parent.parent, RED);
node = parent.parent;
} else {
if (parent.right == node) {
node = parent;
leftRoate(node);
}
parent = node.parent;
setColor(parent, BLACK);
setColor(parent.parent, RED);
rightRoate(parent.parent);
}
} else {
brother = parent.parent == null ? null : parent.parent.left;
if (getColor(brother) == RED) {
setColor(parent, BLACK);
setColor(brother, BLACK);
setColor(parent.parent, RED);
node = parent.parent;
} else {
if (parent.left == node) {
node = parent;
rightRoate(node);
}
parent = node.parent;
setColor(parent, BLACK);
setColor(parent.parent, RED);
leftRoate(parent.parent);
}
}
}
root.color = BLACK;
}
三、红黑树的删除
红黑树的插入分为两步:删除、修正平衡。
这里把需要修正的节点记作A,把A的父节点记作B,把找到的最小不平衡子树记作C。
1.删除
第一步的删除跟二叉搜索树的插入一样,只是要将被删除节点的替代节点当作需要修正的结点。
注意:如果被删结点是红色,那么不影响树的平衡,不需要修正;
2.修正平衡
将当前节点记作A,将A的父节点记作B,将A的兄弟节点记作C,将B的父结点记作D。
修正过程如下:
-
如果A为根节点,则将A设为黑色,修正结束;
-
如果A为红色,则将A设为黑色,修正结束;
-
如果A为B的左子节点,则
- 先判断C的颜色,如果C为红色,则将C设为黑色,将B设为红色,然后对B左旋,然后将B指向新A的父亲,将C指向新B的兄弟
- 然后判断C的左右子节点是否都为黑色,如果都为黑色,则将C设为红色,将A指向B,然后继续判断A;
- 如果C的右子节点是黑色,C的左子节点是红色或黑色,则先将C的左子节点设为黑色,将C设为红色,对B右旋,将B指向新A的父亲,将C指向新B的兄弟;然后将C设为B的颜色,将B设为黑色,将B的右子节点设为黑色,再将B左旋,将A指向root节点。
- 如果C的右子节点是红色,C的左子节点是红色或黑色,则将C设为B的颜色,将B设为黑色,将B的右子节点设为黑色,再将B左旋,将A指向root节点。
-
如果A为B的右子节点,则
- 先判断C的颜色,如果C为红色,则将C设为黑色,将B设为红色,然后对B右旋,然后将B指向新A的父亲,将C指向新B的兄弟
- 然后判断C的左右子节点是否都为黑色,如果都为黑色,则将C设为红色,将A指向B,然后继续判断A;
- 如果C的左子节点是黑色,C的右子节点是红色,则先将C的右子节点设为黑色,将C设为红色,对B左旋,将B指向新A的父亲,将C指向新B的兄弟;然后将C设为B的颜色,将B设为黑色,将B的左子节点设为黑色,再将B右旋,将A指向root节点。
- 如果C的左子节点是红色,C的右子节点是红色或黑色,则将C设为B的颜色,将B设为黑色,将B的左子节点设为黑色,再将B右旋,将A指向root节点。
删除:
public Node<E> remove(E data) {
Node<E> now = get(data);
if (now == null) {
throw new NoSuchElementException();
}
Node<E> p = get(data);
if (p == null) {
throw new NoSuchElementException();
}
//p的右子树的最左子节点r
Node<E> r = nodeLeft(p.right);
//p的左子树的最右子节点l
Node<E> l = nodeRight(p.left);
if (r != null) {
p.data = r.data;
//如果p的右子结点有左节点
if (r != p.right) {
r.parent.left = r.right;
} else {
p.right = p.right.right;
}
//如果被删节点是黑色,就对替换的节点进行修正,即从平衡破坏的地方开始向上修正
if (now.color == BLACK) {
fixAfterDelete(r.right);
}
r.left = r.right = r.parent = null;
} else if (l != null) {
p.data = l.data;
//如果p的左子结点有右节点
if (l != p.left) {
l.parent.right = l.left;
} else {
p.left = p.left.left;
}
//如果被删节点是黑色,就对替换的节点进行修正,即从平衡破坏的地方开始向上修正
if (now.color == BLACK) {
fixAfterDelete(l.left);
}
l.left = l.right = l.parent = null;
//如果p是叶子节点
} else {
//如果p是叶子节点,但不是根节点,且颜色为黑色就需要对其修正
if (p.parent != null && p.color == BLACK) {
fixAfterDelete(p);
}
if (p.parent == null) {
root = null;
} else if (p.parent.left == p) {
p.parent.left = null;
} else {
p.parent.right = null;
}
p.parent = null;
}
return now;
}
修正位置:
private void fixAfterDelete(Node<E> node) {
if (node == null) {
return;
}
Node<E> parent = null;
Node<E> brother = null;
while (node != root && getColor(node) == BLACK) {
parent = node.parent;
if (node == parent.left) {
brother = parent.right;
if (getColor(brother) == RED) {
setColor(brother, BLACK);
setColor(parent, RED);
leftRoate(parent);
parent = node.parent;
brother = parent.right;
}
if (getColor(brother.left) == BLACK && getColor(brother.right) == BLACK) {
setColor(brother, RED);
node = node.parent;
} else {
if (getColor(brother.right) == BLACK) {
setColor(brother.left, BLACK);
setColor(brother, RED);
rightRoate(brother);
parent = node.parent;
brother = parent.right;
}
setColor(brother, getColor(parent));
setColor(parent, BLACK);
setColor(brother.right, BLACK);
leftRoate(parent);
node = root;
}
} else { // symmetric
brother = parent.left;
if (getColor(brother) == RED) {
setColor(brother, BLACK);
setColor(parent, RED);
rightRoate(parent);
parent = node.parent;
brother = parent.left;
}
if (getColor(brother.left) == BLACK && getColor(brother.right) == BLACK) {
setColor(brother, RED);
node = node.parent;
} else {
if (getColor(brother.left) == BLACK) {
setColor(brother.right, BLACK);
setColor(brother, RED);
leftRoate(brother);
parent = node.parent;
brother = parent.left;
}
setColor(brother, getColor(parent));
setColor(parent, BLACK);
setColor(brother.left, BLACK);
rightRoate(parent);
node = root;
}
}
}
setColor(node, BLACK);
}
最后
数据结构与算法专题:https://www.jianshu.com/nb/25128590
喜欢请点赞,谢谢!
网友评论