红黑树简介
红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。
-----百度百科
红黑树的性质
- 每个节点或者是黑色,或者是红色
- 根节点是黑色
- 每个红色节点的两个子节点都是黑色
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
红黑树的应用
红黑树的应用比较广泛,主要是用它来存储有序的数据,它的时间复杂度是O(lgn),效率非常之高。例如,Java集合中的TreeSet和TreeMap,C++ STL中的set、map,以及Linux虚拟内存的管理,都是通过红黑树去实现的。
在讨论红黑树的新增和删除的两个主要操作之前,相信你已经对平衡二叉树的概念和操作以及对树的左旋、右旋操作,以及寻找树的前驱节点或后继节点操作有所了解或已熟悉,这些操作在实现红黑树的新增和删除操作中会频繁用到。如果还不熟悉请参考之前写过的文章-手撕红黑树1,在本文中不做过多介绍。
插入节点操作
插入操作包括两部分内容:1.寻找插入位置。2.插入节点后如不满足红黑树性质还需要进行自平衡。
红黑树的寻找插入位置的过程和普通二叉查找树的寻找过程是一样的。比当前节点大就向右子树寻找,比当前节点小就向左子树寻找,直到到达叶子节点为止。那么这这时就已经找到了插入节点的位置,将该节点插入即可。那么有一个问题就是新插入节点的颜色应该是什么颜色的呢?答案是红色。因为如果插入节点的父节点存在并且是黑色时,插入节点为红色完全满足红黑树的性质,不需要做任何平衡操作,但是如果插入节点换成黑色时,那么在插入位置所在的子树中黑色节点总是多1 ,那么就所有的插入操作都必须做平衡操作。
ok~插入节点已经完成了,但是并非所有插入节点后的树都满足红黑树的性质,如果不满足的话那么就必须进行自平衡操作了。
下面开始逐一分析插入情形,及其操作过程。
对于这种情形,我们只需将插入节点设为根节点即可,但是由于红黑树的性质2,:根节点必须为黑色,所以在插入节点之后还需将根节点的颜色置为黑色。
把插入节点的的value值和已经存在的value值替换即可,这个操作是不会影响二叉树的平衡的。
这种情形是插入操作中最简单的一种情形,这种情形下,不需要做任何操作,因为之前说过,刚插入时的节点是红色的,当插入节点的父节点是黑色时并不会影响红黑树的性质。
当插入节点的父节点为红色时,根据红黑树的性质2:根结点是黑色。如果插入的父结点为红结点,那么该父结点不可能为根结点,所以插入结点总是存在祖父结点。因为后面的操作会和祖父节点有关。
对于这种情形如下图:
操作如下:
- 将p和s节点置为黑色
- 将pp节点置为红色
- 将pp节点置为当前插入节点
操作到此依然没有结束,可以看到,我们把PP结点设为红色了,如果PP的父结点是黑色,那么无需再做任何处理;但如果PP的父结点是红色,根据性质4,此时红黑树已不平衡了,所以还需要把PP当作新的插入结点,继续做插入操作自平衡处理,直到平衡为止。
试想下PP刚好为根结点时,那么根据性质2,我们必须把PP重新设为黑色,那么树的红黑结构变为:黑黑红。换句话说,从根结点到叶子结点的路径中,黑色结点增加了。这也是唯一一种会增加红黑树黑色结点层数的插入情景。
上面的情形描述有点绕,但是转换成图形描述就简单多了,如下图:
对于此种情形操作如下:
- p节点设为黑色
- pp节点设为红色
- 以pp节点为中心节点进行右旋
操作后就如左图
情形4.2.2和情形4.2.1就差一个字,但是意义却是不同的如下图:
对于这种情形操作如下:
- 以p节点为中心节点进行左旋.
- 将p节点设置为插入节点得到情形4.2.1
- 按照情况4.2.1.情形处理
对于情形4.3.*和情形4.2.*的情形几乎是相反的,可以参考上图4.3.*的描述和前文对4.2.*的操作描述 想想4.3.*该怎么做。在此不再多做叙述了。
目前对添加节点操作的理解就这么多~
删除节点操作
对于删除操作应该是红黑树中操作最复杂的了,
红黑树节点的删除我认为大致分为3点
- 寻找待删节点(d)。
- 如果待删节点左右子树都不为空,则寻找待删节点的后继节点(h),将节点h和节点d互换,然后将h设为待删节点,然后再进行删除节点时情形的分析和操作。
- 最后删除节点。
另外需要特别注意:上图删除节点的所有情形描述都是在经过第二点后的情形。也就是上图的所有的删除情形都是经过转换后的情形,也就是说此时的待删节点要么是叶子节点,要么是有一个左子树或只有一个右子树。
另外:下面的所有操作过程中,待删节点都参与红黑树的平衡过程,最后会将待删节点删除。
虽然红黑树的删除情形比删除情形还要复杂。但是本文还是会对所有情形认真分析一遍~下面进入正文。
对于这种情形来说其实只有一种可能性,那就是待删节点为红色叶子节点。为什么呢?上文已经说过,这时的待删节点都是经过转换后的,待删节点要么是叶子节点,要么是有一个左子树或只有一个右子树,如果待删节点有一棵子树,那么该子树必然为黑色,那么将不满足红黑树的性质4。所以待删节点一定为红色待删节点。
那么既然是红色叶子节点,操作就简单了,直接将该待删节点删除即可。删除红色叶子结点不会对红黑树影响红黑树性质。
如果待删节点为黑色,且只有一个左子树或右子树,那么该子树必然为红色,对于这种情况也是一种简单情况,只需做以下简单处理就ok了。
- 把待删节点删除。
- 用它的左子树或右子树代替待删节的位置。
- 将代替节点的颜色变为黑色。
对于这种情形是最复杂的。因为删除一个黑色的叶子节点势必会对红黑树的性质产生影响,所以删除节点后必须对红黑树进行自平衡操作。
这种情形下又分两种情况:1.待删节点是其父节点的左孩子,2.待删节点是其父节点的右孩子。下面以情况1 为例进行分析。
如果待删节点的兄弟节点是红色,那么根据红黑树的性质,兄弟节点必须有两个黑色子节点。
对于这种情况还是比较复杂,并不能一步完成,而是通过以下操作转成其他情况,然后再做处理。如下图。
操作如下:
- 将父亲节点和兄弟节点的颜色互换
- 将p节点进行左旋
经过上图操作以后并不能直接满足红黑树的性质,但是确转化成了下面将要讨论的情形3.1.2.3,然后再根据情形3.1.2.3进行相应操作即可。
这种情形下又可以分为以下四种情形,参考删除节点的描述图。
下面我们一一叙述
在这种情况下近侄子节点可以是红色,也可以不存在,但是不可能是黑色叶子节点。
操作如下:
- 将P和S的颜色对调
- 将远侄子的颜色变黑色
- 对p树进行左旋操作
完成后将如上图所示,然后将待删节点d删除,完全满足红黑树的性质。
这种情形下可以通过两步操作变成3.1.2.1情形。如下
操作如下
- 将s和sl的颜色互换
- 然后将s树右旋
- 变为情况3.1.2.1按3.1.2.1进行操作
然后在按照情形3.1.2.1继续操作即可。
情形如下图
操作如下:
- 将父节点p变为黑色
- 待删节点的兄弟节点s变为红色
经过如上操作和变换,然后将节点d删除,依然满足红黑树的性质。
这种情形下相对复杂,因为三个节点都是黑色,把待删节点删除后,无论在p树下怎么调整,经过p树的路径都会少一个黑色节点,将违背红黑树性质4。那么只有一种方法就是把p节点充当待删节点,继续根据情况进行自平衡处理。
情形如下图
操作如下
- 将待删节点的兄弟节点s变为红色
- 把p点作为待删节点,继续根据情况进行自平衡处理直到p点为根节点。
该情况下的所有情况和3.1.*的情况完全相反,可参考3.1.*分析
至此所有的情况都已讨论完了,接下来用上代码。
代码
package com.dzqc.yx.tree;
/**
* 节点类
* @author jiajia
* @param <T>
* @param <E>
*/
public class Node<T,E> {
/**
* 用于查找数据时比较的key
*/
public Integer key;
/**
* 数据
*/
public E e;
/**
* 父节点引用
*/
public Node<T,E> parent;
/**
* 左子节点引用
*/
public Node<T,E> left;
/**
* 右子节点引用
*/
public Node<T,E> right;
public String color;
public Node(Integer key, E e) {
super();
this.key = key;
this.e = e;
}
public Node(Integer key, E e, Node<T, E> parent) {
super();
this.key = key;
this.e = e;
this.parent = parent;
}
public Node(Integer key, E e,String color) {
super();
this.key = key;
this.e = e;
this.color=color;
}
public Node(Integer key, E e,String color, Node<T, E> parent) {
super();
this.key = key;
this.e = e;
this.parent = parent;
this.color=color;
}
public E setValue(E e) {
return this.e=e;
}
public String getColor() {
return color;
}
public void setColor(String color) {
this.color = color;
}
}
package com.dzqc.yx.tree;
import java.util.LinkedList;
/**
* 红黑树核心类
* @author jiajia
* @param <T>
* @param <E>
*/
public class Tree<T,E> {
/**
* 根节点
*/
public Node<T,E> root;
/**
* 集合容量
*/
public Integer size=0;
/**
* 左旋
* p为旋转的中心点
*/
public void rotateLeft(Node<T,E> p) {
if (p != null) {
Node<T,E> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}
/**
* 右旋
* 以p点为中心点旋转
*/
public void rotateRight(Node<T,E> p) {
if (p != null) {
Node<T,E> l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}
/***
* 先序遍历
* @param p
*/
public void preDis(Node<T,E> p) {
if(p==null)
return;
if(p==root) {
System.out.println(p.e+" (b) 是根节点");
}else {
if(p==p.parent.left) {
System.out.println(p.e+" ("+p.getColor()+")\t 是 "+p.parent.e+" 的 left 孩子");
}else {
System.out.println(p.e+" ("+p.getColor()+")\t 是 "+p.parent.e+" 的 right 孩子");
}
}
preDis(p.left);
preDis(p.right);
}
/***
* 先序遍历
* @param p
*/
public void preDis2(Node<T,E> p) {
if(p==null)
return;
System.out.println(p.e);
preDis(p.left);
preDis(p.right);
}
/***
* 中序遍历
* @param p
*/
public void cenDis(Node<T,E> p) {
if(p==null)
return;
cenDis(p.left);
System.out.println(p.e+" "+p.getColor());
cenDis(p.right);
}
/**
* 层级遍历
* 其中用到了栈和队列,数据结构采用jdk提供的集合LinkedList
*/
public void cengDis(Node<T,E> p) {
LinkedList<Node<T,E>> stack=new LinkedList<>();
LinkedList<Node<T,E>> dui=new LinkedList<>();
PrintfTree tree = null;
dui.add(p);
while(true){
Node<T,E> f=null;
if(dui.size()>0) {
f=dui.removeFirst();
}
if(f==null) {
Node<T,E> d=null;
if(stack.size()>0) {
d=stack.removeFirst();
}
if(d==null) {
tree.show();
return ;
}else {
dui.addLast(d);
while(true) {
d=null;
if(stack.size()>0) {
d=stack.removeFirst();
}
if(d==null) {
break;
}else {
dui.addLast(d);
}
}
}
}else {
if(tree==null) {
tree=new PrintfTree(""+f.e+"("+f.getColor()+")");
}else {
tree.add(new PrintfTree(""+f.e+"("+f.getColor()+")"));
}
Node<T,E> left=f.left;
if(left!=null) {
stack.addLast(left);
}
Node<T,E> right=f.right;
if(right!=null) {
stack.addLast(right);
}
}
}
}
/***
* 根据key得到节点信息
* @param key
* @return
*/
public E getE(Integer key) {
if (key == null)//不允许key值为null
throw new NullPointerException();
Node<T,E> p = root;
while (p != null) {
int cmp = p.key;
if (cmp > key)//向左找
p = p.left;
else if (cmp < key)//向右找
p = p.right;
else
return p.e;
}
return null;
}
/**
* 寻找后继节点
* @param t
* @return
*/
public Node<T,E> successor(Node<T,E> t) {
if (t == null)
return null;
else if (t.right != null) {
Node<T,E> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
Node<T,E> p = t.parent;
Node<T,E> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
/**
* 寻找前驱节点
* @param t
* @return
*/
public Node<T, E> precursor(Node<T, E> t){
if(t!=null) {
if(t.left!=null) {
Node<T, E> p=t.left;
while(p.right!=null)
p=p.right;
return p;
}else {
if(t==t.parent.right) {
return t.parent;
}else {
Node<T, E> p=t.parent;
while(p!=null&&p!=p.parent.right) {
p=p.parent;
}
return p.parent;
}
}
}else {
return null;
}
}
/**
* 添加节点
* @param key
* @param e
* @return
*/
public E put(Integer key,E e) {
int cmp;
Node<T,E> parent;
Node<T,E> t=root;
if (key == null)
throw new NullPointerException();
do {
parent = t;
cmp = t.key;
if (cmp > key) t = t.left;//向左找
else if (cmp < key) t = t.right;//向右找
else return t.setValue(e);
} while (t != null);
Node<T,E> ve = new Node<T,E>(key, e,"r", parent);//创建并插入新的entry
if (cmp > key) parent.left = ve;
else parent.right = ve;
fixAfterInsertion(ve);//调整
size++;
return e;
}
/**
* 删除节点的函数
* 1. 如果待删节点左右子树都非空,寻找改节点的后继节点,并把待删节点和待删节点的后继节点替换。此时待删节点会满足下面的两个条件之一
* 2. 待删节点只有一颗非空子树,该非空子树代替待删节点的位置,如果待删节点的颜色位黑色,则调整颜色。(只可能为黑色)
* 3. 待删节点为叶子节点,如果是红色,直接删除,如果是黑色,先进行调整,再删除。
* @param n
*/
public void deleteEntry(Node<T,E> n) {
if (n.left != null && n.right != null) {
/**
* 删除点n的左右子树都非空
* 寻找其后继节点 s 将待删节点 n 的key和value与s节点互换
* 把删除节点 n 的情况替换成删除 s 节点
*/
Node<T,E> s = successor(n);// 后继
n.key = s.key;
n.e = s.e;
n = s;
}
Node<T,E> replacement = (n.left != null ? n.left : n.right);
if (replacement != null) {
/**
* 删除点n有且只有一棵子树非空
* 下方的代码是将n节点唯一的一棵子树替换节点n
*/
replacement.parent = n.parent;
if (n.parent == null) {
root = replacement;
}else if (n == n.parent.left) {
n.parent.left = replacement;
}else {
n.parent.right = replacement;
}
n.left = n.right = n.parent = null;
/**
* 如果删除节点是黑色,则将替换节点的颜色设置为黑色,保持红黑树平衡
*/
if (n.getColor().equals("b")) {
setColor(replacement,"b");
}
} else if (n.parent == null) {
root = null;
} else {
/**
* 删除点n的左右子树都为空
*/
if (n.getColor().equals("b")) {
/**
* 颜色为黑色
* 调整
*/
fixAfterDeletion(n);
}
if (n.parent != null) {
/**
* 删除n节点
*/
if (n == n.parent.left) {
n.parent.left = null;
}else if (n == n.parent.right) {
n.parent.right = null;
}
n.parent = null;
size--;
}
}
}
/**
* 删除节点时的调整函数
* @param x
*/
public void fixAfterDeletion(Node<T,E> x) {
while (x != root && colorOf(x).equals("b")) {
if (x == leftOf(parentOf(x))) {
Node<T,E> sib = rightOf(parentOf(x));
if (colorOf(sib).equals("r")) {
setColor(sib, "b");
setColor(parentOf(x), "r");
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
if ((leftOf(sib)==null||colorOf(leftOf(sib)).equals("b")) &&
(rightOf(sib)==null||colorOf(rightOf(sib)).equals("b"))){
setColor(sib, "r");
x = parentOf(x);
}else {
if (rightOf(sib)==null||colorOf(rightOf(sib)).equals("b")) {
setColor(leftOf(sib), "b");
setColor(sib, "r");
rotateRight(sib);
sib = rightOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), "b");
setColor(rightOf(sib), "b");
rotateLeft(parentOf(x));
x = root;
}
} else {
Node<T,E> sib = leftOf(parentOf(x));
if (colorOf(sib).equals("r")) {
setColor(sib, "b");
setColor(parentOf(x),"r");
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if ((rightOf(sib)==null||colorOf(rightOf(sib)) .equals("b")) &&
(leftOf(sib)==null||colorOf(leftOf(sib)).equals("b"))) {
setColor(sib,"r");
x = parentOf(x);
} else {
if (leftOf(sib)==null||colorOf(leftOf(sib)).equals("b")) {
setColor(rightOf(sib),"b");
setColor(sib,"r");
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), "b");
setColor(leftOf(sib), "b");
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, "b");
}
/***
* 添加节点时的调整函数
* @param x 插入节点
*/
@SuppressWarnings("unused")
public void fixAfterInsertion(Node<T,E> x) {
/**
* 插入节点先设置成红色
*/
x.setColor("r");
/**
* 在情形4.1中的操作可能导致两个红色节点相邻的情况
*/
while (x != null && x != root && x.parent.getColor() == "r") {
/**
* x节点的父节点是x节点的祖父节点的左孩子
*/
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Node<T,E> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == "r") {
/**
* 情形4.1叔叔结点存在并且为红结点
* 将其父节点和叔叔节点设为黑色,祖父节点设为红色。
*/
setColor(parentOf(x), "b");
setColor(y, "b");
setColor(parentOf(parentOf(x)), "r");
x = parentOf(parentOf(x));
} else {
/**
*
* 叔叔节点不存在或为黑色节点
*/
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), "b");
setColor(parentOf(parentOf(x)), "r");
rotateRight(parentOf(parentOf(x)));
}
} else {//x节点的父节点是x节点的祖父节点的右孩子
Node<T,E> y = leftOf(parentOf(parentOf(x)));//y节点为x节点的叔父节点
if (colorOf(y) == "r") {//x节点的叔父节点为红色
setColor(parentOf(x), "b");
setColor(y, "b");
setColor(parentOf(parentOf(x)), "r");
x = parentOf(parentOf(x));
} else {//x节点的叔父节点为黑色
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), "b");
setColor(parentOf(parentOf(x)), "r");
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.setColor("b");
}
private Node<T, E> rightOf(Node<T, E> parentOf) {
// TODO Auto-generated method stub
return parentOf.right;
}
private Node<T, E> leftOf(Node<T, E> parentOf) {
// TODO Auto-generated method stub
return parentOf.left;
}
private void setColor(Node<T, E> y, String string) {
// TODO Auto-generated method stub
y.color=string;
}
private String colorOf(Node<T, E> y) {
// TODO Auto-generated method stub
return y.getColor();
}
private Node<T,E> parentOf(Node<T, E> x) {
return x.parent;
}
}
package com.dzqc.yx.tree;
public class PrintfTree{
private String v;
private PrintfTree l;
private PrintfTree r;
public PrintfTree(String v){
this.v = v;
}
public void add(PrintfTree the){
if(new Integer(the.v.substring(0,the.v.lastIndexOf("("))) < new Integer(v.substring(0,v.lastIndexOf("(")))){
if(l==null) l = the;
else l.add(the);
}
else{
if(r==null) r = the;
else r.add(the);
}
}
public int getHeight(){
int h = 2;
int hl = l==null? 0 : l.getHeight();
int hr = r==null? 0 : r.getHeight();
return h + Math.max(hl,hr);
}
public int getWidth(){
int w = (""+v).length();
if(l!=null) w += l.getWidth();
if(r!=null) w += r.getWidth();
return w;
}
public void show(){
char[][] buf = new char[getHeight()][getWidth()];
printInBuf(buf, 0, 0);
showBuf(buf);
}
private void showBuf(char[][] x){
for(int i=0; i<x.length; i++){
for(int j=0; j<x[i].length; j++)
System.out.print(x[i][j]==0? ' ':x[i][j]);
System.out.println();
}
}
private void printInBuf(char[][] buf, int x, int y){
String sv = "" + v;
int p1 = l==null? x : l.getRootPos(x);
int p2 = getRootPos(x);
int p3 = r==null? p2 : r.getRootPos(p2+sv.length());
buf[y][p2] = '|';
for(int i=p1; i<=p3; i++) buf[y+1][i]='-';
for(int i=0; i<sv.length(); i++) buf[y+1][p2+i]=sv.charAt(i);
if(p1<p2) buf[y+1][p1] = '/';
if(p3>p2) buf[y+1][p3] = '\\';
if(l!=null) l.printInBuf(buf,x,y+2);
if(r!=null) r.printInBuf(buf,p2+sv.length(),y+2);
}
private int getRootPos(int x){
return l==null? x : x + l.getWidth();
}
}