#include <stdio.h>
#include <stdlib.h>

enum farb_typ { rot = 0, schwarz };

typedef struct _knoten{
  int key;
  int farbe;
  int data;
  struct _knoten *links;
  struct _knoten *rechts;
  struct _knoten *vater;
} knoten;

knoten *neu(int key) {
    knoten *neu;
    if ((neu = (knoten*) calloc (1, sizeof(knoten))) == NULL) {
        printf("kann Knoten nicht anlegen\n");
        return;
    }
    neu->key = key;
    neu->farbe=schwarz;
    printf("neuer Knoten mit Schlssel %d\n", key);
    return neu;
}

knoten* onkel(knoten *n){
	if(n!=NULL && n->vater!=NULL && n->vater->vater!=NULL)
	{
		if (!n->vater) return NULL;
		if (n->vater == n->vater->vater->links) return n->vater->vater->rechts;
		else return n->vater->vater->links;
	}else return NULL;
}

knoten* grossvater(knoten *n) {
	if(n!=NULL && n->vater!=NULL && n->vater->vater!=NULL)
	{
   		if (!n->vater) return NULL;
   		if (!n->vater->vater) return NULL;
   		return n->vater->vater;
	}else return NULL;
}

knoten* bruder(knoten *n){
	if(n!=NULL && n->vater!=NULL)
	{
   		if (!n->vater) return NULL;
   		if (n == n->vater->links) return n->vater->rechts;
   		else return n->vater->links;
	}else return NULL;
}

knoten *suche(knoten *wurzel, int schluessel)
{
	// sucht den Knoten mit dem Schlssel "schluessel" im Suchbaum mit der Wurzel "wurzel"
	knoten *aktuell = wurzel;

	printf("Suche nach %d: ", schluessel);

	while (aktuell != NULL)
	{
	    printf("%d,", aktuell->key);
		if (schluessel < aktuell->key) aktuell = aktuell->links;
		else if (schluessel > aktuell->key) aktuell = aktuell->rechts;
		else if (aktuell->key == schluessel) 
		{
         		printf("\n");
		   	return aktuell;
        	}
	}
	return NULL;
}

void linksrotation(knoten *n)
{
	knoten *x=n;
	knoten *y=x->rechts;
	knoten *alpha=x->links;	
	knoten *beta=y->links;
	knoten *gamma=y->rechts;
	knoten *vatervonx=x->vater;

printf("Linkssrotation an %d\n", n->key);

	// Als erstes das Kind des Vaters von n ermitteln:
	if(vatervonx!=NULL)
	{
		if(n==vatervonx->links) vatervonx->links=y;
		else vatervonx->rechts=y;
	}

	// y vorbereiten:
	y->vater=vatervonx;
	y->rechts=gamma;
	y->links=x;
	
	// x vorbereiten:
	x->vater=y;
	x->links=alpha;
	x->rechts=beta;
	
	// Vater von alpha, beta, gamma:
	if(alpha!=NULL) alpha->vater=x;
	if(beta!=NULL) beta->vater=x;
	if(gamma!=NULL) gamma->vater=y;



/*

	knoten *r = n->vater;
	knoten *teilbaum1 = r->links;
	knoten *teilbaum2 = n->links;
	knoten *teilbaum3= n->rechts;
	knoten *grossvater = r->vater;

    printf("Linkssrotation an %d\n", n->key);

	r->links = teilbaum1;
printf("a,");
	r->rechts = teilbaum2;
printf("b,");
	teilbaum1->vater = r;
printf("b,");
	teilbaum2->vater = r;
printf("c,");
	n->links = r;
printf("d,");
	r->vater = n;
printf("e,");
	n->rechts = teilbaum3;
printf("f,");
	teilbaum3->vater = n;
printf("g,");
	n->vater = grossvater;
printf("h,");
	if (grossvater->links == r) 
	{
		printf("i,");
		grossvater->links = n;
	}
	else grossvater->rechts=n;
printf("j\n");
*/
}

void rechtsrotation(knoten *n)
{

	knoten *y=n;
	knoten *x=y->links;
	knoten *alpha=x->links;	
	knoten *beta=x->rechts;
	knoten *gamma=y->rechts;
	knoten *vatervony=y->vater;

printf("Rechtsrotation an %d\n", n->key);

	// Als erstes das Kind des Vaters von n ermitteln:
	if(vatervony!=NULL)
	{
		if(n==vatervony->links) vatervony->links=x;
		else vatervony->rechts=x;
	}

	// x vorbereiten:
	x->vater=vatervony;
	x->links=alpha;
	x->rechts=y;

	// y vorbereiten:
	y->vater=x;
	y->links=beta;
	y->rechts=gamma;
	
	// Vater von alpha, beta, gamma:
	if(alpha!=NULL) alpha->vater=x;
	if(beta!=NULL) beta->vater=y;
	if(gamma!=NULL) gamma->vater=y;


/*	knoten *r = n->vater;
	knoten *teilbaum1 = n->links;
	knoten *teilbaum2 = n->rechts;
	knoten *teilbaum3= r->rechts;
	knoten *grossvater = r->vater;

    printf("Rechtsrotation an %d\n", n->key);
	r->links = teilbaum2;
	r->rechts = teilbaum3;
	teilbaum2->vater = r;
	teilbaum3->vater = r;
	n->rechts = r;
	r->vater = n;
	n->links=teilbaum1;
	teilbaum1->vater = n;
	n->vater = grossvater;
	if(grossvater->links == r) grossvater->links = n;
	else grossvater->rechts = n;
*/
}

