红黑树插入节点
2018-02-27 本文已影响9人
sunpy
什么是红黑树
红黑树是带有着色性质的二叉查找树。
性质如下：
① 每一个节点或者着成红色或者着成黑色。
② 根节点为黑色。
③ 每个叶子节点为黑色。（指的是指针指向为NULL的叶子节点）
④ 如果一个节点是红色的，那么它的子节点必须是黑色的。
⑤ 从一个节点到一个NULL指针的每一条路径必须包含相同数目的黑色节点。
推论： 有n个节点的红黑树的高度最多是2log(N+1) 。
红黑树旋转操作的原理
下述代码注释搭配图片便于理解
右旋操作：
1.jpg
说明：将rbn节点和c节点顺时针旋转到b的下面，然后调整位置。
代码实现：
//顺时针右旋
public static void rotateByRight(RBNode rbn){
RBNode b =rbn.getLchild();
//旋转后结果调整，rbn的左孩子为e
rbn.setLchild(b.getRchild());
//如果b的右孩子e存在就确定e的父节点为rbn
if(b.getRchild() !=null){
b.getRchild().setParent(rbn);
}
//确定b的父节点为原rbn的父节点
b.setParent(rbn.getParent());
if(rbn.getParent() ==null){
root =;
}else{
//确定rbn是否为父节点的右孩子节点
if(rbn ==rbn.getParent().getRchild()){
rbn.getParent().setRchild(b);
}else{
rbn.getParent().setLchild(b);
}
}
//确定b的右孩子为rbn
b.setRchild(rbn);
//确定rbn的父节点为b
rbn.setParent(b);
}
左旋操作：
2.jpg
说明：将rbn节点和c节点逆时针旋转到d的下面，然后调整位置。
代码实现：
//逆时针左旋
public static void rotateByLeft(RBNode rbn){
RBNode d =rbn.getRchild();
//确定rbn的右孩子为e
rbn.setRchild(d.getLchild());
//如果e不为空，那么确定e的父节点为rbn
if(d.getLchild() !=null){
d.getLchild().setParent(rbn);
}
//确定d的父节点为rbn的父节点
d.setParent(rbn.getParent());
if(rbn.getParent() ==null){
root =;
}else{
//确定rbn是否为其父节点的左孩子节点，目得是为了确定d的父节点的左孩子还是右孩子为d
if(rbn ==rbn.getParent().getLchild()){
rbn.getParent().setLchild(d);
}else{
rbn.getParent().setRchild(d);
}
}
//确定d的左孩子为rbn
d.setLchild(rbn);
//确定rbn的父节点为d
rbn.setParent(d);
}
红黑树插入元素的原理
关于红黑树插入节点后为了保持红黑树的特性，主要进行的操作就是换颜色和旋转操作。
情况1：父节点是黑色，插入新节点为红色。
3.png
解决办法：
由于新节点父节点为黑色，直接插入即可。
情况2：父节点为红色，叔叔节点为红色，插入新节点为红色，插入新节点为父节点的左孩子节点。（红叔左父左插入情况）
4.png
解决办法：
为了保持新节点为红色，如果此时父节点为红色就不满足性质4.所以父节点需要调整为黑色，但是这样祖节点到NL叶子节点，就会出现数目不同的黑色节点了。不满足性质5了。所以祖节点需要调整为红色节点满足性质。这样叔叔也就得调整为黑色了，要不就不满足性质4和性质5.
总结：红父->黑父 红叔->黑叔 黑祖->红祖
情况3：父节点为红色，叔叔节点为红色，插入新节点为红色，插入新节点为父节点的右孩子节点。（红叔左父右插入情况）
5.png
解决办法：
这种情况同情况2一样，无须旋转，只是颜色不满足性质，只需调整颜色即可。
总结： 红父->黑父 红叔->黑叔 黑祖->红祖
情况4：父节点为红色，叔叔节点为黑色，插入新节点为红色，插入新节点为父节点的左孩子节点。（黑叔左父左插入情况）
6.png
解决办法：
这种情况单纯通过换色是无法控制红黑树性质的满足。通过右旋来满足平衡条件。
总结：右旋 红父->黑父 黑祖->红祖
情况5：父节点为红色，叔叔节点为黑色，插入新节点为红色，插入新节点为父节点的右孩子节点。（黑叔左父右插入情况）
7.png
解决办法：
这种使用上面的右旋会发现，就会出现两个值的节点和三个子节点的情况。我们先局部左旋父节点。然后将祖节点和叔节点右旋转。
总结：左旋 右旋 黑祖->红祖 红新->黑新
情况6：父节点为红色，叔叔节点为红色，插入新节点为红色，插入新节点为父节点的左孩子节点。（红叔右父左插入情况）
8.png
解决办法：
这种情况和情况2差不多，就是调整颜色就可以了，主要原因就可以发现父节点和叔叔节点都是红色，这样直接调整颜色，就会满足红黑树性质。
总结：红父->黑父 红叔->黑叔 黑祖->红祖
情况7：父节点为红色，叔叔节点为红色，插入新节点为红色，插入新节点为父节点的右孩子节点。（红叔右父右插入情况）
9.png
解决办法：
这种情况和情况3一样，都是只是调整下颜色就好。
总结：红父->黑父 红叔->黑叔 黑祖->红祖
情况8：父节点为红色，叔叔节点为黑色，插入新节点为红色，插入新节点为父节点的右孩子节点。（黑叔右父右插入情况）
10.png
解决办法：
这种情况会出现旋转了，因为叔节点和父节点颜色不同，所以单纯调整颜色不能满足性质了。就采用将祖节点和叔节点左旋，作为父节点的左孩子树。
总结：左旋 红父->黑父 黑祖->红祖
情况9：父节点为红色，叔叔节点为黑色，插入新节点为红色，插入新节点为父节点的左孩子节点。（黑叔右父左插入情况）
11.png
解决办法：
这种情况类似于情况5，如果我们直接左旋祖节点和叔节点，那么就会出现2节点，3孩子情况。所以为了避免这种冲突。就先进行局部旋转，先将父节点右旋，然后将祖节点和叔节点左旋。
总结：右旋 左旋 黑祖->红祖 红新->黑新
全面总结
黑父，直接插入新节点即可。
红叔，就调整颜色即可。
黑叔，需要进行旋转操作。
红黑树插入元素完整代码实现
颜色枚举：
public enum Color {
RED("0","红色"),
BLACK("1","黑色");
private String name = ;
private String value =;
private Color(String name, String value) {
this.name=name;
this.value=value;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public static Color getEnumByName(String name){
if ( == name) {
return null;
}
for (Color type : values()) {
if (type.getName().equals(name.trim()))
return type;
}
return null;
}
public static Map<String, String> toMap() {
Map<String, String> enumDataMap = new LinkedHashMap<String, String>();
for (Color type : values()) {
enumDataMap.put(type.getName(), type.getValue());
}
return enumDataMap;
}
}
红黑树节点数据的结构定义：
public class RBNode {
private Integer data;
//红黑树中节点对应的颜色
private Color color;
//红黑树中当前节点的左孩子节点
private RBNode lchild;
//红黑树中当前节点的右孩子节点
private RBNode rchild;
//红黑树中当前节点的父节点
private RBNode parent;
public RBNode(){}
public RBNode(Integer data){
this.data =data;
}
public RBNode(Integer data,Color color,RBNode parent,RBNode lchild,RBNode rchild){
this.data =data;
this.color =color;
this.parent =parent;
this.lchild =lchild;
this.rchild =rchild;
}
public RBNode getParent() {
return parent;
}
public void setParent(RBNode parent) {
this.parent = parent;
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public Color getColor() {
return color;
}
public void setColor(Color color) {
this.color = color;
}
public RBNode getLchild() {
return lchild;
}
public void setLchild(RBNode lchild) {
this.lchild = lchild;
}
public RBNode getRchild() {
return rchild;
}
public void setRchild(RBNode rchild) {
this.rchild = rchild;
}
}
主程序代码：
public class RBTree {
private static RBNode root =;
//顺时针右旋
public static void rotateByRight(RBNode rbn){
RBNode b =rbn.getLchild();
rbn.setLchild(b.getRchild());
if(b.getRchild() !=null){
b.getRchild().setParent(rbn);
}
b.setParent(rbn.getParent());
if(rbn.getParent() ==null){
root =;
}else{
if(rbn ==rbn.getParent().getRchild()){
rbn.getParent().setRchild(b);
}else{
rbn.getParent().setLchild(b);
}
}
b.setRchild(rbn);
rbn.setParent(b);
}
//逆时针左旋
public static void rotateByLeft(RBNode rbn){
RBNode d =rbn.getRchild();
rbn.setRchild(d.getLchild());
if(d.getLchild() !=null){
d.getLchild().setParent(rbn);
}
d.setParent(rbn.getParent());
if(rbn.getParent() ==null){
root =;
}else{
if(rbn ==rbn.getParent().getLchild()){
rbn.getParent().setLchild(d);
}else{
rbn.getParent().setRchild(d);
}
}
d.setLchild(rbn);
rbn.setParent(d);
}
//红黑树插入节点
private static void insertRBNode(RBNode insertNode){
RBNode tempRoot =root;
//给红黑树插入节点，先不考虑局部平衡问题
while(tempRoot !=null){
if(insertNode.getData()<tempRoot.getData()){
if(tempRoot.getLchild() !=null){
tempRoot =tempRoot.getLchild();
}else{
tempRoot.setLchild(insertNode);
insertNode.setParent(tempRoot);
break;
}
}else if(insertNode.getData()>tempRoot.getData()){
if(tempRoot.getRchild() !=null){
tempRoot =tempRoot.getRchild();
}else{
tempRoot.setRchild(insertNode);
insertNode.setParent(tempRoot);
break;
}
}
}
//插入节点设置为红色
insertNode.setColor(Color.RED);
insertNode.setLchild(null);
insertNode.setRchild(null);
adjustRBTree(insertNode);
}
//调整红黑树
public static void adjustRBTree(RBNode rbNode){
//定义父节点
RBNode parent =rbNode.getParent();
while(parent !=null && parent.getColor().equals(Color.RED)){
//定义祖父节点
RBNode grandParent =parent.getParent();
//如果父节点是祖父节点的左孩子
if(parent.equals(grandParent.getLchild())){
RBNode uncleNode =grandParent.getRchild();
//情况2、情况3：红叔
if(uncleNode !=null && uncleNode.getColor().equals(Color.RED)){
uncleNode.setColor(Color.BLACK);
parent.setColor(Color.BLACK);
grandParent.setColor(Color.RED);
}else if(uncleNode !=null && uncleNode.getColor().equals(Color.BLACK) && parent.getLchild().equals(rbNode)){
//情况4：黑叔，当前节点是左孩子
rotateByRight(grandParent);
parent.setColor(Color.BLACK);
grandParent.setColor(Color.RED);
}else if(uncleNode !=null && uncleNode.getColor().equals(Color.BLACK) && parent.getRchild().equals(rbNode)){
//情况5：黑叔，当前节点是右孩子
rotateByLeft(parent);
rotateByRight(grandParent);
rbNode.setColor(Color.BLACK);
grandParent.setColor(Color.RED);
}else{
break;
}
}else{//如果父节点是祖父节点的右孩子
RBNode uncleNode =grandParent.getLchild();
//情况6、情况7：红叔
if(uncleNode !=null && uncleNode.getColor().equals(Color.RED)){
uncleNode.setColor(Color.BLACK);
parent.setColor(Color.BLACK);
grandParent.setColor(Color.RED);
}else if(uncleNode !=null && uncleNode.getColor().equals(Color.BLACK) && parent.getRchild().equals(rbNode)){
//情况8：黑叔，当前节点是右孩子
rotateByLeft(grandParent);
parent.setColor(Color.BLACK);
grandParent.setColor(Color.RED);
}else if(uncleNode !=null && uncleNode.getColor().equals(Color.BLACK) && parent.getLchild().equals(rbNode)){
//情况9：黑叔，当前节点是左孩子
rotateByRight(parent);
rotateByLeft(grandParent);
grandParent.setColor(Color.RED);
rbNode.setColor(Color.BLACK);
}else{
break;
}
}
}
root.setColor(Color.BLACK);
}
public static void queryRBNodeByPre(RBNode root){
if(root !=null){
System.out.print(root.getData()+"["+root.getColor().getValue()+"]"+" - ");
queryRBNodeByPre(root.getLchild());
queryRBNodeByPre(root.getRchild());
}else{
return;
}
}
/*递归方式遍历红黑树
* root:为遍历红黑树的根节点
* 中序方式
* */
public static void queryRBNodeByOrder(RBNode root) {
if(root !=null ){
queryRBNodeByOrder(root.getLchild());
System.out.print(root.getData()+"["+root.getColor().getValue()+"]"+" - ");
queryRBNodeByOrder(root.getRchild());
}else{
return;
}
}
public static void main(String[] args) {
root =new RBNode(13,Color.BLACK,null,null,null);
insertRBNode(new RBNode(8));
insertRBNode(new RBNode(17));
insertRBNode(new RBNode(1));
insertRBNode(new RBNode(11));
insertRBNode(new RBNode(15));
insertRBNode(new RBNode(25));
insertRBNode(new RBNode(6));
insertRBNode(new RBNode(22));
insertRBNode(new RBNode(27));
/*initRBTree(new RBNode(6), root);
initRBTree(new RBNode(5), root);
initRBTree(new RBNode(4), root);
queryRBNodeByOrder(root);
System.out.println();
queryBSTNodeByPre(root);
System.out.println();
System.out.println("旋转值：");
//rotateByLeft(root.getLchild());
rotateByRight(root.getRchild());*/
queryRBNodeByPre(root);
System.out.println();
System.out.println("----------------");
queryRBNodeByOrder(root);
/*RBNode rbNode =getMinRchild(root);
System.out.println(rbNode.getData());*/
}
}
测试用例
12.jpg
测试结果
13.png
问题
在插入节点的时候，我直接使用root全局变量来操作的，发现程序的根节点被替换了，程序出现了问题。
后来才想到全局变量是在堆中开辟空间的，而堆是共享区域。方法体内定义的变量是在栈中开辟空间的，是在每个线程私有的区域，如果为了防止全局变量被修改，那么在方法中调用全局变量时，可以单独复制一份，以防止出现全局变量被修改。
如果读者发现博客中出现问题，谢谢评论指出。
参考
http://www.cnblogs.com/dongritengfei/archive/2010/06/16/1759209.html
http://www.cnblogs.com/skywang12345/p/3245399.html#commentform
https://www.ibm.com/developerworks/cn/java/j-lo-tree/index.html?ca=drs-
数据结构与算法分析（c语言）
