Random search tree... un pic de ajutor ?

[•tzoky07]

De ceva vreme incerc sa codez un "Random search tree". Documentatie am gasit asa si asa... si multe lucruri nu am reusit sa le inteleg , am cautat si in multe carti si tot cam in bezna ma aflu. Asta e lista de proceduri pe care o am la momentul de fata... dupa 12 ore de lucru, m'am hotarat sa cer ajutor... macar sa reusesc sa inteleg ce e cu el deci, a bit of help, please  

Cod:

typedef struct nod *arb;
struct nod{int inf,pr;arb st,dr;};


void rotst(arb &r) // Se roteste r->dr catre stanga
{arb x = r->dr;
 r->dr = x->st;
 x->st = r;
 r = x;    
 }
 
void rotdr(arb &r) // Se roteste r->st catre dreapta
{arb x = r->st; 
 r->st = x->dr;
 x->dr = r; 
 r = x;
 }

void ordonare(arb &r)
{if (r->pr < r->st->pr)
    rotdr(r);
 if (r->pr > r->dr->pr)
    rotst(r);
  }

void citire(int &x)
{printf ("info : ");
 scanf ("%d",&x);
 }

void nou(arb &r,int x)
{  r = new nod; r->inf = x; r->pr = rand (); r->st = r->dr = NULL;}

void ins(arb &r,int x)
{if (r == NULL)
    nou (r,x);
 if (x < r->inf)
    ins (r->st,x);
 else
 if (x > r->inf)
    ins (r->dr,x);

 }

void afis(arb r)
{if (r != NULL)
    {afis (r->st); printf ("%d (prioritate : %d )\n",r->inf,r->pr); afis (r->dr);}
 }
 
void stergere(arb &r)
{if ((r->st != NULL) && (r->dr != NULL))
    if (r->st->pr > r->pr)
        rotst(r);
    else
        rotdr (r);
else
    delete(r);
        
 }

[•pauldb]

Ai citit acest articol? Mi se pare ca este exact ce cauti si este unul dintre cele mai bine scrise articole pe care le-am citit.

[•tzoky07]

m'am uitat prin ce e acolo, singura problema e ca arborele pare sa aibe probleme la rotatii, cand se face echilibrarea. Inserez radacina, apoi la urmatorul nod apare eroare. Ideea e ca nu imi pot da seama unde anume am gresit. Iarasi, apar mici probleme in procesul de stergere. Uitati secventa de cod :

Pentru insert :

Cod:

void ins(arb &r,int x)
{if (r == NULL)
    nou (r,x);
 if (x < r->inf)
    ins (r->st,x);
 else
 if (x > r->inf)
    ins (r->dr,x);
ordonare(r);
 }

Pentru delete :

Cod:

void stergere(arb &r, int x)
{ if (x > r->inf)
     stergere (r->dr,x);
  else if (x < r->inf)
     stergere (r->st,x);
  else
  {if ((r->st == NULL) && (r->dr == NULL))
      {r == NULL; delete r;}
   else
       {if (r->st->pr > r->dr->pr)
          rotst(r);
        else
           rotdr(r);
        stergere(r,x);
       }
  }  
 }

Procedurile sunt inspirate dupa articolul despre treaps... singura problema e ca logica pare a fi buna. Astfel incat m'am hotarat sa cer sfatul unor experti

[•blasterz]

La stergere ai

 {r == NULL; delete r;}

nu trebuia sa fie r = NULL; ? Nu vad nicio logica sa ai r == NULL;

[•tzoky07]

Pff... da, ai dreptate )... cred ca e de la oboseala. Totusi, nu imi pot da seama de problema de la inserare. Orice parere si/sau solutie e binevenita

[•pauldb]

Dar si asa, daca faci r = NULL si delete r o sa fie un memory leak. Probabil ca tu vrei intai delete r si apoi r = NULL.

Ce faci in functia nou?

[•tzoky07]

nou imi creaza un nod in arbore si seteaza fiul stanga si fiul dreapta ca NULL

Cod:

void nou(arb &r,int x)
{  r = new nod; r->inf = x; r->pr = rand (); r->st = r->dr = NULL; }

si totusi logica pare sa fie buna, problema este ca nu functioneaza corect procedurile de inserare si procedura de stergere ... care sunt inspirate din articol. Eu unu mai am putin si imi arunc laptopu' pe geam 

[•pauldb]

Problema ta apare tot la a doua inserare? Ai incercat sa afisezi arborele dupa ce ai inserat radacina sa vezi daca e in regula?