void aufraeumen(knoten *n)
{
	knoten *deronkel = onkel(n);
	knoten *dergrossvater = grossvater(n);
	knoten *vater = n->vater;

    printf("Aufraeumen\n");
    
	if(n->vater == NULL){
		// 1. Fall:
		n->farbe = schwarz; 
		printf("1/");
                return;
	}
	else{
		// 2. Fall:
		if (vater->farbe == schwarz) 
		{
			printf("2,");
			return;
		}
		else{
			// 3. Fall:
			if( (deronkel != NULL) && (deronkel->farbe == rot) ){
				printf("3,");
				vater->farbe = schwarz;
				deronkel->farbe = schwarz;
				dergrossvater->farbe = rot;
				aufraeumen(dergrossvater);
			}
			else{
				// 4. Fall:
				if( (n == vater->rechts) && (vater == dergrossvater->links) ){
					printf("4a,");
					linksrotation(vater);
					// mache alten Vater zum aktuellen Knoten fr 5. Fall
					n=n->links;
					deronkel = onkel(n);
					dergrossvater = n->vater->vater;
					vater=n->vater;
				}else if( (n == vater->links) && (vater == dergrossvater->rechts) ){
					printf("4b,");
					rechtsrotation(vater);
					// mache alten Vater zum aktuellen Knoten fr 5. Fall
					n = n->rechts;
					deronkel = onkel(n);
					dergrossvater = n->vater->vater;
					vater = n->vater;
				}

				// 5. Fall:
				printf("5,");
				vater->farbe = schwarz;
				dergrossvater->farbe = rot;
				if( (n == vater->links) && (vater == dergrossvater->links) )
					rechtsrotation(dergrossvater);
				else linksrotation(dergrossvater);
			}
		}
	}

}// Ende Aufr�men

void einfuegen(knoten *wurzel, knoten* neuerknoten)
{
	// fgt den Knoten neuerknoten in den Red-Black Tree mit Wurzel "wurzel" ein
	knoten *aktuell = wurzel;
	knoten *vorgaenger = wurzel;
	while (aktuell != NULL)
	{
		vorgaenger = aktuell;
		if (neuerknoten->key < aktuell->key) aktuell = aktuell->links;
		else if (neuerknoten->key > aktuell->key) aktuell = aktuell->rechts;
		else if (aktuell->key == neuerknoten->key) return;
	}

	if (neuerknoten->key < vorgaenger->key) {
            vorgaenger->links = neuerknoten;
            printf("%d links von %d eingefgt\n", neuerknoten->key, vorgaenger->key);
            
        }
	else if (neuerknoten->key > vorgaenger->key) {
           vorgaenger->rechts = neuerknoten;
            printf("%d rechts von %d eingefgt\n", neuerknoten->key, vorgaenger->key);
        }
	neuerknoten->vater = vorgaenger;
	neuerknoten->farbe = rot;
	aufraeumen(neuerknoten);
}


