rotacje avl

0

witam
mam problem z rotacjami w avl, już 4 dzień nad tym siedzę i nie mogę dojść co jest nie tak
to jest najlepsza wersja jak na razie,
w rotacjach (rr i ll) jeżeli a == 1 wykonywana jest rotacja rl lub lr,
kluczem drzewa jest przede wszystkim pesel przynajmniej jedno pole jest zawsze unikatowe, zatem pesel może się powtarzać i np. imię ale nazwisko musi być wtedy inne
bardzo proszę o pomoc

 #include <iostream>

using namespace std;

struct drzewo{
        drzewo *parent, *left, *right;
        string name,surname;
        unsigned int pesel;
        int bf;
};

drzewo *rr(drzewo * p,int a){
     drzewo *l;
     l = p->right;
     if(a == 1){
          p->right = l->left;
          l->left->parent = p;
          l->left->right = l;
          l->parent = l->left;
          l->left = NULL;
          }
          l = p->right;
     l->parent = p->parent;
     p->parent->right = l;
     l->left = p;
     p->parent = l;
     p->right = NULL;
     return l;

     }
drzewo *ll(drzewo *p,int a){
       drzewo *l;
       l=p->left;
       if(a == 1){
          p->left = l->right;
          l->right->parent = p;
          l->right->left = l;
          l->parent = l->right;
          l->right = NULL;
          }
          l = p->left;

     l->parent = p->parent;
     p->parent->left = l;
     l->right = p;
     p->parent = l;
     p->left = NULL;

     return l;
     }

drzewo * balance(drzewo * l,int dir){                                               // -1 prawy, 1 lewy
     drzewo *p;
     p=l->parent;

     l->bf=0;

     if(dir == 1)l->parent->left=l;
            else l->parent->right=l;

     if(p->bf != 0)p->bf=0;

            //cout << "sciezka: " << endl << endl;

            while(p->parent != NULL){
                    if(p->left == NULL && p->right == NULL)p->bf=0;
                    if(p->left == NULL){
                               if(p->right->bf == 0)p->bf=-1;
                               else p->bf=-2;
                               }
                    if(p->right == NULL){
                                if(p->left->bf == 0) p->bf=1;
                                else p->bf=2;
                                }

                    if(p->left != NULL && p->right != NULL){
                               if(p->left->bf !=0 && p->right->bf == 0)p->bf+=1;
                               if(p->right->bf !=0 && p->left->bf == 0)p->bf-=1;
                               if(p->right->bf !=0 && p->left->bf != 0)p->bf=0;
                               if(p->right->bf ==0 && p->left->bf == 0)p->bf=0;
                               }

                    cout << "jestem " << p->pesel << " moj bf=" << p->bf << " synowie: ";
                    if(p->left != NULL)cout << p->left->pesel << " ";;
                    if(p->right != NULL)cout << p->right->pesel;
                    cout << endl;

                    if(p->bf == -2){
                             //cout << "rotacja rr!!!" << endl;
                             if(p->right->bf == -1) {rr(p,0);break;}
                             else {rr(p,1);break;}
                             }
                    else if(p->bf == 2){
                             //cout << "rotacja ll!!!" << endl;
                             if(p->left->bf == 1) {ll(p,0);break;}
                             else {ll(p,1);break;}
                             }
                    p=p->parent;                                                //przesuwamy wskaznik
            }                                                                 
} 
0

Nawet nie napisałeś w czym problem. Tutaj masz świetny tutorial: http://edu.i-lo.tarnow.pl/inf/utils/002_roz/mp002.php

0

jakbym miał nad tak krótkim kodem siedzieć 4 dni, to bym go 4 razy od nowa napisał, wtedy patrząc na świeżo na problem pewnie znalazłbym błąd szybciej niż analizując ten fragment

0

