/* aufgabe 23 */
#define FEHLER 1000
#include <stdio.h>
static insert_baum_000000_co();
static print_baum_000000_co();
static delete_baum_000000_co();
struct knoten {
struct knoten *links;
struct knoten *rechts;
int wert;
int rang;
};
#define RECHTERNACHFOLGERSCHWARZ(a) \
( ((*a) -> rechts == NULL) || \
((*a)->rechts->rang < ((*a)->rang)) )
#define LINKERNACHFOLGERSCHWARZ(a) \
( ((*a) -> links == NULL) || \
((*a)->links->rang < ((*a)->rang)) )
struct knoten *new_knoten(int wert)
{
struct knoten *hilf;
hilf = (struct knoten *) calloc(1,sizeof(struct knoten));
if (hilf == NULL)
return hilf;
hilf -> links = NULL;
hilf -> rechts = NULL;
hilf -> wert = wert;
hilf -> rang = 0;
return hilf;
}
delete_baum_000000(struct knoten **wurzel, int wert)
// rueckgabe 0 = ohne fehler
// 2 = wert war nicht drin
// FEHLER sonst
{
return delete_baum_000000_co(NULL,wurzel,wert);
}
static delete_baum_000000_co(
struct knoten **papa,
struct knoten **wurzel,
int wert)
{
int res;
struct knoten **neu;
struct knoten **bruder;
if (*wurzel == NULL) /* wert nicht gefunden */ return 2;
// suchen
if ((*wurzel) ->wert == wert) // gefunden
{
struct knoten *zeiger;
if (
(papa != NULL) &&
(((*wurzel) ->rechts) == NULL) &&
(((*wurzel) ->links) == NULL) &&
(((*papa)->rang) == 1)
)
// es wird ein schwarzes blatt geloescht
// das gibt ein rang problem
{
free(*wurzel);
*wurzel = NULL;
return 1;
}
else if (
(((*wurzel) ->rechts) == NULL) &&
(((*wurzel) ->links) == NULL)
)
// es wird ein rotes blatt geloescht
// oder die alleinige wurzel
{
free(*wurzel);
*wurzel = NULL;
return 0; // fertig
}
else if ( (((*wurzel) ->links) == NULL))
// vater eines blattes
{
zeiger = (*wurzel) ->rechts;
free(*wurzel);
*wurzel = zeiger;
return 0; // fertig
}
else if ( (((*wurzel) ->rechts) == NULL))
// vater eines blattes
{
zeiger = (*wurzel) ->links;
free(*wurzel);
*wurzel = zeiger;
return 0; // fertig
}
// es muss der austausch wert gefunden werden
zeiger = (*wurzel) ->rechts;
while (zeiger != NULL)
{
wert = zeiger->wert;
zeiger = zeiger->links;
}
(*wurzel) ->wert = wert; // der austausch;
neu = & ((*wurzel) ->rechts);
}
else if ((*wurzel) ->wert > wert) {
neu = & ((*wurzel) ->links);
}
else {
neu = & ((*wurzel) ->rechts);
}
res = delete_baum_000000_co( wurzel, neu,wert);
#define RANG(a) (((*a) == NULL) ? -1 : ((*a)->rang))
if (res == 2) return 2;
if (res == 0) return 0;
if (res == FEHLER) return FEHLER;
if (wurzel == NULL) return 0; // leerer baum
// hier werden die rangstoerungen behoben
// zwischen neu und wurzel muss sie liegen
if ((RANG(wurzel) - RANG(neu)) == 1) return 0;
/* in der rekursion muss nicht weiter gemacht werden */
if ((RANG(wurzel) - RANG(neu)) != 2)
{
return FEHLER; // sollte nicht sein
}
// zuerst der fall dass sich die rangstoerung fortsetzt
// d.h. es gibt zu neu keinen roten bruder
// und der schwarze bruder hat keine roten nachfolger
// bruder zeiger
bruder = ( neu == &((*wurzel)->links) ) ? &((*wurzel)->rechts) : &((*wurzel)->links) ;
// bruder kann nicht der nullzeiger sein
if (bruder == NULL) {
return FEHLER; // sollte nicht sein
}
if (RANG(bruder) < RANG(wurzel))
if (RANG(bruder) > RANG(& ((*bruder)->rechts)))
if (RANG(bruder) > RANG(& ((*bruder)->links)))
{(*wurzel)->rang --; return 1;}
// das war der einfache fall, dass sich die rangerniedrigung fortsetzt
// alle anderen faelle werden hier geloest und die delete routine mit return 0 beendet
#define BRUDERRECHTSROT() (( neu == &((*wurzel)->links) ) && (RANG(wurzel) == RANG(& ((*wurzel)->rechts))))
#define BRUDERLINKSROT() (( neu == &((*wurzel)->rechts) ) && (RANG(wurzel) == RANG(& ((*wurzel)->links))))
if (BRUDERRECHTSROT()) { rot_links(wurzel);
papa = wurzel;
wurzel = & ((*wurzel)->links);
bruder = & ((*wurzel)->rechts);
}
else if (BRUDERLINKSROT()) { rot_rechts(wurzel);
papa = wurzel;
wurzel= & ((*wurzel)->rechts);
bruder = & ((*wurzel)->links);
}
// die rangdifferenz besteht immer noch
// der (neue) bruder ist jetzt schwarz und kein blatt (wg rang)
if (bruder == NULL) {
return FEHLER; // sollte nicht sein
}
#define OHNEROTEBRUEDER(a) ( (RANG(a) > RANG(& ((*a)->links) )) && (RANG(a) > RANG(& ((*a)->rechts))))
#define ZWEIROTEBRUEDER(a) ( (RANG(a) == RANG(& ((*a)->links) )) && (RANG(a) == RANG(& ((*a)->rechts))))
#define LINKERROTEBRUEDER(a) ( (RANG(a) == RANG(& ((*a)->links) )) )
#define RECHTERROTEBRUEDER(a) ( (RANG(a) == RANG(& ((*a)->rechts) )) )
// printf("rangstoerung teil 2\n");
// jetzt nur noch faelle wo der bruder schwarz ist
// der rang der wurzel wird erniedrigt
((*wurzel) -> rang) --;
if (neu == &((*wurzel)->links))
{
if (OHNEROTEBRUEDER(bruder))
{
return 0;
}
if (ZWEIROTEBRUEDER(bruder))
{
rot_links(wurzel); // fertig
((*wurzel) -> rang) ++;
return 0;
}
if (LINKERROTEBRUEDER(bruder))
{
doppel_rot_rechtslinks(wurzel); // fertig
((*wurzel) -> rang) ++;
return 0;
}
if (RECHTERROTEBRUEDER(bruder))
{
rot_links(wurzel); // fertig
((*wurzel) -> rang) ++;
return 0;
}
} else {
if (OHNEROTEBRUEDER(bruder))
{
return 0;
}
if (ZWEIROTEBRUEDER(bruder))
{
rot_rechts(wurzel); // fertig
((*wurzel) -> rang) ++;
return 0;
}
if (RECHTERROTEBRUEDER(bruder))
{
doppel_rot_linksrechts(wurzel); // fertig
((*wurzel) -> rang) ++;
return 0;
}
if (LINKERROTEBRUEDER(bruder))
{
rot_rechts(wurzel); // fertig
((*wurzel) -> rang) ++;
return 0;
}
}
}
insert_baum_000000(struct knoten **wurzel, int wert)
// rueckgabe 0 = ohne fehler
// 2 = war schon drin
// FEHLER sonst
{
return insert_baum_000000_co(NULL,NULL,wurzel,wert);
}
static insert_baum_000000_co(
struct knoten **opa,
struct knoten **papa,
struct knoten **wurzel,
int wert)
{
int res;
struct knoten **neu;
if (*wurzel == NULL)
/* der baum ist noch leer */
{
*wurzel = new_knoten(wert);
if (*wurzel == NULL)
return FEHLER;
return 1;
}
if ((*wurzel) ->wert == wert) return 2; // schon da;
if ((*wurzel) ->wert > wert)
neu = & ((*wurzel) ->links);
else if ((*wurzel) ->wert < wert)
neu = & ((*wurzel) ->rechts);
res = insert_baum_000000_co( papa, wurzel, neu,wert);
if (res == 0) return 0; // keine rang korrektur mehr
if (res == 2) return 2; // schon da
if (res == FEHLER) return FEHLER; // Fehler
if (res == 1) // rang ueberpruefung
{
if (papa == NULL) return 0;
if ((*papa)->rang != (*neu)->rang) return 1; // hier keine korrektur
/* rotation rechts */
if (
RECHTERNACHFOLGERSCHWARZ(papa) && RECHTERNACHFOLGERSCHWARZ(wurzel)
)
return rot_rechts(papa);
/* rotation links */
if (
LINKERNACHFOLGERSCHWARZ(papa) && LINKERNACHFOLGERSCHWARZ(wurzel)
)
return rot_links(papa);
/* doppel links rechts */
if (
RECHTERNACHFOLGERSCHWARZ(papa) && LINKERNACHFOLGERSCHWARZ(wurzel)
)
return doppel_rot_linksrechts(papa);
/* doppel rechts links */
if (
LINKERNACHFOLGERSCHWARZ(papa) && RECHTERNACHFOLGERSCHWARZ(wurzel)
)
return doppel_rot_rechtslinks(papa);
/* sonst rangerhoehung */
(*papa)->rang ++;
return 1;
}
// kann nicht sein
}
print_baum_000000(struct knoten *wurzel)
{
print_baum_000000_co(wurzel,0);
printf("\n");
}
static print_baum_000000_co(struct knoten *wurzel,int level)
{
int i;
if (wurzel != NULL)
{
print_baum_000000_co(wurzel->links,level+1);
for (i=0;i<3*level;i++) printf(" ");
printf("(%d:%d:%d \n",level,wurzel->rang,wurzel->wert);
print_baum_000000_co(wurzel->rechts,level+1);
}
}
free_baum_000000(struct knoten *wurzel)
{
if (wurzel != NULL)
{
free_baum_000000(wurzel->links);
free_baum_000000(wurzel->rechts);
free(wurzel);
}
}
rot_rechts(struct knoten **wurzel)
{
int wert;
struct knoten * hilf;
if (*wurzel == NULL) return FEHLER;
wert =(*wurzel)->wert;
hilf = *wurzel;
*wurzel = (*wurzel)->links;
hilf->links = (*wurzel)->rechts;
(*wurzel)->rechts = hilf;
return 0;
}
rot_links(struct knoten **wurzel)
{
int wert;
struct knoten * hilf;
if (*wurzel == NULL) return FEHLER;
wert =(*wurzel)->wert;
hilf = *wurzel;
*wurzel = (*wurzel)->rechts;
hilf->rechts = (*wurzel)->links;
(*wurzel)->links = hilf;
return 0;
}
doppel_rot_linksrechts(struct knoten **wurzel)
{
int wert;
struct knoten * hilf;
if (*wurzel == NULL) return FEHLER;
wert =(*wurzel)->wert;
if ( (*wurzel)->links == NULL) return FEHLER;
hilf = (*wurzel)->links->rechts;
(*wurzel)->links->rechts = hilf->links;
hilf->links = (*wurzel)->links;
(*wurzel)->links = hilf->rechts;
hilf->rechts = (*wurzel);
*wurzel = hilf;
return 0;
}
doppel_rot_rechtslinks(struct knoten **wurzel)
{
int wert;
struct knoten * hilf;
if (*wurzel == NULL) return FEHLER;
wert =(*wurzel)->wert;
if ( (*wurzel)->rechts == NULL) return FEHLER;
hilf = (*wurzel)->rechts->links;
(*wurzel)->rechts->links = hilf->rechts;
hilf->rechts = (*wurzel)->rechts;
(*wurzel)->rechts = hilf->links;
hilf->links = (*wurzel);
*wurzel = hilf;
return 0;
}
main()
{
struct knoten *wurzel = NULL,*z;
int i,wert;
int n;
// scanf("%d",&n);
for (i=0;i<1000;i++)
insert_baum_000000(&wurzel,rand()%1000);
print_baum_000000(wurzel);
for (i=0;i<1000;i++)
{
//wert =i;
//printf("delete wert = %d\n",wert);
delete_baum_000000(&wurzel,rand()%1000);
}
print_baum_000000(wurzel);
free_baum_000000(wurzel);
}