Posteaza si partea de cod in care apelezi functia de inserare. In functie de ce valori introduci, poate ne dam seama de ce merge prost.

[•tzoky07]

Pai, am mai multe lucruri de spus acum. Un debug mi'a mai lamurit putin mintea dar totusi am nevoie de ajutor ca de aer, poate si din cauza ca peste 2 zile trebuie sa prezint proiectul.
Dupa cum am zis, un debug a fost foarte util si mi'a mai limpezit putin mintea, am descoperit intr-un fel problema la inserare.

Prima data, inserez radacina, apeland :

scanf ("%d",&x) ; nou(r,x) , unde nou creaza un nod in arbore

Dupa aceea, elementele le introduc utilizand in programul principal un While :

While (x != 0)
{scand ("%d",&x); ins(r,x);}

problema apare atunci cand introduc a doua valoare, adica :

Se apeleaza functia ins :

void ins(arb &r,int x)
{if (r == NULL)
    nou (r,x);
 if (x < r->inf)
    ins (r->st,x);
 else
 if (x > r->inf)
    ins (r->dr,x);
ordonare (r);
 }

totul merge bine pana cand se ajunge la "Ordonare (r)"

void ordonare(arb &r)
{if (r->st->pr > r->pr)
    rotdr(r);
 if (r->dr->pr > r->pr)
    rotst(r);
  }

eroarea "Segmentation fault" apare in locul marcat cu rosu si boldit. Cel mai probabil, comparatia nu se face de la radacina, ci de la r-ul din functie (r->st; r->st->dr; etc). Articolul punea functia de ordonare exact in locul in care am plasat-o si eu, iar daca fac ordonare dupa, cum am incercat, arborele nu se echilibreaza cum trebuie.

Oricine are vreo idee, va rog postati. Eu raman la ideea cu aruncatu laptopului. Multumesc pentru asistenta acordata pana acum.   

[•pauldb]

Mie mi se pare suspect ca iti merge sa inserezi si radacina. Functia ordonare nu ar trebui sa se apeleze pentru un subarbore cu un singur nod (adica pentru acel apel al functiei insert in care r e initial NULL). Si in articol exista un return dupa ce se creeaza nodul nou, obligand functia sa se incheie imediat. Motivul pentru care cred ca nu iti functioneaza este ca in linia de cod cu rosu tu apelezi r->st->pr, dar daca r->st e NULL, atunci nu exista pr si e normal sa primesti segmentation fault.

[•toni2007]

Cel mai bine creezi un nod nil, cu ambii fii NULL, si cand creezi un nod ii pui ambii fii nil. Asa nu o sa mai ai probleme cu segmentation fault. Ma rog, dupa trebuie sa ai grija sa nu ajungi pe nil in loc de NULL.

[•tzoky07]

Cu ajutorul vostru, am dat gata procedura de inserare (am mai pus un if sa nu mi se compare cu NULL), deci multumesc voua 

Acum, stergerea imi pune mici probleme. Ideea e sa gasesc nodul in arbore, apoi sa il cobor ca frunza si mai apoi sa il sterg simplu cu un delete sau sa il fac NULL. Problema e ca primesc acelasi vechi segmentation fault care ma bantuie de 2 zile incoace, uitati codul :

void stergere(arb &r, int x)
{ if (x > r->inf)
     stergere (r->dr,x);
  else if (x < r->inf)
     stergere (r->st,x);
  else
  {if ((r->st == NULL) && (r->dr == NULL))
      {delete (r);r = NULL;}
   else
       {if (r->st->pr > r->dr->pr)
          rotst(r);
        else
           rotdr(r);
        stergere(r,x);
       }
  } 
 }

ar trebui sa ridic conditia cu fiu stanga si fiu dreapta sus ?

[•toni2007]

Eu in momentul in care am gasit nodul. Ii bag prioritate -1 si bag cu for... Cat timp nu e NULL, echilibrez, ma duc in fiul in care s-a dus nodul dupa echilibrare pana ajung la el. Tu faci prost, pentru ca ar trebui sa verifici la inceput daca nodul nu e NULL. In caz ca nodul e NULL, in primul if tu faci NULL -> st. Incearca sa bagi cu for, cum ti-am zis.

[•tzoky07]

As vrea sa va multumesc pentru ajutor. Pana la urma a functionat cum trebuie programelul, astfel incat am scapat. Mai am de facut un word cu descrierea si e gata. Inca o data, multumesc celor de pe forumul Infoarena.