#include <stdio.h>

#include <conio.h>

static struct node{

int key,info,red;

struct node *l,*r;

};

static struct node *head,*z,*gg,*g,*p,*x,*gc1;

int i1=0;

void plirofories( );

void menu( );

void rbtreeinitialize( );

struct node *rotate(int,struct node *);

void split(int);

void rbtreeinsert(int);

void rbtreesearch(int);

void rbtreeprint(struct node *,int);

void rbtreeprint2(struct node *,int);

main( )

{

int v,info,num,j;

char c;

clrscr( );

plirofories( );

gotoxy(22,24); printf("Πατήστε ένα πλήκτρο για συνέχεια");

getch( ); clrscr( );

/* Πρώτα γίνεται αρχικοποίηση των δεικτών του δέντρου. */

rbtreeinitialize( );

/* Εμφάνιση του μενού επιλογών και επιλογή αριθμού από το πληκτρολόγιο

για τη διεργασία που θα ακολουθηθεί από το πρόγραμμα. */

menu( );

c=getch( );

/* Το πρόγραμμα τερματίζεται με τον αριθμό 0. Όσο είναι διαφορετικό

εκτελείται συνεχώς. */

while (c!='0') {

/* Πρόταση ελέγχου πολλαπλής επιλογής */

switch(c) {

/* Επιλογή 1η: Εισάγει στο κόκκινο-μαύρο δέντρο νέα στοιχεία. */

case '1': { clrscr( );

printf(" Δώστε τον αριθμό των νέων στοιχείων που θα εισαχθούν :");

scanf(" %d",&num);

for(j=1; j<=num; j++) {

printf(" Δώσε τον%2dο ακέραιο αριθμό εισαγωγής: ",j);

scanf(" %d",&v);

rbtreeinsert(v);

/* Δίνουμε αρχική τιμή στην i1=0 ,για να μετράει τις γραμμές που εκτυπώνονται

και να περιμένει συνέχεια από τον χρήστη .Η μεταβλητή gc1 παίρνει την τιμή του

δείκτη που δείχνει πριν από την αρχή του δέντρου ,διότι είναι βοηθητική

i1=0; gc1=head;

rbtreeprint2(head->r,0);

}

gotoxy(1,24);

printf("\n Πατήστε ένα πλήκτρο για συνέχεια");

getch( );

}

break;

/* Επιλογή 2η: Αναζήτηση ενός κλειδιού μέσα στο δέντρο. */

case '2': {clrscr( );

printf(" Δώστε τον ακέραιο αριθμό του κλειδιού αναζήτησης: ");

scanf(" %d",&v);

clrscr( );

/* Εδώ η gc1 παίρνει την τιμή του δείκτη που δείχνει στην κορυφή του δέντρου

και καθώς κάνει την αναζήτηση μέσα στο δέντρο κάθε τόσο αλλάζει τιμή . */

gc1=head->r; i1=0;

rbtreesearch(v);

getch( );

}

break;

/* Επιλογή 3η: Εμφάνιση των στοιχείων του δέντρου. */

case '3': {clrscr( );

gotoxy(25,2); printf("ΕΜΦΑΝΙΣΗ RED-BLACK TREE\n");

i1=0; rbtreeprint(head->r,0);

gotoxy(1,24);

printf("\n Πατήστε ένα πλήκτρο για συνέχεια");

getch( );

}

break;

}

/* Καθαρισμός της οθόνης και επανεμφάνιση του μενού επιλογών για νέα επιλογή.*/

clrscr( ); menu( ); c=getch( );

}

}

void plirofories( )

{

gotoxy(20,2);

printf("Κόκκινα-Μαύρα Δέντρα (Red-Black Trees) \n\n\n");

printf("\n (δηλ. δέντρα που έχουν 1 ή 2 ή 3 κλειδιά και 2 ή 3 ή 4 κόμβους παιδιά) \n");

printf("\n και οφείλουν το όνομα τους στην εξής σύμβαση. Οι δενδρικοί δείκτες \n");

printf("\n που ξεκινούν από κόμβους με ένα κλειδί είναι μαύροι, ενώ οι δείκτες \n");

printf("\n κόκκινοι. Αυτό που παρατηρείται είναι ότι όλα τα μονοπάτια προς \n");

printf("\n τα φύλλα έχουν τον ίδιο αριθμό μαύρων δεικτών, ενώ επίσης δεν είναι \n");

printf("\n δυνατόν να υπάρχουν δύο διαδοχικοί κόκκινοι δείκτες. \n");

}

/* Η συνάρτηση αυτή τυπώνει στην οθόνη το μενού επιλογών . */

void menu( )

{

gotoxy(23,5); printf(" 1. Εισαγωγή Στοιχείων R_B_Tree");

gotoxy(23,7); printf(" 2. Αναζήτηση στο R_B_Tree");

gotoxy(23,9); printf(" 3. Εμφάνιση του R_B_Tree");

gotoxy(31,14); printf(" ΕΠΙΛΟΓΗ: ");

}

/* Η συνάρτηση αυτή κάνει την αρχικοποίηση των δεικτών και δίνει αρχικές

τιμές στι μεταβλητές που περιέχονται στην δομή τύπου node . */

void rbtreeinitialize( )

{

/* Η συνάρτηση malloc είναι κατανεμητής μνήμης ,δηλ. ζητάει χώρο στην μνήμη

ανάλογα με τις ανάγκες .Εδώ ζητάει χώρο ίσο με το μέγεθος των μεταβλητών που

περιέχονται στην δομή . */

z=(struct node *) malloc(sizeof *z);

/* Αρχικοποίηση των μεταβλητών της δομής z . */

z->l=z; z->r=z; z->key=0; z->red=0;

head=(struct node *) malloc(sizeof *head);

/* Αρχικοποίηση των μεταβλητών της δομής head . */

head->r=z; head->key=0; head->red=0;

}

/* Η συνάρτηση αυτή επιστρέφει τον δείκτη ο οποίος θα συνδέει τα κλειδιά στα

οποία έγινε ανακατανομή στο δέντρο ,δείχνοντας στην κορυφή εκείνη μετά την

οποία έγινε η εναλλαγή . */

struct node *rotate(int v,struct node *y)

{

struct node *c,*gc;

/* Αν ο νέος αριθμός (κλειδί) εισαγωγής είναι μικρότερος από την κορυφή στο

επίπεδο του δέντρου που καλείται η συνάρτηση ,τότε τοποθετείτε στον δείκτη c

την τιμή που δείχνει στ' αριστερά του ,αλλιώς τοποθετείτε ο δείκτης στα

δεξιά . */

c=(v<y->key) ? y->l:y->r;

/* Αν τώρα ο αριθμός (κλειδί) εισαγωγής είναι μικρότερος από την νέα τιμή του

δείκτη c τότε , */

if (v<c->key) {

/* Τοποθετεί στον δείκτη gc την τιμή που δείχνει στο παιδί του δείκτη c που

βρίσκεται στ' αριστερά του .Κατόπιν ο δείκτης που δείχνει στ' αριστερά του c

παίρνει την τιμή που δείχνει στα δεξιά του αριστερου παδιού του c ,δηλ. στο

δεξί παιδί του νέου gc .Έπειτα κάνει τον δείκτη c να είναι το δεξί παιδί

του gc . */

gc=c->l; c->l=gc->r; gc->r=c; }

else {

/* Τοποθετεί στον δείκτη gc την τιμή που δείχνει στο δεξί παιδί του c .Μετα

κάνει τον δείκτη στα δεξιά του c να πάρει την τιμή του δείκτη που δείχνει

στ' αριστερά του δεξιού παιδιού του δείκτη c .Και μετά κάνει τον δείκτη c να

είναι το αριστερό παιδί του gc . */

gc=c->r; c->r=gc->l; gc->l=c; }

/* Αν ο αριθμός εισαγωγής είναι μικρότερος από την κορυφή που ένα επίπεδο πιο

πάνω από το επίπεδο που βρίσκεται το κλειδί που δείχνει ο δείκτης gc ,τότε

τοποθετείτε στ' αριστερά της κορυφής αυτής ο δείκτης που δείχνει στον gc

διαφορετικά τοποθετείτε στα δεξιά . */

if (v<y->key) y->l=gc;

else y->r=gc;

return gc;

}

/* Η συνάρτηση αυτή κάνει την διάσπαση του δέντρου και είναι αυτή που δημιουργεί

με την βοήθεια της ''rotate'' το ισοζυγισμένο δέντρο με τους κόκκινους και

μαύρους δείκτες . */

void split (int v)

{

/* Όταν καλείται αυτή η συνάρτηση ο δείκτης χ που δείχνει σε κάποιο σημείο

του δέντρου γίνεται αυτόματα κόκκινος και όπως είναι επόμενο οι δείκτες που

δείχνουν εκείνη τη στιγμή στο αριστερό και στο δεξί παιδί ,γίνονται μαύροι .

Αυτό συμβαίνει γιατί δεν είναι δυνατόν να βρεθούν δύο διαδοχικοί κόκκινοι

δείκτες . */

x->red=1; x->l->red=0; x->r->red=0;

/* Αν ο δείκτης που δείχνει στον πατέρα του κλειδιού του <χ> είναι κόκκινος

τότε κάνει τον πατέρα του κλειδιού του <p> κόκκινο . */

if (p->red) {

g->red=1;

/* Αν ισχύει έστω η σχέση ( v<g->key ) η τιμή που επιστρέφει αυτή η συνθήκη

είναι 1 ,διαφορετικά είναι 0 ,ψευδής .Όταν λοιπόν μια από τις δύο σχέσεις δεν

ισχύει τοποθετεί στον δείκτη p την τιμή που δείχνει στην κορυφή κάποιων

κλειδιών μετά την εναλλαγή . */

if (v<g->key != v<p->key)

p=rotate(v,g);

/* Τοποθετεί στον δείκτη χ την τιμή που δείχνει σε κάποια κορυφή του δέντρου

κάτω από την οποία σημειώθηκε η εναλλαγή στο δέντρο . */

x=rotate(v,gg);

/* Συγχρόνως κάνει τον δείκτη του χ μαύρο . */

x->red=0;

}

/* Καθώς τελειώνει η διάσπαση η συνάρτηση αυτή κάνει τον δείκτη της κορυφής

του δέντρου μαύρο .Επειδή στην αρχικοποίηση η μεταβλητή key παίρνει τιμή

μηδέν (0) ,όλα τα κλειδιά που εισάγονται στο δέντρο βρίσκονται μια θέση

δεξιότερα . Δηλ. η κορυφή του δέντρου βρίσκεται στη θέση ''head->r'' και

είναι το κλειδί (αριθμός) , ''head->r->key'' . */

head->r->red=0;

}

/* Συνάρτηση εισαγωγής στοιχείων σε δέντρο RED_BLACK ισοζυγισμένο */

void rbtreeinsert(int v)

{

/* Δίνει στις μεταβλητές x,g,p ως αρχική τιμή την θέση μνήμης στην

οποία βρίσκεται η κορυφή του δέντρου. */

x=head; p=head; g=head;

/* Όσο το χ είναι διάφορο του z δηλ. η διάσχιση του δέντρου δεν έχει φτάσει

στο τέλος και δεν έχει βρεθεί ίδιος αριθμός στο δέντρο ,συνέχισε την διάσχιση. */

while (x!=z && v!=x->key) {

/* Στον δείκτη p τοποθετείτε η τιμή του χ .Δηλ. ο p προχωράει στο δέντρο μέχρι

να βρει το κλειδί (αριθμό) εκείνο μετά το οποίο θα μπει ο νέος αριθμός .Ο

δείκτης g κρατάει κάθε φορά τον πατέρα του p .Και ο δείκτης gg κρατάει την

διεύθυνση που έδειχνε προηγουμένως ο g .*/

gg=g; g=p; p=x;

/* Αν ο αριθμός που δείχνει ο δείκτης χ είναι μικρότερος από τον αριθμό

εισαγωγής τότε τοποθέτησε στον χ τον δείκτη που δείχνει στ' αριστερά του

διαφορετικά αυτόν που δείχνει δεξιά του .*/

x=(v < x->key) ? x->l:x->r;

/* Αν το κλειδί (αριθμός) υπάρχει ήδη τότε δεν κάνει νέα εισαγωγή στο δέντρο.*/

if (v= =x->key)

printf(" Το κλειδί που δώσατε υπάρχει ήδη.\n");

else

/* Αν οι δείκτες που δείχνουν στα παιδιά του δείκτη x είναι και οι δύο

συγχρόνως κόκκινοι ή μαύροι τότε κάνει διάσπαση και ανακατανομή των κορυφών

στο δέντρο .*/

if (x->l->red && x->r->red)

split(v);

}

/* Αν η διάσχιση έχει φτάσει στο τέλος της και δεν έχει βρεθεί το κλειδί μέσα

στο δέντρο τότε ζητάει για τον δείκτη χ που είναι τύπου δομής node ,χώρο στην

μνήμη ίσο με το μέγεθος των μεταβλητών που περιέχονται στην δομή του .*/

if (x= =z && v!=x->key) {

x=(struct node *) malloc(sizeof *x);

/* Τοποθετεί το νέο κλειδί εισαγωγής στο δέντρο κάνοντας τον δείκτη χ να

δείχνει εκεί και ταυτόχρονα αφήνει χώρο στην μνήμη για τους δείκτες που

είναι για το αριστερό και δεξιό παιδί ,όταν θα αποκτήσει .*/

x->key=v; x->l=z; x->r=z;

/* Αν το νέο κλειδί εισαγωγής είναι μικρότερο από το προηγούμενο κλειδί του χ,

τοποθετούμε στ' αριστερά του δείκτη p τον δείκτη χ ,διαφορετικά τον τοποθετούμε

στα δεξιά του .*/

if (v<p->key) p->l=x;

else p->r=x;

/* Αφού τοποθετηθεί το νέο κλειδί στ' αριστερά ή στα δεξιά του δείκτη p ,κάνει

διάσπαση στο δέντρο για να γίνει ισοζυγισμένο και να κάνει τον δείκτη του

κόκκινο ή μαύρο ανάλογα με την θέση του μέσα στο δέντρο .*/

split(v);

}

}

/* Αναζήτηση ενός κλειδιού μέσα στο δέντρο. */

void rbtreesearch(int v)

{ int level=1; /* Βοηθητική μεταβλητή για το επίπεδο του δέντρου */

struct node *gc,*gp; /*Βοηθητικοί δείκτες ,ο gp δείχνει τον γονέα του κλειδιού */

/*Επειδή δίνουμε αρχική τιμή στα κλειδιά <0> η κορυφή βρίσκεται στα δεξιά

του δείκτη κεφάλι(head) */

gc=head->r; /* Αρχική τιμή στον gc την κορυφή του δέντρου */

συγχρόνως ο δείκτης δεν έχει φτάσει στο τέλος του δέντρου */

while (v!=gc->key && gc!=z) {

/*Κρατάει ο δείκτης gp την τιμή του gc προτού αυτός αλλάξει για να δείχνει

πιο είναι το προηγούμενο κλειδί στο δέντρο. Η μεταβλητή level αυξάνεται σε

κάθε έλεγχο για να δείχνει το επόμενο επίπεδο του δέντρου. */

gp=gc; level++;

i1=0;

rbtreeprint2(head->r,0);

/*Ελέγχει αν είναι μικρότερο το κλειδί αναζήτησης και πηγαίνει αριστερότερα

του δέντρου στο επόμενο επίπεδο διαφορετικά πηγαίνει στα δεξιά */

if (v<gc->key) {

gotoxy(28,8);

printf("Το κλειδί %d είναι μικρότερο από το %d.\n",v,gc->key);

gotoxy(28,9); printf("Άρα θα βρίσκεται στ' αριστερά του δέντρου. \n");

gotoxy(28,10);printf("Προχωράμε στο %d επίπεδο του δέντρου ",level);

gc=gc->l; /* Δίνει στον δείκτη τη διεύθυνση που δείχνει αριστερά του */

gc1=gc;

}

else {

gotoxy(28,8);

printf("Το κλειδί %d είναι μεγαλύτερο από το %d. \n",v,gc->key);

gotoxy(28,9); printf("Άρα θα βρίσκεται στα δεξιά του δέντρου. \n");

gotoxy(28,10); printf("Προχωράμε στο %d επίπεδο του δέντρου ",level);

gc=gc->r; /* Δίνει στον δείκτη τη διεύθυνση που δείχνει δεξιά του */

gc1=gc;

}

gotoxy(1,24);

printf("\n Πατήστε ένα πλήκτρο για το επόμενο βήμα ");

getch( ); clrscr( );

} /* while */

/* Ελέγχει αν ο δείκτης έφτασε στο τέλος του δέντρου χωρίς να βρει το κλειδί

που σημαίνει οτι δεν υπάρχει στο δέντρο */

if (gc= =z && v!=gc->key) {

else {

i1=0;

rbtreeprint2(head->r,0);

gotoxy(19,6);

printf(" Το κλειδί αναζήτησης <%d> βρέθηκε στο δέντρο στο %do επίπεδο."

, v,level);

gotoxy(19,8);

/* Ελέγχει αν το κλειδί αναζήτησης είναι ή όχι η κορυφή του δέντρου */

if (gc= =head->r) printf(" Είναι η κορυφή του δέντρου, άρα δεν έχει γονέα.");

gotoxy(19,10);

/* Ελέγχει αν ο δείκτης είναι μαύρος ή κόκκινος */

if (gc->red= =1)

printf(" Ο δείκτης που δείχνει το %d είναι κόκκινος.",gc->key);

else printf(" Ο δείκτης που δείχνει το %d είναι μαύρος.",gc->key);

gotoxy(19,12);

printf(" To κλειδί %d έχει και ως παιδιά του τα κλειδιά :",gc->key);

gotoxy(22,15);

printf("ΑΡΙΣΤΕΡΟ ΠΑΙΔΙ: ");

if (gc->l->key!=0) /*Ελέγχει αν υπάρχει αριστερό παιδί*/

printf("%d",gc->l->key);

else printf("--");

gotoxy(47,15);

printf("ΔΕΞΙ ΠΑΙΔΙ: ");

if (gc->r->key!=0) /* Ελέγχει αν υπάρχει δεξί παιδί */

printf("%d",gc->r->key);

else printf("--");

} /* else */

}

/* Συνάρτηση Αναδρομής για την εμφάνιση του Κόκκινου-Μαύρου Δέντρου */

void rbtreeprint(struct node *x,int level)

{ int i;

/* Ελέγχει αν ο δείκτης χ δείχνει στο τέλος του δέντρου */

if (x!=z) {

if (x->key= =head->r->key) printf("Κορυφή \n");

/* Αφήνει κενά και τυπώνει γραμμές στην εμφάνιση ανάλογα με το επίπεδο που

βρίσκετε στο δέντρο */

for(i=1; i<=level; i++) printf("%2c",179);

/* Τυπώνει το κλειδί στο δέντρο ανάλογα με το επίπεδο στο οποίο βρίσκεται */

printf("%2d",x->key);

for(i=1; i<=(18-2*level); i++) printf(" ");

/* Ελέγχει αν το κλειδί έχει αριστερό παιδί ή όχι */

if (x->l->key= =0)

printf("Aριστερά <ΔΕΝ ΕΧΕΙ>");

else {

/* Ελέγχει αν ο δείκτης που δείχνει στο αριστερό παιδί είναι κόκκινος ή

μαύρος */

if (x->l->red= =1)

printf("Αριστερά =%d<δείκτης κόκκινος>",x->l->key);

else

printf("Αριστερά =%d<δείκτης μαύρος>",x->l->key);

}

/* Ελέγχει αν το κλειδί έχει δεξί παιδί ή όχι */

if (x->r->key= =0)

printf("--Δεξιά<ΔΕΝ ΕΧΕΙ>\n");

else {

/* Ελέγχει αν ο δείκτης που δείχνει στο δεξί κλειδί είναι κόκκινος ή μαύρος*/

if (x->r->red= =1)

printf("--Δεξιά=%d<δείκτης κόκκινος>\n",x->r->key);

}

i1++;

/* Αν τυπωθούν 22 γραμμές περιμένει εντολή από

τον χρήστη για να συνεχίσει. */

if (i1%22= =0) {

i1=0; getch( ); }

rbtreeprint(x->l,level+1);

rbtreeprint(x->r,level+1);

}

}

/* Συνάρτηση Αναδρομής όπου εμφανίζεται το δέντρο στην αναζήτηση ενός

κλειδιού και το σημείο αναζήτησης που βρισκόμαστε μέσα στο δέντρο. */

void rbtreeprint2(struct node *x,int level)

{

int i;

/* Έλεγχος για το τέλος του δέντρου. */

if (x!=z) {

if (x->key==head->r->key) printf("Κορυφή\n");

i1++;

/* Αφήνει κενά και εμφανίζει μια γραμμή η οποία δείχνει το επίπεδο του κάθε

στοιχείου στο δέντρο. */

for(i=1; i<=level; i++)

printf("%2c",179);

printf("%2d",x->key);

/* Ελέγχει αν εμφανιστούν 22 γραμμές στην οθόνη περιμένει να πατηθεί κάποιο

πλήκτρο για να συνεχίσει. */

if (i1%22= =0) {

i1=0; getch( );

}

/* Δείχνει στο δέντρο το σημείο στο οποίο βρίσκεται η αναζήτηση. */

if (x->key= =gc1->key) printf(" %c%c\n",17,16);

else printf("\n");

/* Αναδρομή της συνάρτησης. */

rbtreeprint2(x->l,level+1);

rbtreeprint2(x->r,level+1);

}

}