public class baum{

public int bh;
public knoten wurzel;
public knoten leer;
public int first=0;

public baum(){

	leer=new knoten();
	leer.setzeRight(leer);
	leer.setzeLeft(leer);
	leer.setzeParent(leer);
	leer.setzeColour(1);
	wurzel=leer;
	int bh=0;
	
}








public void addKnoten(knoten x){
	x.setzeRight(leer);
	x.setzeLeft(leer);
	x.setzeColour(0);
	if(first==0){
		x.setzeParent(leer);
		x.setzeColour(1);
		bh++;
		wurzel=x;
		first=1;
	} else {
		knoten y=wurzel;
		while(true){
			
			if(y.value()>x.value()){
				if(y.left()==leer){
					x.setzeParent(y);
					y.setzeLeft(x);
					if(y.colour()==0){
						repair(x);
					}
					break;
				} else {
					y=y.left();
				}
			} else if(y.value()<x.value()){

				if(y.right()==leer){
					x.setzeParent(y);
					y.setzeRight(x);
					if(y.colour()==0){
						repair(x);
					}
					break;
				} else {
					y=y.right();
				}
			} else if(y.value()==x.value()){
				break;
			}
		}
	
	}
	

}  // end addKnoten

public void rotateRight(knoten top){

	if(top==wurzel){
		wurzel=top.left();
	} 
	top.left().setzeParent(top.parent());
	top.left().right().setzeParent(top);
	top.setzeParent(top.left());
	knoten temp = top.left().right();
	top.left().setzeRight(top);
	top.setzeLeft(temp);

	
}

public void rotateLeft(knoten top){


	if(top==wurzel){
		wurzel=top.right();
	} 
	top.right().setzeParent(top.parent());
	top.right().left().setzeParent(top);
	top.setzeParent(top.right());
	knoten temp = top.right().left();
	top.right().setzeLeft(top);
	top.setzeRight(temp);


}

	



public void repair(knoten neu){

	int hallo=0;
	knoten o;
	while (neu != wurzel & neu.parent().colour() == 0){

		if (neu.parent() == neu.parent().parent().left()) {     // parent und uncle rot, beide schwarz färben, dafür großvater rot färben, und problem weiter hoch geben
			System.out.println("1");
			o = neu.parent().parent().right();
			if (o.colour() == 0) {
				neu.parent().setzeColour(1);
				o.setzeColour(1);
				neu.parent().parent().setzeColour(0);
				neu = neu.parent().parent();
			} else { 					// der onkel ist schwarz
				if (neu == neu.parent().right()) {
					neu = neu.parent();
					rotateLeft(neu);
				}
				neu.parent().setzeColour(1);
				neu.parent().parent().setzeColour(0);
				neu=neu.parent().parent();
				rotateRight(neu);
				neu=wurzel;
				
			}
		} else {     						// parent und uncle rot, beide schwarz färben, dafür großvater rot färben, und problem weiter hoch geben
			if(hallo==0){
				hallo=1;
				System.out.println("2");
			}
			o = neu.parent().parent().left();
			if (o.colour() == 0) {
				neu.parent().setzeColour(1);
				o.setzeColour(1);
				neu.parent().parent().setzeColour(0);
				neu = neu.parent().parent();
			} else { 					// der onkel ist schwarz
				if (neu == neu.parent().left()) {
					neu = neu.parent();
					rotateRight(neu);
				}
				neu.parent().setzeColour(1);
				neu.parent().parent().setzeColour(0);
				neu=neu.parent().parent();
				rotateLeft(neu);
				neu=wurzel;
			}
		}

	
	}
	if(wurzel.colour()==0){
		bh++;
	}
	wurzel.setzeColour(1);
	




} // end repair 




public void deleteKnoten(knoten k) {
	
	if (k == leer) 
	{
	} else {
		rb_Delete(k);
	}
}


public void rb_Delete(knoten z) {
	knoten x, k;
								// k: der physisch entfernte Knoten
								// x: Kind von k
	if (z.left() == leer | z.right()== leer) 
		k = z;
	else 
		k = bs_Successor(z);
	if (k.left()!=leer) 
		x = k.left();
	else 
		x = k.right();
	if (k.parent() == leer) 
		wurzel = x;
	else if (k == k.parent().left())
		k.parent().setzeLeft(x);
	else 
		k.parent().setzeRight(x);
	if (k != z) 
		z.setzeValue(k.value());
								// Nur wenn der gelöschte Knoten
								// Schwarz gefärbt war,
								// muss ausgeglichen werden
	if (k.colour() == 1){
		bh--;
		rb_Delete_Fixup(x);
	}
} 								// Ende rb_Delete



public void rb_Delete_Fixup(knoten x) {
	knoten w;
									// Ausgleich in Richtung Wurzel (Iteration):
	while (x != wurzel & x.colour() == 1)
		if (x == x.parent().left()) {
									// Fallgruppe a ...
			w = x.parent().right();
									// w = Bruder von x
									// Fall (L1): w ist rot
			if (w.colour() == 0) {
				w.setzeColour(1);
				x.parent().setzeColour(0);
				rotateLeft(x.parent());
				w = x.parent().right();
			} 						// Fall (L2/3/4): w ist schwarz
									// Fall (L2): ... und beide Kinder von w
									// sind schwarz
			if(w.left().colour() == 1 & w.right().colour() == 1) {
				w.setzeColour(0);
				x = x.parent();
			} 						// else (d. h. nicht beide Kinder von w
									// sind schwarz)
			else {
									// Fall (L3): w und dessen rechtes Kind
									// sind schwarz, linkes Kind von w ist rot
				if (w.right().colour() == 1) {
					w.left().setzeColour(1);
					w.setzeColour(0);
					rotateRight(w);
					w = x.parent().right();
				} 					// Fall (L4): w ist schwarz und
									// w‘s rechtes Kind rot:
				w.setzeColour(x.parent().colour());
				x.parent().setzeColour(1);
				w.right().setzeColour(1);
				rotateLeft(x.parent());
				x = wurzel; 				// Fast fertig
			}
		} 							// Ende Fallgruppe a


		else { 	// Fallgruppe b: symmetrische Fälle
			// Behandlung analog zu Fallgruppe a
			w = x.parent().left();
									// w = Bruder von x
									// Fall (L1): w ist rot
			if (w.colour() == 0) {
				w.setzeColour(1);
				x.parent().setzeColour(0);
				rotateRight(x.parent());
				w = x.parent().left();
			} 						// Fall (L2/3/4): w ist schwarz
									// Fall (L2): ... und beide Kinder von w
									// sind schwarz
			if(w.right().colour() == 1 & w.left().colour() == 1) {
				w.setzeColour(0);
				x = x.parent();
			} 						// else (d. h. nicht beide Kinder von w
									// sind schwarz)
			else {
									// Fall (L3): w und dessen rechtes Kind
									// sind schwarz, linkes Kind von w ist rot
				if (w.left().colour() == 1) {
					w.right().setzeColour(1);
					w.setzeColour(0);
					rotateLeft(w);
					w = x.parent().left();
				} 					// Fall (L4): w ist schwarz und
									// w‘s rechtes Kind rot:
				w.setzeColour(x.parent().colour());
				x.parent().setzeColour(1);
				w.left().setzeColour(1);
				rotateRight(x.parent());
				x = wurzel; 				// Fast fertig
			}
		}
									// Der zuletzt behandelte Knoten x wird schwarz gefärbt.
									// Dies kann insb. der Wurzelknoten sein
									// ==> Eigenschaft 2 wird sichergestellt
		if(x.colour()==0){
			bh++;
		}
		x.setzeColour(1);
}

public knoten min(knoten x){
	while(x.left()!=leer){
		x=x.left();
	}
	return x;
}


public knoten max(knoten x){
	while(x.right()!=leer){
		x=x.right();
	}
	return x;
}

public knoten bs_Successor(knoten x){
	if(x.right()!=leer){
		return min(x.right());
	}
	knoten y=x.parent();
	while(y!=leer & x==y.right()){
		x=y;
		y=y.parent();
	}
	return y;
}

public void ausgabe(knoten x){
System.out.println(x.value());
System.out.println(x.left().value()+"     "+x.right().value());
}



} // end class