红黑树也是一种自平衡的二叉搜索树，以前也叫做平衡二叉B树
红黑树必须满足以下5条性质
- 节点是红色或者是黑色
- 根节点是黑色
- 叶子节点（外部节点、空节点）都是黑色
- 红色节点的子节点都是黑色
- 红色节点的父节点都是黑色
- 从根节点到叶子节点的所有路径上不能有2个连续的红色节点
- 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点
请问下面树是红黑树吗？
Snip20200902_29.png
不是红黑树，红黑树要求从任一节点到叶子节点的所有路径都包含相同数目的黑色节点 ，上图从节点38到叶子节点有两条路径，包含的黑色节点分别为2和1，不相同
红黑树的等价变换
- 红黑树和4阶B树（2-3-4树）具有等价性（注意：网上有些教程，用2-3树与红黑树进行类比，这是及其不严谨的，2-3树并不能完美匹配红黑树的所有情况）
-
黑色节点与它的红色子节点融合在一起，形成1个B树节点
Snip20200902_28.png
添加
-
如下图，为了方便理解，我们将红黑树以B树的形式进行展示，向红黑树中添加元素，分为4种情况
- 新添加的元素是根节点
- 新添加的元素的父节点是黑色节点，如添加到46的左侧、76的右侧、88的左侧或者右侧
- 新添加的元素的父节点是红色节点，并且叔父节点（父节点的兄弟节点）不是红色节点
- 新添加的元素的父节点是红色节点，并且叔父节点（父节点的兄弟节点）也是红色节点
-
已知，在B树中，新元素必定是添加到叶子节点中，而且4阶B树所有节点元素的个数x都符合1<=x<=3。
-
建议新添加的节点默认为红色，这样能够让红黑树的性质尽快满足（性质1、2、3、4都满足，性质4不一定）
Snip20200902_30.png
情况1
如果添加的是根节点，染成黑色即可。
判定条件：parent 等于 null
情况2
如果新添加的元素的父节点是黑色节点，不需要额外处理
判定条件：parent为黑色节点
情况3
如果新添加的元素的父节点是红色节点，并且叔父节点不是红色节点，这种情况如果将红黑树转成B树，父节点有父节点元素和祖父及节点元素两个元
素，必然不会出现B树节点上溢的情况。
判定条件：parent为红色节点，并且叔父节点不是红色节点
-
LL/RR
- 父节点染成黑色，祖父节点染成红色
-
祖父节点进行单旋，如果是LL，祖父节点右旋转；如果是RR，祖父节点左旋转；
Snip20200903_33.png
-
LR/RL
- 自己染成黑色，祖父节点染成红色
-
进行双旋操作，如果是LR，父节点左旋，祖父节点右旋；如果是RL，父节点右旋转，祖父节点左旋转
Snip20200903_34.png
情况4
如果新添加的元素的父节点是红色节点，并且叔父节点（父节点的兄弟节点）也是红色节点，这种情况如果将红黑树转成B树，父节点有父节点元素、祖父节点元素和叔父节点元素三个元素，必然会导致B树节点上溢
判定条件：父节点是红色节点，并且叔父节点也是红色节点
- 将父节点和叔父节点染成黑色
- 祖父节点染成红色，向上合并，当做是新添加的节点进行处理
-
祖父节点向上合并时，可能继续发生上溢，若上溢持续到根节点，只需要将根节点染成黑色
Snip20200903_36.png
删除
已知，在B树中，最后真正被删除的元素都在叶子节点中
删除红黑树中的元素，分为以下三种情况：
- 删除的是红色节点，如节点50、节点72
- 删除拥有一个红色子节点的黑色节点（不可能直接删除拥有两个子节点的黑色节点，因为它是度为2的节点），如节点46、节点76
- 删除黑色叶子节点
情况1
删除的是红色节点，直接删除即可
判定条件：node为红色节点
情况2
删除拥有一个红色子节点的黑色节点
判定条件：用以替代的子节点是红色
操作：将替代的子节点染成黑色即可
Snip20200903_39.png
情况3
删除的是黑色叶子节点，黑色叶子节点被删除后，会导致B树节点下溢
3.1 被删除的黑色节点是根节点
直接删除即可
3.2 兄弟节点是黑色节点，并且至少有一个红色子节点
判定条件：sibling是黑色节点 && sibling的左子节点或者右子节点是红色节点
操作：进行旋转操作，旋转之后中心节点继承parent的颜色，旋转之后的左右节点染成黑色
Snip20200903_40.png
3.3 兄弟节点是黑色节点，并且没有一个红色子节点
判定条件：sibling是黑色节点 && sibling的左子节点和右子节点都不是红色节点
操作：将兄弟节点染成红色，父节点染成黑色
注意：如果父节点是黑色节点，会导致父节点下溢，这时需要把parent当作被删除的节点处理即可
Snip20200903_41.png
3.4 兄弟节点是红色节点
判定条件：sibling是红色节点
操作：兄弟节点染成黑色，父节点染成红色，进行旋转，于是又回到了兄弟节点是黑色节点的情况
Snip20200903_42.png
添加/删除代码(java)
package RBTree;
import java.util.Comparator;
public class LZRBTree<E> extends LZBST<E>{
private static final boolean RED = false;
private static final boolean BLACK = true;
public LZRBTree(){
this(null);
}
public LZRBTree(Comparator<E> comparator){
super(comparator);
}
@Override
protected void afterAdd(Node<E> node) {
//判断情况1，是否是根节点
if (node.parent == null) {
black(node);
return;
}
//判断情况2，父节点是否是黑色
if(isBlack(node.parent)) return;
//判断情况4，叔父节点是否是红色，如果是红色，不需要旋转，B树节点溢出
if (isRed(node.parent.sibling())){
black(node.parent);
black(node.parent.sibling());
Node<E> parent = red(node.parent.parent);
afterAdd(parent);
return;
}
//符合情况3，旋转，B树节点不会溢出
Node<E> parent = node.parent;
Node<E> grand = red(parent.parent); //将祖父节点染成红色
if (parent.isLeftChild()){ //L
if (node.isLeftChild()){ //LL
black(parent);
}else { //LR
black(node);
rotateLeft(parent);
}
rotateRight(grand);
}else { //R
if (node.isLeftChild()){ //RL
black(node);
rotateRight(parent);
}else { //RR
black(parent);
}
rotateLeft(grand);
}
}
@Override
protected void afterRemove(Node<E> node,Node<E> replaceNode) {
//如果符合情况1，被删除节点是红色节点，那么直接删除即可
if (isRed(node)) return;
//如果符合情况2，被删除节点的替代节点是红色节点，那么将替代节点染成黑色即可
if (isRed(replaceNode)){
black(replaceNode);
return;
}
//符合情况三，被删除节点是黑色叶子节点
Node<E> parent = node.parent;
//3.1 被删除节点是根节点，那么直接删除即可
if (parent == null) return;
// 判断被删除的node是左还是右
boolean left = parent.left == null || node.isLeftChild();
Node<E> sibling = left ? parent.right : parent.left;
// 黑色叶子节点被删除后，会导致B树节点下溢
if (left){ //被删除的节点在左边，兄弟节点在右边
// 3.2 兄弟节点是红色
// 染色：兄弟节点染成黑色，父节点染成红色
// 旋转：父节点左旋，让兄弟节点的左子节点成为兄弟节点，让原来的兄弟节点成为祖父节点
if (isRed(sibling)){
black(sibling);
red(parent);
rotateLeft(parent);
//更换兄弟节点
sibling = parent.right;
}
// 兄弟节点必然是黑色，
// 3.3 如果兄弟节点至少有一个红色子节点，可以向兄弟节点借一个
if (isRed(sibling.left) || isRed(sibling.right)){
// 兄弟节点的左侧是红色子节点，
// 符合RL的情况，让兄弟节点先左旋，使红色子节点成为新的兄弟节点
if (isBlack(sibling.right)){
rotateLeft(sibling);
sibling = parent.right;
}
//染色
color(sibling,colorOf(parent));
black(parent);
black(sibling.right);
//父节点右旋
rotateLeft(parent);
}else{
// 3.4 兄弟节点没有一个红色子节点，父节点向下合并
boolean parentBlack = isBlack(parent);
red(sibling);
black(parent);
//如果parent是黑色节点，会导致parent也下溢
if (parentBlack){
afterRemove(parent,null);
}
}
}else { //被删除的节点在右边，兄弟节点在左边
// 3.2 兄弟节点是红色
// 染色：兄弟节点染成黑色，父节点染成红色
// 旋转：父节点右旋，让兄弟节点的右子节点成为兄弟节点，让原来的兄弟节点成为祖父节点
if (isRed(sibling)){
black(sibling);
red(parent);
rotateRight(parent);
//更换兄弟节点
sibling = parent.left;
}
// 兄弟节点必然是黑色，
// 3.3 如果兄弟节点至少有一个红色子节点，可以向兄弟节点借一个
if (isRed(sibling.left) || isRed(sibling.right)){
// 兄弟节点的右侧是红色子节点，
// 符合LR的情况，让兄弟节点先左旋，使红色子节点成为新的兄弟节点
if (isBlack(sibling.left)){
rotateLeft(sibling);
sibling = parent.left;
}
//染色
color(sibling,colorOf(parent));
black(parent);
black(sibling.left);
//父节点右旋
rotateRight(parent);
}else{
// 3.4 兄弟节点没有一个红色子节点，父节点向下合并
boolean parentBlack = isBlack(parent);
red(sibling);
black(parent);
//如果parent是黑色节点，会导致parent也下溢
if (parentBlack){
afterRemove(parent,null);
}
}
}
}
//左旋
private void rotateLeft(Node<E> grand){
Node<E> parent = grand.right;
Node<E> child = parent.left;
grand.right = child;
parent.left = grand;
afterRote(grand,parent,child);
}
//右旋
private void rotateRight(Node<E> grand){
Node<E> parent = grand.left;
Node<E> child = parent.right;
grand.left = child;
parent.right = grand;
afterRote(grand,parent,child);
}
private void afterRote(Node<E> grand,Node<E> parent,Node<E> child){
// 更新parent的父节点
parent.parent = grand.parent;
if (grand.isLeftChild()){
grand.parent.left = parent;
}else if(grand.isRightChild()){
grand.parent.right = parent;
}else {
root = parent;
}
//更新child
if (child != null){
child.parent = grand;
}
//更新grand的父节点
grand.parent = parent;
}
/**
* 将节点染色
* @param node
* @param color
* @return 染色后的节点
*/
private Node<E> color(Node<E> node,boolean color){
if (node == null) return node;
((RBNode<E>)node).color = color;
return node;
}
/**
* 将节点染成红色
* @param node
* @return
*/
private Node<E> red(Node<E> node){
return color(node,RED);
}
/**
* 将节点染成黑色
* @param node
* @return
*/
private Node<E> black(Node<E> node){
return color(node,BLACK);
}
/**
* 返回节点的颜色
* @param node
* @return
*/
private boolean colorOf(Node<E> node){
return node == null ? BLACK: ((RBNode<E>)node).color;
}
/**
* 判断节点是否是黑色节点
* @param node
* @return
*/
private boolean isBlack(Node<E> node){
return colorOf(node) == BLACK;
}
/**
* 判断节点是否是红色节点
* @param node
* @return
*/
private boolean isRed(Node<E> node){
return colorOf(node) == RED;
}
@Override
protected Node createNode(Object element, Node parent) {
return new RBNode<>(element,parent);
}
private static class RBNode<E> extends Node<E>{
boolean color = RED;
public RBNode(E element,Node<E> parent){
super(element,parent);
}
@Override
public String toString() {
String str = "";
if (color == RED){
str = "R_";
}
return str + element.toString();
}
}
}
红黑树的平衡
-
红黑树的5条性质，可以保证红黑树等价于4阶B树，B树非常平衡
-
红黑树的平衡标准：没有一条路径会大于其他路径的2倍，因此红黑树的平衡是一种若平衡、黑高度平衡
-
红黑树的最大高度：2*log2(n+1)，依然是O(logn)级别
红黑树的平均时间复杂度
- 搜索：O(logn)
- 添加：O(logn)，O(1)次的旋转操作
- 删除：O(logn)，O(1)次的旋转操作
网友评论