Drzewa czerwono-czarne - wstawianie.

0

Witam,
mam problem z implementacją algorytmu drzew czerwono-czarnych. Albo źle wpisuje i nie korzysta z Left, Right Rotate, albo w ogóle nie wstawia do drzewa. Prosiłbym o pomoc oraz wskazówki jeśli ktoś ma pojęcie o co może chodzić.

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

#define RED 1
#define BLACK 0
#define SZER_EKR 80
#define IL_POZ 5

typedef struct drzewo *Wskwezel;
typedef struct drzewo {
  int liczba, kolor;
  Wskwezel left, right, p;
} drzewo;

Wskwezel nil;
Wskwezel korzen;

void nilInit(void){
  nil = (Wskwezel) malloc(sizeof(drzewo));
  nil->p = NULL;
  nil->kolor = BLACK;
  nil->left = NULL;
  nil->right = NULL;
}

void drukuj(Wskwezel w);
void drukujDot(Wskwezel r);

char wydruk[IL_POZ+1][SZER_EKR];

void drukujost(Wskwezel w, int l, int p, int poziom){
  int srodek = (l+p)/2;
  
  if(w==nil)
    return;
  
  wydruk[poziom][srodek]='*';
}

void drukujwew(Wskwezel w, int l, int p, int poziom){
  int srodek = (l+p)/2;
  int i, dl;
  char s[19];

  if(w==nil)
    return;
  if(w->kolor == BLACK)
    dl=sprintf(s, "%d", w->liczba);
  else
    dl=sprintf(s, "%+d", w->liczba);
  for (i=0;i<dl;i++)
    wydruk[poziom][srodek-dl/2+i]=s[i];
  if (++poziom<IL_POZ){
    drukujwew(w->left,l,srodek,poziom) ;
    drukujwew(w->right,srodek+1,p,poziom) ;
  }
  else {
    drukujost(w->left,l,srodek,poziom) ;
    drukujost(w->right,srodek+1,p,poziom) ;
  }
}

void drukuj(Wskwezel w){
  int i, j;

  for(i=0;i<=IL_POZ;i++)
    for(j=0;j<SZER_EKR;j++)
      wydruk[i][j] = ' ';
  drukujwew(w, 0, SZER_EKR, 0);
  for(i=0;i<=IL_POZ;i++){
    for(j=0;j<SZER_EKR;j++)
      putchar(wydruk[i][j]);
    printf("\n");
  }
}

void drukujKrawedz(FILE *plikwy, Wskwezel r, int z, Wskwezel syn, int zs){
  if(syn == nil){
    fprintf(plikwy, "%d [shape=circle, style=invisible, label=\"", zs);
    fprintf(plikwy, "%d ", 0);
    fprintf(plikwy, "\"]\n");
    fprintf(plikwy, "%d -- %d [style=invis];\n ", z, zs);
  } 
  else {
    if(syn->kolor == RED)
      fprintf(plikwy, "%d [shape=circle, color=red, label=\"", zs);
    else
      fprintf(plikwy, "%d [shape=circle, color=black, label=\"", zs);
    fprintf(plikwy, "%d ", syn->liczba);
    fprintf(plikwy, "\"]\n");
    fprintf(plikwy, "%d -- %d ;\n", z, zs);
  }
}

int rekDrukujDot(Wskwezel r, int z, FILE *plikwy){
  int nz, i;
  if(r == nil) 
    return z;
  else {
    drukujKrawedz(plikwy, r, z, r->left, z+1);
    nz = rekDrukujDot(r->left, z+1, plikwy);
    drukujKrawedz(plikwy, r, z, r->right, nz+1);
    nz = rekDrukujDot(r->right, nz+1, plikwy);
    return nz;
  }
}