problem polega na tym, że dla małych testów, gdzie na przykład kolejne pesele to: 10 20 30, rotacja działa prawidłowo ustanawiając jako ojca (korzeń) 20 lewy syn 10 prawy syn 30 i podobnie dobrze dla innych rotacji. Kiedy stworzyłem test dla 30 elementów drzewa, program nie radzi sobie z ich odnalezieniem. Poniżej dorzucam jeszcze maina. Na poczatku wczytuje on liczbę elementów, następnie kolejno imię, nazwisko, numer identyfikacyjny. W następnym kroku program wczytuje liczbę zapytań i w kolejnych liniach imię, nazwisko i numer identyfikacyjny celem wyszukania go w drzewie. Do pisania programu korzystałem właśnie z poradnika, który zamieścił kolega wyżej w poście. Oto kod main:

 int main(){

    unsigned int n; 
    int m,t1,t2;
    cin >> n;

    drzewo *p=new struct drzewo;
    drzewo *first = new struct drzewo;
    drzewo *back,*l,*t;
    for(int i=0;i<n;i++){
            p = new struct drzewo;p=first;
            l = new struct drzewo;
            if(i == 0){
                 cin >> first->name >> first->surname >> first->pesel;
                 first->parent=NULL;
                 first->right=NULL;
                 first->left=NULL;
                 continue;
                 }
           cin >> l->name >> l->surname >> l->pesel;
           back=NULL;
           while(p!=NULL){
                          back=p;
                          if(l->pesel < p->pesel) p=p->left;
                          else if(l->pesel > p->pesel) p=p->right;
                          else {
                               t1=(l->name).compare(p->name);
                               t2=l->surname.compare(p->surname);
                               if((t1 == 0 && t2 == 1) || (t1 == 1 && t2 == 0)) p=p->right;
                               else p=p->left;
                               } 
           }
           l->right=NULL;
           l->left=NULL;
           if(back!=NULL){
                          l->parent=back;
                          if(l->pesel < back->pesel) t=balance(l,1);
                          else if(l->pesel > back->pesel) t=balance(l,-1);
                          else {
                               t1=(l->name).compare(back->name);
                               t2=l->surname.compare(back->surname);
                               if((t1 == 0 && t2 == 1) || (t1 == 1 && t2 == 0)) t=balance(l,-1);
                               else t=balance(l,1);
                               }
                               if(t->parent == NULL)first=t;
           }
    }
           cin >> m;
           string a,b;
           unsigned int c;
           int log=0;
           for(int i=0;i<m;i++){
                   log = 0;
                   cin >> a >> b >> c;
                   p=NULL;
                   p=first;
                   while(p!=NULL){
                          if(c == p->pesel){
                               t1=a.compare(p->name);
                               t2=b.compare(p->surname);
                               if(t1 == 0 && t2 == 0){
                                     cout << "TAK" << endl;
                                     log=1;
                                     break;
                               }
                               else if((t1 == 0 && t2 == 1) || (t1 == 1 && t2 == 0)) p=p->right;
                               else /*if((t1 == 0 && t2 == -1) || (t1 == -1 && t2 == 0))*/ p=p->left;

                          }
                          else if(c < p->pesel) p=p->left;
                          else if(c > p->pesel) p=p->right;
                   }
                   if(log == 0) cout << "NIE" << endl;
           }

    return 0;
}

Program wypisze TAK w przypadku znalezienia poszukiwanego elementu w drzewie i NIE w przeciwnym wypadku.
Dla większości testów działa dobrze, jednak wypisuje tylko NIE dla testu w załączniku.

0
krwq napisał(a)

jakbym miał nad tak krótkim kodem siedzieć 4 dni, to bym go 4 razy od nowa napisał, wtedy patrząc na świeżo na problem pewnie znalazłbym błąd szybciej niż analizując ten fragment

jestem początkującym programistą, a komentarze w stylu: 4 dni nad taki krótkim kodem... wcale nie są pomocne, a napisanie tego co zamieściłem uważam za szczyt moich możliwości programistycznych, niemniej dziękuje za zainteresowanie :)

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