rotacje avl

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
            }                                                                 
} 

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

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

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.

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 :)