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