Algoritmo di rotazione ABR

[crypt0]

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)

[LexaIdo]

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)

[crypt0]

Grazie mille, era tutto quello di cui avevo bisogno
 

[LexaIdo]

Grazie mille, era tutto quello di cui avevo bisogno
 

di niente 

[milos224]

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?

[vincenzo86]

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

[milos224]

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

[dario]

  scusate ma la parte inerente all'aggiornamento dei campi degree e height???

[milos224]

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

[Daréios89]

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

[milos224]

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!

[Daréios89]

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.