使用和二叉查找树相同的方式插入一个结点，如果不满足红黑树性质需要修复
分析一下怎么可以递归往红黑树添加新结点
1. 怎么往普通二叉查找树添加新结点(递归实现)
假设当前结点为p
- 递归出口
1 、h == null 也就是p下个结点是空的（p下个结点就是需要插入的地方）,
每一次插入都是只执行一次（叶子节点 ）
2 、return h 每个节点执行一次
规模也是每次-1、 层次每次+1并且越来越往外层 - 区分往左还是往右添加
比较带插入值和p的值，比p值大往右，小往左 - 返回值
开始递归返回的规模比较大， 到最后一次遍历返回的是整个树结构
比如下面这个树
带插入的是 0
然后规模开始就是4 层次是1（从里到外）
0是h == null返回 执行一次 规模-1
124结点是 return h 执行3次 没执行一次规模-1
/**
* 4
* / \
* 2 7
* / \ \
* 1 3 8
* /
* 0
*/
public class RedBlackBST<Key extends Comparable<Key>, Value>{
public Node root;
private static final boolean RED = true;
private static final boolean BLACK = false;
public class Node {
Key key;
Value val;
Node left, right;
int N;
boolean color;
Node(Key key, Value val, int N, boolean color){
this.key = key;
this.val = val;
this.N = N;
this.color = color;
}
}
private boolean isRed(Node x){
if(x == null){
return false;
}
return x.color == RED;
}
private int size(Node x){
if(x == null){
return 0;
}else{
return x.N;
}
}
private Node rotateLeft(Node h){
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
x.N = h.N;
h.N = 1+size(h.left) +size(h.right);
return x;
}
private Node rotateRight(Node h){
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = RED;
x.N = h.N;
h.N = 1+size(h.right) +size(h.left);
return x;
}
private void flipColor(Node h){
h.color = RED;
h.left.color = BLACK;
h.right.color = BLACK;
}
public void put(Key key, Value val){
root = put(root, key, val);
root.color = BLACK;
}
public Node put (Node h, Key key, Value val){
if(h == null){
return new Node(key, val, 1, RED);
}
int cmp = key.compareTo(h.key);
if(cmp < 0){
//待插入值小于当前的key
h.left = put(h.left, key, val);
}
else if(cmp > 0){
//待插入值大于当前的key
h.right = put(h.right, key, val);
}
else{
//相等 直接替换 不插入元素
h.val = val;
}
if(isRed(h.right) && !isRed(h.left)){
h = rotateLeft(h);
System.out.println("左旋");
}
if(!isRed(h.left) && isRed(h.left.left)){
h = rotateRight(h);
System.out.println("右旋");
}
if(isRed(h.right) && isRed(h.left)){
flipColor(h);
}
h.N = size(h.left) + size(h.right) + 1;
return h;
}
}
