public class redbalcktree {
private class Node{
private int val;
private int key;
boolean color; //black true
private Node left,right,p;
private int N; //the number of the all nodes of its child nodes and itself
//private int num;//the number
public Node(int val,int key){
this.val = val; this.key = key;
}
}
Node root;
private void leftrotation(Node x){
Node y = x.right;
x.right = y.left;
if(y.left != null){
y.left.p = x;
}
y.p = x.p;
if(x.p == null){
root = y;
}
else if(x == x.p.left){
x.p.left = y;
}
else{x.p.right = y;}
y.left = x;
x.p = y;
}
private void rightrotation(Node y){
Node x = y.left;
y.left = x.right;
if(x.right != null){
x.right.p = y;
}
x.p = y.p;
if(y.p == null){
root = x;
}
else if(y == y.p.left){
y.p.left = x;
}
else{y.p.right = x;}
x.right = y;
y.p = x;
}
public void insert(int val,int key){
Node y = null;
Node x = root;
Node z = new Node(val,key);
if(x == null){root = z;}
while(x != null){
y = x;
if(z.key < x.key){
x = x.left;
}
else{x = x.right;}
}
z.p = y;
if(z.key < y.key){
y.left = z;
}
else{y.right = z;}
z.left = null;
z.right = null;
z.color = false;
inseretfix(z);
}
private void inseretfix(Node z){
Node y;
while (z.p.color == false){
if(z.p == z.p.p.left){
y = z.p.p.right;
if(y.color == false){ //case 1,both z.p and y(uncle) are red
z.p.color = true;
y.color = true;
z.p.p.color = false;
z= z.p.p;
continue;
}
else if(z == z.p.right){ //case 2, z.p is red,uncle is black,z is right,transfer to case 3
z = z.p;
leftrotation(z);
}
z.p.color = true; //case 3, z.p is red,uncle is black,z is left;
z.p.p.color = false;
rightrotation(z.p.p);
}
else{ //set y(uncle) and change rotation
y = z.p.p.left;
if(y.color == false){ //case 1,both z.p and y(uncle) are red
z.p.color = true;
y.color = true;
z.p.p.color = false;
z= z.p.p;
continue;
}
else if(z == z.p.right){ //case 2, z.p is red,uncle is black,z is right,transfer to case 3
z = z.p;
rightrotation(z);
}
z.p.color = true; //case 3, z.p is red,uncle is black,z is left;
z.p.p.color = false;
leftrotation(z.p.p);
}
}
root.color = true;
}
private int get(Node x,int key){
if(x == null){
throw new NullPointerException("have't this key");
}
if(x.key>key){
return get(x.left,key);
}
else if(x.key < key){
return get(x.right,key);
}
else{
return x.val;
}
}
private void transplant(Node u,Node v){ //substitute u as v
if(u.p == null){
root = v;
}
else if(u == u.p.left){
u.p.left = v;
}
else {
u.p.right = v;
}
v.p = u.p;
}
private Node deletemin(Node x){
if(x.left == null){return x.right;}
x.left = deletemin(x.left);
return x;
}
public void delete(int key){
int val = get(root,key);
Node z = new Node(val,key);
Node x;
Node y = z;
boolean original = y.color;
if(z.left == null){
x = z.right;
transplant(z,z.right);
}
else if(z.right == null){
x = z.left;
transplant(z,z.left);
}
else{
y = deletemin(z.right); // next node after z
original = y.color;
x = y.right;
if(y.p == z){
x.p = y;
}
else{
transplant(y,y.right); // put y.right on the original y's position
y.right = z.right;
y.right.p = y;
}
transplant(z,y);
y.left = z.left;
y.left.p = y;
y.color = z.color;
}
if(original == true){
deletefix(x);
}
}
private void deletefix(Node x) {
Node other;
while ((x.color = true) && (x != root)) {
if (x.p.left == x) {
other = x.p.right;
if (other.color == false) {
// Case 1: x's brother is red
other.color = true;
x.p.color = false;
leftrotation(x.p);
other = x.p.right;
}
if ((other.left.color == true) &&
(other.right.color == true) ){
// Case 2: x's black is black and w 's both child are black
other.color = false;
x = x.p;
continue;
} else if (other.right.color == true) {
// Case 3: transfer to case 4
other.left.color = true;
other.color = false;
rightrotation(other);
other = x.p.right;
}
// Case 4: x's black is black,w's right child is red ,left anyway
other.color = x.p.color;
x.p.color = true;
other.right.color = true;
leftrotation(x.p);
x = root;
break;
}
else {
other = x.p.left;
if (other.color == false) {
// Case 1: x's brother is red
other.color = true;
x.p.color = false;
rightrotation(x.p);
other = x.p.right;
}
if ((other.left.color == true) &&
(other.right.color == true) ){
// Case 2: x's black is black and w 's both child are black
other.color = false;
x = x.p;
continue;
} else if (other.right.color == true) {
// Case 3: transfer to case 4
other.left.color = true;
other.color = false;
leftrotation(other);
other = x.p.right;
}
// Case 4: x's black is black,w's right child is red ,left anyway
other.color = x.p.color;
x.p.color = true;
other.right.color = true;
rightrotation(x.p);
x = root;
break;
}
}
}
}
