Newsgroup: it.comp.lang
Titolo: [PYTHON] Alberi in Python

Ciao a tutti.
volevo avere delle delucidazione su un algoritmo di inserimento
bilanciato in un albero binario. Per ora l'algoritmo e' solo pensato
ma non riesco a capire come cominciarlo in python. Il tutto dovrebbe
riuscire molto piu' semplice in C ma in python non riesco proprio a
pensare come iniziarlo...
L'algoritmo si compone di 3 elementi ovvero il metodo di comportamento
standard seguito da 2 eccezioni.
In sostanza:
- Ogni elemento inserito, se e' compreso tra 2 elementi che si trovano
su uno dei due rami esterni (tutto a destra o tutto a sinistra)
diventa un nuovo vertice per i due elementi tra cui e' compreso. Se
non e' compreso tra nessuna coppia di elementi allora segue
l'inserimento standard.
Le eccezioni sono da inserire in un determinato ordine altrimenti
entrerebbero in un loop continuo.
- Se ci sono 3 elementi consecutivi tutti sulla stessa direzione a cui
manca il sottoramo della direzione opposta, l'elemento che e' in mezzo
diventa il vertice dei due elementi in cui e' compreso.
- Se c'e' una differenza di piu' di 1 livello di profondita' tra il
ramo destro e sinistro della radice allora l'albero va ruotato nella
direzione con meno profondita'. Il nuovo vertice dell'albero sara'
l'elemento piu' vicino al vertice vecchio come valore (in pratica
l'elemento piu' a destra del primo elemento a sinistra del vertice
originale e vice versa). Il vertice vecchio mantiene tutte le sue
referenze e il vecchio ramo del nuovo vertice viene modificato di
conseguenza (il ramo dove stava il nuovo vertice) [probabilmente la
questione del girare l'albero va un po' modificata perche' non l'ho
studiata ancora benissimo].
Ci tengo a precisare che l'algoritmo non l'ho copiato in giro ma
pensato da solo quindi non lapidatemi se e' uguale ad un algoritmo
gia' esistente (non mi fregerei mai dei meriti di un altro).
Il mio problema ora e' l'implementazione a oggetti di questa cosa...
Non capisco se creare un oggetto "item" dell'albero oppure creare un
oggetto albero e nel caso le funzioni da inserire, oppure creare
entrambi gli oggetti...
In C l'approcio sarebbe piu' "semplice" perche' creerei la struttura
appropriata per l'elemento e una serie di funzioni che agiscono
sull'albero (turnRight, turnLeft, addItem, removeItem, searchItem)
Non ho ancora pensato a come cancellare gli elementi dall'albero
comunque, ma prima sarebbe bello crearlo.
L'altro approcio sarebbe quello di creare una lista e dividerla a
meta' di volta in volta assegnando gli elementi che appartengono ai
multipli della meta' degli elementi che ho a ogni sottolivello sempre
piu' in basso
es:    3 5 7 8 9 12 15 16
L'albero sarebbe
      /   3  
    5
  /  \   7
/          \   8
9
\  
   15
      \  16
Grazie 1000 delle risposte.
-- 
try: troll = "Brain"
except TypeError, data: 
   troll.plonk()
Co-Responsabile Hardware Information & Technology 
http://hit.edengames.net

 sull'albero (turnRight, turnLeft, addItem, removeItem, searchItem)
Se questo e` l'approccio che trovi semplice, perche` non lo adotti pari
pari in Python?  Rappresenta la "struttura" in una classe contenente
solo i campi-dati, poi scrivi le funzioni, proprio come faresti in C.  Poi
in un secondo passo puoi trasformare le funzioni in metodi della classe,
se ti sembra che questo renda piu` leggibile il tutto (com'e` probabile).
Cosa mai potrebbe rendere PIU` semplice il C rispetto al Python per
questo problema?  Python non ti OBBLIGA ad adottare un approccio
OO, te lo PERMETTE se e quando TU lo ritieni opportuno...!
Alex