红黑树原理详解与手写红黑树
红黑树的性质：
红黑树的性质红黑树示例图
性质1：每个节点要么是黑色，要么是红色。性质2：根节点是黑色。性质3：每个叶子节点（NIL）是黑色。性质4：每个红色节点的两个子节点一定都是黑色。不能有两个红色节点相连。性质5：任意一节点到每个叶子节点的路径都包含数量相同的黑结点。俗称：黑高！从性质5又可以推出：性质5.1：如果一个节点存在黑子节点，那么该结点肯定有两个子节点
红黑树并不是一个完美平衡二叉查找树，从图上可以看到，根结点P的左子树显然比右子树高，
但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。
所以我们叫红黑树这种平衡为黑色完美平衡。
红黑树的性质讲完了，只要这棵树满足以上性质，这棵树就是趋近与平衡状态的，
前面讲到红黑树能自平衡，它靠的是三种操作：左旋、右旋和变色。
1.变色结点的颜色由红变黑或由黑变红。
2.左旋以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。
3.右旋以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变
左旋图示
右旋图示
红黑树查找：
红黑树插入：
插入操作包括两部分工作：
1.查找插入的位置
2.插入后自平衡
注意：插入节点，必须为红色，理由很简单，红色在父节点（如果存在）为黑色节点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。
但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。
在开始每个情景的讲解前，我们还是先来约定下:
红黑树插入节点情景分析
情景1：红黑树为空树
最简单的一种情景，直接把插入结点作为根结点就行
注意：根据红黑树性质2：根节点是黑色。还需要把插入结点设为黑色。
情景2：插入结点的Key已存在
处理：更新当前节点的值，为插入节点的值
情景3：插入结点的父结点为黑结点
由于插入的结点是红色的，当插入结点的黑色时，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。
情景4：插入节点的父节点为红色
再次回想下红黑树的性质2：根结点是黑色。如果插入节点的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。
这一点很关键，因为后续的旋转操作肯定需要祖父结点的参与。
插入情景4.1：叔叔结点存在并且为红结点
依据红黑树性质4可知，红色节点不能相连 ==> 祖父结点肯定为黑结点；
因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是：黑红红。显然最简单的处理方式是把其改为：红黑红
处理：
1.将P和U节点改为黑色
2.将PP改为红色
3.将PP设置为当前节点，进行后续处理
可以看到，我们把PP结点设为红色了，如果PP的父结点是黑色，那么无需再做任何处理；
但如果PP的父结点是红色，则违反红黑树性质了。所以需要将PP设置为当前节点，继续做插入操作自平衡处理，直到平衡为止。
插入情景4.2：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点
注意：单纯从插入前来看，叔叔节点非红即空（NIL节点），否则的话破坏了红黑树性质5，此路径会比其它路径多一个黑色节点。
插入情景4.2.1：新插入节点，为其父节点的左子节点（LL红色情况）
处理：
1.变颜色：将P设置为黑色，将PP设置为红色
2.对PP节点进行右旋
插入情景4.2.2：新插入节点，为其父节点的右子节点（LR红色情况）
处理：
1.对P进行左旋
2.将P设置为当前节点，得到LL红色情况
3.按照LL红色情况处理（1.变颜色 2.右旋PP）
**插入情景4.3：**叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点
该情景对应情景4.2，只是方向反转，直接看图。
插入情景4.3.1：新插入节点，为其父节点的右子节点（RR红色情况）
处理：
1.变颜色：将P设置为黑色，将PP设置为红色
2.对PP节点进行左旋
插入情景4.3.2：新插入节点，为其父节点的左子节点（RL红色情况）
处理：
1.对P进行右旋
2.将P设置为当前节点，得到RR红色情况
3.按照RR红色情况处理（1.变颜色 2.左旋PP）
红黑树代码详解
package com
.study
.struct
;
public class TreeOperation {
public static int getTreeDepth(RBTree
.RBNode root
) {
return root
== null
? 0 : (1 + Math
.max(getTreeDepth(root
.getLeft()), getTreeDepth(root
.getRight())));
}
private static void writeArray(RBTree
.RBNode currNode
, int rowIndex
, int columnIndex
, String
[][] res
, int treeDepth
) {
if (currNode
== null
) return;
res
[rowIndex
][columnIndex
] = String
.valueOf(currNode
.getKey() );
int currLevel
= ((rowIndex
+ 1) / 2);
if (currLevel
== treeDepth
) return;
int gap
= treeDepth
- currLevel
- 1;
if (currNode
.getLeft() != null
) {
res
[rowIndex
+ 1][columnIndex
- gap
] = "/";
writeArray(currNode
.getLeft(), rowIndex
+ 2, columnIndex
- gap
* 2, res
, treeDepth
);
}
if (currNode
.getRight() != null
) {
res
[rowIndex
+ 1][columnIndex
+ gap
] = "\\";
writeArray(currNode
.getRight(), rowIndex
+ 2, columnIndex
+ gap
* 2, res
, treeDepth
);
}
}
public static void show(RBTree
.RBNode root
) {
if (root
== null
) System
.out
.println("EMPTY!");
int treeDepth
= getTreeDepth(root
);
int arrayHeight
= treeDepth
* 2 - 1;
int arrayWidth
= (2 << (treeDepth
- 2)) * 3 + 1;
String
[][] res
= new String[arrayHeight
][arrayWidth
];
for (int i
= 0; i
< arrayHeight
; i
++) {
for (int j
= 0; j
< arrayWidth
; j
++) {
res
[i
][j
] = " ";
}
}
writeArray(root
, 0, arrayWidth
/ 2, res
, treeDepth
);
for (String
[] line
: res
) {
StringBuilder sb
= new StringBuilder();
for (int i
= 0; i
< line
.length
; i
++) {
sb
.append(line
[i
]);
if (line
[i
].length() > 1 && i
<= line
.length
- 1) {
i
+= line
[i
].length() > 4 ? 2: line
[i
].length() - 1;
}
}
System
.out
.println(sb
.toString());
}
}
}
package com
.study
.struct
;
public class RBTree <K
extends Comparable<K>, V
> {
private static final boolean RED
= true;
private static final boolean BLACK
= false;
private RBNode root
;
public RBNode
getRoot() {
return root
;
}
public void insert(K key
, V value
) {
RBNode node
= new RBNode();
node
.setKey(key
);
node
.setValue(value
);
node
.setColor(RED
);
insert(node
);
}
private void insert(RBNode node
) {
RBNode parent
= null
;
RBNode x
= this.root
;
while(x
!= null
) {
parent
= x
;
int cmp
= node
.key
.compareTo(parent
.key
);
if(cmp
< 0) {
x
= x
.left
;
} else if(cmp
== 0) {
parent
.setValue(node
.value
);
return;
} else {
x
= x
.right
;
}
}
node
.parent
= parent
;
if(parent
!= null
) {
if(node
.key
.compareTo(parent
.key
) < 0) {
parent
.left
= node
;
} else {
parent
.right
= node
;
}
} else {
this.root
= node
;
}
insertFixUp(node
);
}
private void insertFixUp(RBNode node
) {
RBNode parent
= parentOf(node
);
RBNode gparent
= parentOf(parent
);
if(parent
!= null
&& isRed(parent
)) {
if(parent
== gparent
.left
) {
RBNode uncle
= gparent
.right
;
if(uncle
!= null
&& isRed(uncle
)) {
setBlack(parent
);
setBlack(uncle
);
setRed(gparent
);
insertFixUp(gparent
);
return;
}
if(uncle
== null
|| isBlack(uncle
)) {
if(node
== parent
.right
) {
leftRotate(parent
);
insertFixUp(parent
);
return;
}
if(node
== parent
.left
) {
setBlack(parent
);
setRed(gparent
);
rightRotate(gparent
);
}
}
} else {
RBNode uncle
= gparent
.left
;
if(uncle
!= null
&& isRed(uncle
)) {
setBlack(parent
);
setBlack(uncle
);
setRed(gparent
);
insertFixUp(gparent
);
return;
}
if(uncle
== null
|| isBlack(uncle
)) {
if(node
== parent
.left
) {
rightRotate(parent
);
insertFixUp(parent
);
return;
}
if(node
== parent
.right
) {
setBlack(parent
);
setRed(gparent
);
leftRotate(gparent
);
}
}
}
}
setBlack(this.root
);
}
private void leftRotate(RBNode x
) {
RBNode y
= x
.right
;
x
.right
= y
.left
;
if(y
.left
!= null
) {
y
.left
.parent
= x
;
}
if(x
.parent
!= null
) {
if(x
.parent
.left
== x
) {
x
.parent
.left
= y
;
} else {
x
.parent
.right
= y
;
}
y
.parent
= x
.parent
;
} else {
this.root
= y
;
this.root
.parent
= null
;
}
y
.left
= x
;
x
.parent
= y
;
}
private void rightRotate(RBNode y
) {
RBNode x
= y
.left
;
y
.left
= x
.right
;
if(x
.right
!= null
) {
x
.right
.parent
= y
;
}
x
.parent
= y
.parent
;
if(y
.parent
!= null
) {
if(y
.parent
.left
== y
) {
y
.parent
.left
= x
;
} else {
y
.parent
.right
= x
;
}
} else {
this.root
= x
;
this.root
.parent
= null
;
}
x
.right
= y
;
y
.parent
= x
;
}
private RBNode
parentOf(RBNode node
) {
if(node
!= null
) {
return node
.parent
;
}
return null
;
}
private boolean isRed(RBNode node
) {
if(node
!= null
) {
return node
.isColor() == RED
;
}
return false;
}
private void setRed(RBNode node
) {
if(node
!= null
) {
node
.setColor(RED
);
}
}
private void setBlack(RBNode node
) {
if(node
!= null
) {
node
.setColor(BLACK
);
}
}
public void inOrderPrint() {
if(this.root
!= null
) {
inOrderPrint(this.root
);
}
}
private void inOrderPrint(RBNode node
) {
if(node
!= null
) {
inOrderPrint(node
.left
);
System
.out
.println("key -> " + node
.key
+ ", value -> " + node
.value
);
inOrderPrint(node
.right
);
}
}
private boolean isBlack(RBNode node
) {
if(node
!= null
) {
return node
.isColor() == BLACK
;
}
return false;
}
static class RBNode<K
extends Comparable<K>, V
> {
private boolean color
;
private RBNode left
;
private RBNode right
;
private RBNode parent
;
private K key
;
private V value
;
public RBNode(boolean color
, RBNode left
, RBNode right
, RBNode parent
, K key
, V value
) {
this.color
= color
;
this.left
= left
;
this.right
= right
;
this.parent
= parent
;
this.key
= key
;
this.value
= value
;
}
public RBNode() {
}
public boolean isColor() {
return color
;
}
public void setColor(boolean color
) {
this.color
= color
;
}
public RBNode
getLeft() {
return left
;
}
public void setLeft(RBNode left
) {
this.left
= left
;
}
public RBNode
getRight() {
return right
;
}
public void setRight(RBNode right
) {
this.right
= right
;
}
public RBNode
getParent() {
return parent
;
}
public void setParent(RBNode parent
) {
this.parent
= parent
;
}
public K
getKey() {
return key
;
}
public void setKey(K key
) {
this.key
= key
;
}
public V
getValue() {
return value
;
}
public void setValue(V value
) {
this.value
= value
;
}
}
public void padding
( String ch
, int n
) {
int i
;
for ( i
= 0; i
< n
; i
++ )
System
.out
.printf(ch
);
}
void print_node
(RBNode root
, int level
) {
if ( root
== null
) {
padding
( "\t", level
);
System
.out
.println( "NIL" );
} else {
print_node
( root
.right
, level
+ 1 );
padding
( "\t", level
);
if(root
.color
== BLACK
) {
System
.out
.printf(root
.key
+ "(" + (root
.isColor() ? "红" : "黑") +")" + "\n");
} else
System
.out
.printf(root
.key
+ "(" + (root
.isColor() ? "红" : "黑") +")" + "\n");
print_node
( root
.left
, level
+ 1 );
}
}
void print_tree() {
print_node(this.root
,0);
System
.out
.printf("-------------------------------------------\n");
}
}
package com
.study
.struct
;
import java
.util
.Scanner
;
public class TestRBTree {
public static void main(String
[] args
) {
RBTree
<String, Object> rbt
= new RBTree();
while(true) {
Scanner sc
= new Scanner(System
.in
);
System
.out
.println("请输入key:");
String key
= sc
.next();
rbt
.insert(key
, null
);
TreeOperation
.show(rbt
.getRoot());
}
}
}
