 |
 | | algorytm równoważenia drzew binarnych [C] |
|
 |
 Wysłano: Wtorek, 25 Maj 2004, 10:35 |
  |
|
|
| Szukam algorytmu równoważenia drzew binarnych w c. |
|
|
|
|
 |
|
 |
|
| | Re: algorytm równoważenia drzew binarnych [C] |
|
|
| Wysłano: Środa, 26 Maj 2004, 01:00 |
|
|
|
jest ich pare..
dobre to AVL i RB.
http://www.seanet.com/users/arsen/avltree.html
kod dla AVL:
| Kod: |
/*zwraca wielkosc poddrzewa o korzeniu x*/
int pod(EL *x){
if(x)
return x->pod;
return 0;
}
/*zwraca element wieszky*/
int max(int a,int b){
if(a>b)
return a;
return b;
}
/*rotacja w lewo wzgledem x*/
void ll(EL *x){
if(!x->p)
root=x->r;
else if(x==x->p->l)
x->p->l=x->r;
else
x->p->r=x->r;
x->r->p=x->p;
x->p=x->r;
x->r=x->p->l;
if(x->r)
x->r->p=x;
x->p->l=x;
/*aktualizacja wysokosci poddrzew*/
x->pod=max(pod(x->l),pod(x->r))+1;
x=x->p;
x->pod=max(pod(x->l),pod(x->r))+1;
}
/*rotacja w lewo wzgledem x*/
void rr(EL *x){
if(!x->p)
root=x->l;
else if(x==x->p->l)
x->p->l=x->l;
else
x->p->r=x->l;
x->l->p=x->p;
x->p=x->l;
x->l=x->p->r;
if(x->l)
x->l->p=x;
x->p->r=x;
/*aktualizacja wysokosci poddrzew*/
x->pod=max(pod(x->l),pod(x->r))+1;
x=x->p;
x->pod=max(pod(x->l),pod(x->r))+1;
}
/*przywraca wlasnosc AVL od x-a w gore*/
void update(EL *x){
int temp;
do{
temp=x->pod;
switch(pod(x->l)-pod(x->r)){ /*roznica wysokosci*/
case 2:
if(pod(x->l->l)-pod(x->l->r)==-1)
ll(x->l);
rr(x);
x=x->p;
break;
case -2:
if(pod(x->r->l)-pod(x->r->r)==1)
rr(x->r);
ll(x);
x=x->p;
break;
default:
x->pod=max(pod(x->l),pod(x->r))+1;
}
}
while(x=x->p);
} |
struktura elementow:
| Kod: |
element->l <=> lewy potomek
element->r <=> prawy potomek
element->l <=> rodzic
element->pod <=> wielkosc poddrzewa - specyficzne dla AVL - musisz dodac |
korzen musi byc zdefiniowany globalnie, charakteryzuje sie tym ze jego rodzic jest NULL.
jesli element nie ma danego potomka to wskaznik na niego to tez NULL.
oczywiscie wszystkie nazwy mozesz pozmieniac.
po dodaniu lub usunieciu czegos z drzewa trzeba je zrownowazyc wywolujac update(x), gdzie x to element dodawany lub rodzic elementu usuwanego (tego ktorego pamiec zwalniamy), jesli taki istnieje.
Kod, ktory mam u siebie jest lepszy - troche szybszy, ale moze ci przysporzyc dodatkowych problemow w stosunku do tego wiec nie podaje. |
|
|
|
|
|
|
|
Kopiowanie i rozpowszechnianie materiałów w całości lub części jest niedozwolone. Wszelkie informacje zawarte w tym miejscu są chronione prawem autorskim.
|
