红黑树-详解及Java插入示例
详解插入分析-自顶向下Cur黑Cur红Brother黑Cur红Brother红Grand黑-圆Grand红-方
Java例子测试参考
详解
AVL流行的另外一种变种，操作最坏情况下O(logN)时间
定义：具有下面性质的二叉查找树
节点为红色或黑色根节点为黑色红色节点的子节点为黑色从一个节点到Null节点(默认叶子节点为空)，经过黑色树相等
插入分析-自顶向下
插入时，默认新节点N为红色，插入位置即新节点的parent为Cur
思路：让Cur的颜色重置为黑色，这样红色的N插入Cur的位置就还是红黑树！
备注：图中圆为黑，方形为红； N为新节点； Cur为要插入的位置，即N的parent; P为Cur的parent； B为Cur的兄弟brother； G为grand祖父，即N的parent的parent； GT即great曾祖父，Cur的parent的parent的parent
共可以分为下面3大种情况，共5种小情况
Cur黑
直接插入即可(新节点为左子树或右子树）；
左或右
Cur
N
Cur红Brother黑
若parent为红，Cur只能为黑，故parent必为黑; 进行一次单旋转即可，下面以向右单旋转为例（左Brother、向左单旋转的例子同理）
Cur为新根，且修改为黑；原来根P为Cur的子，修改为红
左或右
P
Cur
B
N
左或右
Cur
N
P
B
Cur红Brother红
如下图所示。目的让左右子树为黑（即下面的Cur或Brother为黑，N可以直接插入到Cur或Brother上）。
思路：从顶往下查找Cur，Cur的左右子树都为红色，进行处理，
grand为红或者黑2种情况
P
Cur
Brother
Grand黑-圆
P、Cur、B均颜色反置即可，结果如下所示
G
P
Cur
Brother
Grand红-方
这种情况是最复杂的。祖父grand为红，曾祖父great必然为黑，处理思路为对曾祖父这个子树进行处理，返回根节点为黑的新数（根节点可能部位曾祖父了！）
GT、G、P若不在一个方向上，则G、P进行一次单旋转GT、G、P已在一个方向上，GT、G进行一次单旋转
等同：不在一个方向上就进行双旋转，否则单旋转
下面以GT、G、P不在一个方向上示例。下面为原图
GT
G
a
c
P
Cur
Brother
下面G、P向左旋转，P及其左右子树颜色反置
GT
P
a
G
Brother
c
Cur
可以看到PG都为红色，且等同于GT、G、P在一个方向上的情况。所以要把P红色上冒，其实GT、P、a相当于上面第2大种情况了！！Cur(这里为P)红、B(这里为a)黑！！ GT、P进行向右旋转，在修改P、GT的颜色即可(P黑⚪，GT红方）：
P
G
GT
Brother
a
c
Cur
P
G
GT
Brother
a
c
Cur
Java例子
package com.ydfind.datastructure.tree;
/**
* 红黑树
* @param <T> 数据的类型
* @author ydfind
* @date 2019.11.1
*/
public class MyRedBlackTree<T extends Comparable<? super T>>{
/**
* 黑色
*/
private static final int BLACK = 1;
/**
* 红色
*/
private static final int RED = 0;
private RedBlackNode<T> header;
private RedBlackNode<T> nullNode;
// 当前节点、父、祖父、曾祖父节点
private RedBlackNode<T> current;
private RedBlackNode<T> parent;
private RedBlackNode<T> grand;
private RedBlackNode<T> great;
/*************************************************节点类**********************************/
/**
* 红黑树节点 类
* @param <T>
*/
private static class RedBlackNode<T> {
T data;
RedBlackNode<T> left;
RedBlackNode<T> right;
int color;
RedBlackNode(T data){
this(data, null, null );
}
RedBlackNode(T data, RedBlackNode<T> left, RedBlackNode<T> right) {
this.data = data;
this.left = left;
this.right = right;
// 默认节点为黑色
this.color = MyRedBlackTree.BLACK;
}
}
public MyRedBlackTree(){
// 初始化根节点和空节点（默认的叶子节点）
nullNode = new RedBlackNode<>(null);
nullNode.left = nullNode.right = nullNode;
header = new RedBlackNode<>(null);
header.left = header.right = nullNode;
}
private final int compare(T item, RedBlackNode<T> t){
if(t == header){
// header默认为空，默认比其他都小
return 1;
}else{
return item.compareTo(t.data);
}
}
public void insert(T item){
// 默认都等于头节点
current = parent = grand = header;
nullNode.data = item;
int cp;
while ((cp = compare(item, current)) != 0){// 会有相等的时候吗？？？？？？？？是不是插入后，和自己比较就相等了
// 往下面一个节点
great = grand;
grand = parent;
parent = current;
// 第一个节点必然再header的右边
current = cp < 0 ? current.left : current.right;
// 两个子节点为红，重新确定红黑色
if(current.left.color == RED && current.right.color == RED){
handleReorient(item);
}
}
// 找到对应节点current不为空，无法进行插入
if(nullNode != current){
return;
}
// 执行插入操作
current = new RedBlackNode<>(item, nullNode, nullNode);
if(compare(item, parent) < 0){
parent.left = current;
}else{
parent.right = current;
}
handleReorient(item);
}
/**
* 全局变量current两个子节点为红，重新确定红黑色
*/
private void handleReorient(T item){// current等变量传入这里会不会有问题?????????????????????
current.color = RED;
current.left.color = BLACK;
current.right.color = BLACK;
if(parent.color == RED){
grand.color = RED;
if((compare(item, parent) < 0) != (compare(item, grand) < 0)){
// 需要进行双旋转
// 第一步：current、parent两个节点进行，传入parent的parent即grand
parent = rotate(item, grand);
}
// 单旋转或双旋转的第二步
// 这里可能会使insert中current往前了，是不是会多了一层????????????????
current = rotate(item, great);
// 新树根默认黑色，这样树上面的节点的结构
current.color = BLACK;
}
header.right.color = BLACK;
}
/***************************************************旋转************************************/
/**
* 对parent的left或right节点，进行 单旋转 或 双旋转中单旋转;
* 并将新子树的树根 重新赋值；
* 其中颜色需要外部处理
* @param item
* @param parent
* @return
*/
private RedBlackNode<T> rotate(T item, RedBlackNode<T> parent){
if(compare(item, parent) < 0){
// 判断LL，还是LR型，单旋转后面的L或R
parent.left = compare(item, parent.left) < 0 ?
rotateWithLeftChild(parent.left) :
rotateWithRightChild(parent.left);
return parent.left;
}else{
parent.right = compare(item, parent.right) < 0 ?
rotateWithLeftChild(parent.right) :
rotateWithRightChild(parent.right);
return parent.right;
}
}
/**
* 左子树，向右单旋转
*/
private RedBlackNode<T> rotateWithLeftChild( RedBlackNode<T> k2 ){
RedBlackNode<T> k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
}
/**
* 右子树，向左单旋转
*/
private RedBlackNode<T> rotateWithRightChild( RedBlackNode<T> k1 )
{
RedBlackNode<T> k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
}
/*******************************************打印***********************************************/
public void printTree() {
if(isEmpty()) {
System.out.println("Empty tree");
} else {
System.out.println("\n中序：left data right--------------");
printTree(header.right);
System.out.println("\n先序：data left right--------------");
printPreTree(header.right);
}
}
private void printPreTree( MyRedBlackTree.RedBlackNode<T> t ) {
if(t != nullNode){
if(t.color == BLACK) {
System.out.print(t.data + " ");
}else {
System.out.print(t.data + "_ ");
}
if(t.right != nullNode || t.left != nullNode) {
printPreTree(t.left);
printPreTree(t.right);
}
}
}
private void printTree( MyRedBlackTree.RedBlackNode<T> t ) {
if(t != nullNode){
if(t.left != nullNode) {
printTree(t.left);
}
if(t.color == BLACK) {
System.out.print(t.data + " ");
}else {
System.out.print(t.data + "_ ");
}
if(t.right != nullNode) {
printTree(t.right);
}
}
}
public boolean isEmpty( ) {
return header.right == nullNode;
}
}
测试
package com.ydfind.datastructure.avl;
import com.ydfind.datastructure.tree.MyRedBlackTree;
import org.junit.Test;
public class RedBlackTreeTest {
@Test
public void testInsert(){
MyRedBlackTree redBlackTree = new MyRedBlackTree();
int[] items = {10, 85, 15, 70, 20, 60, 30, 50, 65, 80, 90, 40, 5, 55};
for(int item: items) {
redBlackTree.insert(item);
}
redBlackTree.printTree();
System.out.print("\n");
}
}
运行结果
中序：left data right--------------
5_ 10 15 20 30 40_ 50 55_ 60_ 65 70 80_ 85 90_
先序：data left right--------------
30 15 10 5_ 20 70 60_ 50 40_ 55_ 65 85 80_ 90_
利用先序和中序，还愿图如下：
左
5红
10
15
20
30
40红
50
55红
60红
65
70
80红
85
90红
与《数据结构与算法分析-C语言描述》中P351下面的图示一致
参考
《数据结构与算法分析-C语言描述》第2版《数据结构与算法分析-Java语言描述》第3版