void aufraeumen_entfernen(knoten *nachfolger)
{
	printf("Aufraeumen_entfernen");
	// Fall 3a:
	if(nachfolger->vater == NULL) return;
	else{
		// Fall 3b:
		if(bruder(nachfolger)->farbe == rot){
			nachfolger->vater->farbe = rot;
			bruder(nachfolger)->farbe = schwarz;
			if(nachfolger->vater->links == nachfolger) linksrotation(nachfolger->vater);
			else rechtsrotation(nachfolger->vater);
		}

		// Fall 3c:
		if( (nachfolger->vater->farbe == schwarz) &&
			(bruder(nachfolger)->farbe == schwarz) &&
			(bruder(nachfolger)->links->farbe == schwarz) &&
			(bruder(nachfolger)->rechts->farbe == schwarz) ){
			bruder(nachfolger)->farbe = rot;
			aufraeumen_entfernen(nachfolger->vater);
		}
		else{
			// Fall 3d:
			if( (nachfolger->vater->farbe == rot) &&
				(bruder(nachfolger)->farbe == schwarz) &&
				(bruder(nachfolger)->links->farbe == schwarz) &&
				(bruder(nachfolger)->rechts->farbe == schwarz) ){
				bruder(nachfolger)->farbe = rot;
				nachfolger->vater->farbe = schwarz;
			}
			else{
				// Fall 3e:
				if( (nachfolger->vater->links == nachfolger) &&
					(bruder(nachfolger)->farbe == schwarz) &&
					(bruder(nachfolger)->links->farbe == rot) &&
					(bruder(nachfolger)->rechts->farbe == schwarz) ){
					bruder(nachfolger)->farbe = rot;
					bruder(nachfolger)->links->farbe = schwarz;
					rechtsrotation(bruder(nachfolger));
				}
				else if( (nachfolger->vater->rechts == nachfolger) &&
					(bruder(nachfolger)->farbe == schwarz) &&
					(bruder(nachfolger)->links->farbe == schwarz) &&
					(bruder(nachfolger)->rechts->farbe == rot) ){
					bruder(nachfolger)->farbe = rot;
					bruder(nachfolger)->rechts->farbe = schwarz;
					linksrotation(bruder(nachfolger));
				}

				// Fall 3f:
				bruder(nachfolger)->farbe = nachfolger->vater->farbe;
				nachfolger->vater->farbe = schwarz;

				if(nachfolger->vater->links == nachfolger){
					bruder(nachfolger)->rechts->farbe = schwarz;
					linksrotation(nachfolger->vater);
				}
				else{
					bruder(nachfolger)->links->farbe = schwarz;
					rechtsrotation(nachfolger->vater);
				}
			}
		}
	}
}

void entfernen(knoten *wurzel, int schluessel)
{
	// l�cht den Knoten mit dem Schlssel "schluessel" im Baum mit der Wurzel "wurzel".
	// Vorsicht: Es findet keine Freigabe von Speicher statt!
	knoten *nachfolger;
	knoten *loeschen = suche(wurzel, schluessel);
	printf("Löschen: %d (%s)\n", loeschen->key, loeschen->farbe == 0 ? "rot" : "schwarz");

	if(loeschen->links != NULL && loeschen->rechts != NULL)
	{
		// bestimme Ersatzknoten:
		knoten *ersatzknoten = loeschen->rechts; // erst in den rechten Teilbaum von loeschen
		// dann nach links, bis es nicht mehr weitergeht
		while(ersatzknoten->links!=NULL) ersatzknoten = ersatzknoten->links;
		printf("Ersatzknoten: %d (%s)\n", ersatzknoten->key, ersatzknoten->farbe == 0 ? "rot" : "schwarz");
		// Werte bertragen:
		loeschen->key = ersatzknoten->key;
		loeschen->data = ersatzknoten->data;
		// jetzt den ersatzknoten loeschen:
		loeschen = ersatzknoten;
	}

	// Nominiere einen Nachfolger für den zu löschenden Knoten:
	// Hier kann der Knoten nur noch ein Kind oder gar keine Kinder haben:
	if(loeschen->rechts == NULL) nachfolger=loeschen->links;
	else nachfolger = loeschen->rechts;
	// Den Knoten aushängen, dazu: Enkel auf Großvater
	if(nachfolger!=NULL) nachfolger->vater = loeschen->vater;
	// Und Großvater auf Enkel
	if(loeschen->vater->links == loeschen) loeschen->vater->links=nachfolger;
	else loeschen->vater->rechts = nachfolger;
	printf("1\n");
	if(loeschen->farbe == schwarz)
	{
		if(nachfolger!=NULL)
		{
			printf("2\n");
			if(nachfolger->farbe == rot) nachfolger->farbe = schwarz;
			else aufraeumen_entfernen(nachfolger);
		}
	}
}

void printtree(knoten *node)
{
    printf("%d (%s)\n", node->key, node->farbe == 0 ? "rot" : "schwarz");
   /* if(node->links == NULL && node->rechts == NULL) {
       return;
    }*/
	printf("Gehe nach links.\n");
    if (node->links != NULL)
{
	
       printtree(node->links);
	
}
printf("Back aus links\n");
printf("Gehe nach rechts\n");
    if (node->rechts != NULL)
	{
	
       printtree(node->rechts);
	
}
printf("Back aus rechts\n");
}

int main (int argc, char **argv)
{
   knoten *wurzel, *node;

   wurzel = neu(10);
   einfuegen(wurzel, neu(5));
   einfuegen(wurzel, neu(11));
   einfuegen(wurzel, neu(6));
   einfuegen(wurzel, neu(8));
   einfuegen(wurzel, neu(15));
   einfuegen(wurzel, neu(3));
   einfuegen(wurzel, neu(20));
   einfuegen(wurzel, neu(4));
   einfuegen(wurzel, neu(14));
   einfuegen(wurzel, neu(17));

   suche(wurzel, 3);
   suche(wurzel, 5);
   suche(wurzel, 20);
   suche(wurzel, 4);
printf("\n");
printf("Löschen:\n");
printf("--------------\n");
	entfernen(wurzel, 17);

printf("\n");
   printtree(wurzel);

}