Benvenuto!
Accedi
o
registrati
.
15-12-2019, 11:45:34
Home
CDL Informatica
UniCT
CEA
Prof
Help
Search
Calendar
Login
Register
Forum Informatica Unict
»
LAUREA TRIENNALE (D.M. 270/04)
»
I anno
»
Programmazione 2, 9 CFU
(Moderators:
Rosalba Giugno
,
Alfredo Pulvirenti
,
Simone Faro
) »
Algoritmo di rotazione ABR
Pages: [
1
]
Go Down
« precedente
successivo »
Print
Author
Topic: Algoritmo di rotazione ABR (Read 2566 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
crypt0
Apprendista Forumista
Offline
Posts: 109
Algoritmo di rotazione ABR
«
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
Gender:
Posts: 110
Re:Algoritmo di rotazione ABR
«
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
Posts: 109
Re:Algoritmo di rotazione ABR
«
Reply #2 on:
15-07-2010, 11:28:40 »
Grazie mille, era tutto quello di cui avevo bisogno
Logged
LexaIdo
Apprendista Forumista
Offline
Gender:
Posts: 110
Re:Algoritmo di rotazione ABR
«
Reply #3 on:
16-07-2010, 09:24:24 »
Quote from: crypt0 on 15-07-2010, 11:28:40
Grazie mille, era tutto quello di cui avevo bisogno
di niente
Logged
milos224
Forumista
Offline
Posts: 830
Re:Algoritmo di rotazione ABR
«
Reply #4 on:
03-10-2011, 10:44:34 »
Quote from: LexaIdo 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)
Del Left non hai lo pseudocodice?
Logged
vincenzo86
Forumista
Offline
Gender:
Posts: 505
Re:Algoritmo di rotazione ABR
«
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
Posts: 830
Re:Algoritmo di rotazione ABR
«
Reply #6 on:
03-10-2011, 10:57:25 »
Quote from: vincenzo86 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..
Il fatto è che non so metterci mano
Logged
dario
Matricola
Offline
Posts: 21
Re:Algoritmo di rotazione ABR
«
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
Posts: 830
Re:Algoritmo di rotazione ABR
«
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
Gender:
Posts: 2.679
La musica è la forma d'arte suprema.
Re:Algoritmo di rotazione ABR
«
Reply #9 on:
03-10-2011, 21:19:54 »
Quote from: milos224 on 03-10-2011, 17:29:55
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
Posts: 830
Re:Algoritmo di rotazione ABR
«
Reply #10 on:
03-10-2011, 21:21:58 »
Quote from: Daréios89 on 03-10-2011, 21:19:54
Quote from: milos224 on 03-10-2011, 17:29:55
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
Gender:
Posts: 2.679
La musica è la forma d'arte suprema.
Re:Algoritmo di rotazione ABR
«
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
« precedente
successivo »
Jump to:
Please select a destination:
-----------------------------
Area Ufficiale
-----------------------------
=> Annunci Ufficiali
=> Segreteria Didattica
=> Aiuto, proposte e commenti
=> Stages e progetti finali
=> C.O.F. Centro Orientamento e Formazione
=> Messaggi (d)agli amministratori del forum
-----------------------------
LAUREA TRIENNALE (D.M. 270/04)
-----------------------------
=> I anno
===> Architettura degli Elaboratori, 9 CFU
===> Elementi di Analisi Matematica, 12 CFU
===> Fondamenti di Informatica, 9 CFU
===> Matematica Discreta, 12 CFU
===> Programmazione 1, 9 CFU
===> Programmazione 2, 9 CFU
=> II anno
===> Algoritmi, 9 CFU
===> Basi di Dati, 9 CFU
===> Fisica, 9 CFU
===> Ingegneria del Software, 9 CFU
===> Inglese, 3 e 6 CFU
===> Interazione e Multimedia, 9 CFU
===> Sistemi Operativi, 9 CFU
=> III anno
===> Calcolo Numerico, 6 CFU
===> Formazione Numerica, 6 CFU
===> Introduzione all'Analisi dei Dati, 9 CFU
===> Metodi Matematici e Statistici, 6 CFU
===> Reti di Calcolatori, 9 CFU
===> Tecniche di Programmazione Concorrente e Distribuita, 9 CFU
===> Teoria dell'Informazione e Crittografia, 9 CFU
=> III anno - Materie a scelta (crediti liberi)
===> Computer Forensics, 6 CFU
===> Computer Graphics, 9 CFU
===> Digital Game Development, 6 CFU
===> GPGPU/CUDA, 6 CFU
===> Informatica Musicale, 6 CFU
===> LAP 1: programmazione C/C++ 6 CFU
===> LAP 2: Programmazione Android, 6 CFU
===> Sistemi Centrali, 6 CFU
===> Startup d'impresa e Modelli di Business, 6 CFU
===> Internet Security 9 CFU
===> Social Media Management, 6 CFU
=> Corsi disattivati - Vecchio curriculum
===> E-Commerce, 6 CFU
===> Legislazione Informatica, 6 CFU
===> Teoria della Computabilità, 9 CFU
-----------------------------
LAUREA MAGISTRALE
-----------------------------
=> I ANNO
===> Intelligenza Artificiale e Lab, 9 CFU
===> Algoritmi e Complessità, 9 CFU
===> Computer Vision, 9 CFU
===> Crittografia, 9 CFU
===> Fondamenti e Linguaggi per la Programmazione Distribuita
===> Inglese Scientifico, 3 CFU
===> Metodi analitici per l'informatica, 6 CFU
===> Metodi Matematici per l'Ottimizzazione (Corso Integrato), 12 CFU
===> Multimedia, 9 CFU
===> Sicurezza dei Sistemi Informatici 9 CFU
===> Computer Security, 9 CFU
=> II ANNO
===> Machine Learning 6 CFU
===> Teoria della Computabilità, 9 CFU
===> Analisi e Gestione dei Dati, 9 CFU
===> Compilatori, 9 CFU
===> Computazione Naturale e BioIspirata, 6 CFU
===> Introduzione alla Bioinformatica, 9 CFU
===> Linguaggi Formali e Applicazioni, 9 CFU
===> Logica Computazionale, 9 CFU
===> P2P & Wireless Networks, 9 CFU
===> Pattern Recognition, 9 CFU
===> Sistemi Distribuiti, 9 CFU
===> Sistemi dedicati e laboratorio, 9 CFU
===> Web Reasoning
=> Corsi disattivati - Vecchio curriculum
===> Fisica moderna per l'informatica, 6 CFU
===> Linguaggi di Programmazione, 9 CFU
===> Protocolli di Rete
===> Teoria dei Codici, 6 CFU
-----------------------------
Vecchi ordinamenti ad esaurimento
-----------------------------
=> Laurea Triennale (D.M. 509/00)
===> Algoritmi 1
===> Algoritmi 2
===> Basi Teoriche dell'Informatica
===> Economia Aziendale
===> Fisica 1, 6 CFU
===> Fisica 2, 6 CFU
===> Fisica 3
===> Formazione Analitica 1
===> Formazione Analitica 2
===> Formazione Discreta 1
===> Formazione Discreta 2
===> J2ME
===> Lab. Amministrazione di Sistemi
===> Laboratorio di Interazione
===> Modelli Matematici
===> Multimedia per Dispositivi Mobile
===> Progetto Software
===> Reti 1, 6 CFU
===> Sicurezza dei Sistemi Informatici 1
===> Sistemi Distribuiti 1
===> Teoria dei Grafi
===> Usabilità ed Estetica del Web
===> Web Programming
=> Laurea Specialistica (D.M. 509/00)
===> Algoritmi 3
===> Analisi Numerica
===> Complessità
===> Computabilità
===> Data analysis e management
===> Ingegneria del software 2
===> Linguaggi Formali
===> Metodi algoritmici per l'ottimizzazione combinatoria
===> Programmazione Funzionale
===> Reti di Calcolatori 2
===> Ricerca Operativa
===> Sistemi Distribuiti 2
-----------------------------
Dottorandi
-----------------------------
=> Wall
=> Events
-----------------------------
Area Studenti
-----------------------------
=> Agorà
=> L'angolo del tecnico
=> Il Mercatino degli studenti
=> Software
===> -vecchia catalogazione [sarà rimossa a breve]-
=====> Proprietario
=====> Free Software
=====> Open Source
===> Approfondimenti
===> News
===> Studio
===> Videogiochi
===> Networking e telecomunicazioni
===> Sviluppo
===> Ufficio e produttività
===> Sistemi Operativi
=====> Microsoft Windows
=====> GNU/Linux, Unix e BSD
=====> Mac OS X
=====> Windows Phone
=====> Android
=====> iOS
=====> Altri
===> Eventi, conferenze, concorsi
=> Microsoft Student Partner - Avvisi e informazioni
=> ERASMUS/borse di studio internazionali
Caricamento in corso...