void drukujDot(Wskwezel r){
  // dot -Tpdf -O drzewo1.gv" ---> drzewo1.gv.pdf

  static int gdzie=0;
  FILE *plikwy;
  if(gdzie){
    plikwy=fopen("drzewo1.gv", "w");
    gdzie=0;
  }
  else {
    plikwy=fopen("drzewo0.gv", "w");
    gdzie=1;
  }

  fprintf(plikwy, "graph drzewo{\n");
  fprintf(plikwy, "size = \"20,200\"");
  
  if(r!=nil){
    if(r->kolor == RED)
      fprintf(plikwy, "%d [shape=circle, color=red, label=\"", 0);
    else
      fprintf(plikwy, "%d [shape=circle, color=black, label=\"", 0);
    fprintf(plikwy, "%d ", r->liczba);
    fprintf(plikwy, "\"]\n");
  }
  fprintf(plikwy, "}\n");
  fclose(plikwy);
  printf("wydrukowane drzewo%d.gv\n", (gdzie +1)%2);
}

// funkcje z algorytmu

void Left_Rotate(Wskwezel T, Wskwezel x){
  Wskwezel y;

  y=x->right;
  x->right = y->left;
  if(y->left != nil)
    y->left->p = x;
  
  y->p = x->p;

  if(x->p == nil)
    T=y;

  else if(x == x->p->left)
    x->p->left = y;

  else
    x->p->right = y;
  y->left = x;
  x->p = y;
}

void Right_Rotate(Wskwezel T, Wskwezel x){
  Wskwezel y;
  
  y=x->left;
  x->left = y->right;
  
  if(y->right != nil)
    y->right->p = x;
  
  y->p = x->p;

  if(x->p == nil)
    T=y;

  else if(x == x->p->left)
    x->p->left = y;
  else
    x->p->right = y;

  y->right = x;
  x->p = y;
}

void RB_Insert_Fixup(Wskwezel T, Wskwezel z){
  Wskwezel y;

  while(z->p->kolor == RED){
    if(z->p == z->p->p->left){
      y = z->p->p->right;
      
      if(y->kolor == RED){
	z->p->kolor = BLACK;
	y->kolor = BLACK;
	z->p->p->kolor = RED;
	z = z->p->p;
      }
      
      else if(z == z->p->right){
	z = z->p;
	Left_Rotate(T, z);
      }
      z->p->kolor = BLACK;
      z->p->p->kolor = RED;
      Right_Rotate(T, z->p->p);
    }

    else {
      y=z->p->p->left;
      if(y->kolor == RED){
	z->p->kolor == RED;
	y->kolor = BLACK;
	z->p->p->kolor = RED;
	z = z->p->p;
      }

      else if(z == z->p->left){
	z = z->p;
	Right_Rotate(T, z);
      }
      z->p->kolor = BLACK;
      z->p->p->kolor = RED;
    }
  }
}

void RB_Insert(Wskwezel T, Wskwezel z){
  Wskwezel x, y;

  y = nil;
  x = T;

  while(x != nil){
    y=x;
    if(z->liczba < x->liczba)
      x = x->left;
    else
      x = x->right;
  }

  z->p = y;
  if(y == nil)
    T=z;
  else if(z->liczba < y->liczba)
    y->left = z;
  else
    y->right = z;
  
  z->left = nil;
  z->right = nil;
  z->kolor = RED;
  RB_Insert_Fixup(T, z);
}

// end funkcje z algorytmu

Wskwezel nowyWezel(int liczba, int kolor){
  Wskwezel w = (Wskwezel) malloc(sizeof(drzewo));
  w->p = nil;
  w->liczba = liczba;
  w->kolor = kolor;
  w->left = w->right = nil;
  return w;
}
  
int main(void) {

  int steruj = 1;
  int liczba;
  Wskwezel temp;
  char wybor;

  nilInit();
  Wskwezel korzen, w38, w31, w22;
  korzen=nil;

  // TESTY ========================================
  w38=nowyWezel(38, BLACK);
  korzen=w38;
  w31=nowyWezel(31, RED);
  RB_Insert(korzen, w31);
  w22=nowyWezel(22, RED);
  RB_Insert(korzen, w22);
  drukuj(korzen);
  
  return 0;
}
0

Zwiększ czytelność kodu, bo tutaj nawet święty miałby trudności z doczytaniem się. Nazywaj w jakiś znaczący sposób zmienne, bo tego się nie da zrozumieć. BTW zamiast define black i red zrób sobie enuma.

1 użytkowników online, w tym zalogowanych: 0, gości: 1