Pages: 1 2 3 [4]   Go Down
Print
Author Topic: dubbio su un possibile errore in un esercizio sugli Alberi binari di ricerca  (Read 5371 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
fabryxio
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 343

Chi l'ha duro....... l'ha duro!


WWW
« Reply #45 on: 19-09-2011, 18:12:29 »

Scusate mi stavo rileggendo le vostre discussioni e mi pare di aver capito che quando si presenta un'operazione di rightRotate si fa diventare l'elemento x (es. rightRotate(46) ) il primo figlio destro del suo figlio sinistro (33) e si collegano a lui gli eventuali nodi al di sotto di quest'ultimo nodo (33), giusto?


              17
             /    \
          3        46
                   /
                33
              /     \
           18      40
            \
            26
              \
              30

Si ma se posti già l'albero ruotato come si capisce ? -.-
Logged

jos90
Apprendista Forumista
**
Offline Offline

Posts: 171



« Reply #46 on: 19-09-2011, 19:16:59 »

Sia dato un albero binario di ricerca, T, costruito mediante l'inserimento delle seguenti chiavi, in ordine di arrivo (3, 9, 31, 8, 4, 28, 34, 22).
Individuare il corretto output di una visita Preorder del suddetto albero dopo aver effettuato l'operazione RightRotate(T,31)


Supponiamo sia questo l'albero su cui fare la rotazione:

Code:
                             3
                               \
                                 9
                                /  \
                              8    31
                             /      /  \
                            4    28  34
                                  /
                                22

RightRotate in questo caso sostituisce il 31 con il figlio 28, poi fa diventar 31 il primo figlio destro di 34 e 22 diventa anch'esso figlio di 34, diventando così, giusto?

Code:
                             3
                               \
                                 9
                                /  \
                              8    28
                             /        \
                            4         34
                                       /  \
                                     22 31
Logged

Perchè non pensi di non capire, quando capisci di non pensare?
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #47 on: 19-09-2011, 20:19:48 »

Premetto che non sono mai stato forte nelle rotazioni, a me viene:

              3
                \
                  9
                /   \
             8      28
            /      /    \
          4    22      31
                            \
                              34
Logged

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

Posts: 171



« Reply #48 on: 20-09-2011, 07:40:29 »

quindi è come se avessi fatto scorrere verso destra il 31? (perdona le domande un pò sempliciotte e stupide ma vorrei capire il ragionamento XD )
Logged

Perchè non pensi di non capire, quando capisci di non pensare?
callo
Forumista
***
Offline Offline

Gender: Male
Posts: 564


"Quanto manca alla vetta?";"Tu sali e non pensare"


« Reply #49 on: 20-09-2011, 08:44:44 »

Confermo che la rotazione fatta da Dareios è corretta!!Il ragionamento da fare quando si fa una rotazione è il seguente:
Supponiamo di avere l'albero composto dai seguenti nodi

                                                     x                           
                                                  /     \
                                                 a       y
                                                        /   \ 
                                                      b     g
Dove a,b,g sono sottoalberi arbitrari!!Quando vuoi fare una rotazione sinistra sul nodo x la prima cosa che deve verificarsi è che il nodo x deve avere un figlio destro(e nell'albero che ho rappresentato il figlio destro di x è y)....analogamente per la rotazione destra il nodo che vuoi ruotare deve avere il figlio sinistro. La rotazione sinistra fa "perno"(non è proprio corretto come termine però rende l'idea!!) sul collegamento tra il nodo x e il nodo y; il nodo y diventa la nuova radice, x diventa il figlio sinistro di y(perché altrimenti verrebbe invalidata la regola degli alberi binari di ricerca secondo cui : key
  • <key[y]) e il figlio sinistro di y diventa figlio destro di x!! Analogamente funziona la RightRotate!!Ricorda che ciò che viene modificato in una rotazione sono solo i puntatori quindi visto che "muovere" un puntatore costa O(1) la rotazione avviene in un tempo costante!!
L'albero finale quindi sarà:

                       y
                     /    \
                   x      g
                 /   \
               a     b
Logged

"A cavallina....a cavallina.....a chi era bedda quannu  curreva" [Cit.  Dal Tenerissimo via plebiscito]
fabryxio
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 343

Chi l'ha duro....... l'ha duro!


WWW
« Reply #50 on: 20-09-2011, 09:42:34 »

Premetto che non sono mai stato forte nelle rotazioni, a me viene:

              3
                \
                  9
                /   \
             8      28
            /      /    \
          4    22      31
                            \
                              34
Corretto Wink
Logged

jos90
Apprendista Forumista
**
Offline Offline

Posts: 171



« Reply #51 on: 21-09-2011, 11:42:15 »

EDIT: Esercizio Risolto grazie mille per le risposte!
Logged

Perchè non pensi di non capire, quando capisci di non pensare?
Pages: 1 2 3 [4]   Go Up
Print
Jump to: