Pages: [1]   Go Down
Print
Author Topic: Algoritmo di rotazione ABR  (Read 2506 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
crypt0
Apprendista Forumista
**
Offline Offline

Posts: 109


« on: 15-07-2010, 10:10:11 »

Salve

Nel libro consigliato (Strutture dati ed algoritmi in Java) non si fa alcun riferimento all'algoritmo di rotazione applicato agli alberi binari (argomento di una lezione che, a quanto pare, devo aver perso)

Qualcuno può fornirmene una implementazione in pseudocodice ed una breve spiegazione?
O per lo meno un link che descriva tale algoritmo in maniera più simile a quella spiegata dal prof a lezione.

Lo chiedo perchè è capitato, come ad esempio nel caso dell'albero, che il prof abbia fornito una implementazione diversa da quella classica.
(TRADUZIONE: Niente link da lmgtfy.com, per favore)
Logged
LexaIdo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 110



« Reply #1 on: 15-07-2010, 11:15:51 »

questo è lo pseudocodice del rightRotate(x) che ho copiato io dalla lavagna durante la lezione del prof
Code:
rightRotate(x)
     if (x == null) return
     if (x.left == null) return
     y=x.left
     y.parent = x.parent
     if (y.parent == null) then root=y
     else if (x == x.parent.left) then y.parent.left=y
            else y.parent.right=y
     x.parent=y
     x.left=y.right
     if (x.left != null) then x.left.parent=x
     y.right=x
e questa è una rappresentazione grafica di quello che avviene con una rightRotate(x):

                  |                         |
                (x)                       (y)
               /    \                     /   \
             (y)   (c)      =>     (a)   (x)
             / \                               /  \
           (a) (b)                        (b)  (c)
Logged
crypt0
Apprendista Forumista
**
Offline Offline

Posts: 109


« Reply #2 on: 15-07-2010, 11:28:40 »

Grazie mille, era tutto quello di cui avevo bisogno
 ok
Logged
LexaIdo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 110



« Reply #3 on: 16-07-2010, 09:24:24 »

Grazie mille, era tutto quello di cui avevo bisogno
 ok
di niente 
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #4 on: 03-10-2011, 10:44:34 »

questo è lo pseudocodice del rightRotate(x) che ho copiato io dalla lavagna durante la lezione del prof
Code:
rightRotate(x)
     if (x == null) return
     if (x.left == null) return
     y=x.left
     y.parent = x.parent
     if (y.parent == null) then root=y
     else if (x == x.parent.left) then y.parent.left=y
            else y.parent.right=y
     x.parent=y
     x.left=y.right
     if (x.left != null) then x.left.parent=x
     y.right=x
e questa è una rappresentazione grafica di quello che avviene con una rightRotate(x):

                  |                         |
                (x)                       (y)
               /    \                     /   \
             (y)   (c)      =>     (a)   (x)
             / \                               /  \
           (a) (b)                        (b)  (c)


Del Left non hai lo pseudocodice?
Logged
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #5 on: 03-10-2011, 10:50:03 »

Basta cambiare i riferimenti, vedendo lo pseudocodice del precedente, puoi fare l'altro. Il prof così ha fatto a lezione..
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #6 on: 03-10-2011, 10:57:25 »

Basta cambiare i riferimenti, vedendo lo pseudocodice del precedente, puoi fare l'altro. Il prof così ha fatto a lezione..

Il fatto è che non so metterci mano [Emoticon] Rosik Asd
Logged
dario
Matricola
*
Offline Offline

Posts: 21


« Reply #7 on: 03-10-2011, 15:55:58 »

  scusate ma la parte inerente all'aggiornamento dei campi degree e height???
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #8 on: 03-10-2011, 17:29:55 »

raga nessuno che sa la rotazione sinistra? il compito è domani 
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #9 on: 03-10-2011, 21:19:54 »

raga nessuno che sa la rotazione sinistra? il compito è domani 

Scusa!!!!! Ho visto solamente adesso, dovrebbe essere questa, non l' ho controllata ma l' ho trovata tra i miei appunti:

Code:
public void LeftRotate(E x){
    TNode<E> tmp= tornaNodo(x);
    if (tmp == null)
      return;
    if (tmp.getRight() == null)
      return;
    TNode<E> y= tmp.getRight();
    y.setParent(tmp.getParent());
    if (y.getParent() == null)
      root=y;
    else if (tmp.getlabel() == tmp.getParent().getRight().getlabel())
      y.getParent().setRight(y);
    else
      y.getParent().setLeft(y);
    tmp.setParent(y);
    tmp.setRight(y.getLeft());
    if (tmp.getRight() != null)
      tmp.getRight().setParent(tmp);
    y.setLeft(tmp);
  }

In bocca al lupacchiotto!!!
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #10 on: 03-10-2011, 21:21:58 »

raga nessuno che sa la rotazione sinistra? il compito è domani 

Scusa!!!!! Ho visto solamente adesso, dovrebbe essere questa, non l' ho controllata ma l' ho trovata tra i miei appunti:

Code:
public void LeftRotate(E x){
    TNode<E> tmp= tornaNodo(x);
    if (tmp == null)
      return;
    if (tmp.getRight() == null)
      return;
    TNode<E> y= tmp.getRight();
    y.setParent(tmp.getParent());
    if (y.getParent() == null)
      root=y;
    else if (tmp.getlabel() == tmp.getParent().getRight().getlabel())
      y.getParent().setRight(y);
    else
      y.getParent().setLeft(y);
    tmp.setParent(y);
    tmp.setRight(y.getLeft());
    if (tmp.getRight() != null)
      tmp.getRight().setParent(tmp);
    y.setLeft(tmp);
  }

In bocca al lupacchiotto!!!

Grazieee!
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #11 on: 03-10-2011, 21:30:24 »

Uno pseudocodice più astratto preso dal libro di algoritmi potrebbe essere:

Code:
LEFT-ROTATE(T,x)
y=right(x)   //Imposta y
right(x)=left(y)  //Sposta il sottoalbero sinistro di y nel sottoalbero destro di x
if(left(y)!=null)
 then
       p(left(y))=x
p(y)=p(x)                //collega il padre di x ad y
if(p(x)=null)
  then root(T)=y
else if x=left(p(x))
  then left(p(x))=y
  else right(p(x))=y
left(y)=x      //Pone x a sinistra di y
p(x)=y

Ovviamente p sta per parent, left e right per figlio sinistro e destro.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Pages: [1]   Go Up
Print
Jump to: