Alberi binari di ricerca

da **Valerio Capraro** » 23/05/2006, 11:14

Devo implementare in c++ un albero binario di ricerca,
ovvero tale che ogni nodo è maggiore del suo
sottoalbero sinistro e minore del suo sottoalbero destro.
IL mio problema sta nel decidere la radice, in quanto
altrimenti si rischia che l'albero venga sbilanciato. Come faccio
a decidere? insomma se prendo l'elemento medio di tutti gli
elementi devo sapere a priori quali sono, metterli in un array, trovarlo....
mi sembra troppo costoso...
viceversa, se costruisco direttamente l'albero, allora
ad ogni iterazione devo eventualmente cambiare radice se l'elemento
mediano cambia... e quindi devo fare un sacco di confronti...

da **Valerio Capraro** » 23/05/2006, 12:26

oppure mi servirebbe un algoritmo veloce che calcoli, dato un array,
l'elemento che starebbe nella metà se l'array fosse ordinato...
ho provato con una variante del quick sort... ma non viene..
e in realtà non so bene perchè..

da **Kroldar** » 23/05/2006, 12:28

un array statico o dinamico?
cmq perché non provi con una funzione che riceve un array di cardinalità n (dispari), ne crea una copia, la ordina e restituisce il valore dell'elemento [n/2]+1-esimo (poi magari distrugge la copia deallocando la memoria utilizzata)?

da **Valerio Capraro** » 23/05/2006, 12:59

volevo cavarmela con meno...
insomma, concorderai che ordinare completamente
un array per trovare un elemento solo è tremendamente
dispendioso

da **Kroldar** » 23/05/2006, 13:24

ubermensch ha scritto:insomma, concorderai che ordinare completamente
un array per trovare un elemento solo è tremendamente
dispendioso

concordo pienamente

da **etherior** » 23/05/2006, 15:27

a primo acchitto mi verebbe in mente di inserire in ordine gli elementi e poi applicare uno dei noti metodi di bilanciamento;ciò ti evita di fare qualsiasi controllo preventivo sugli elementi e va bene anche se in seguito vuoi aumentare il numero di elementi.La soluzione dell'array è troppo pesante e ti limita ad un solo utilizzo dell'algoritmo.Cioè se hai fatto il tuo albero per la prima volta,poi vuoi inserire un'altro stock di elementi o rifai tutte cose o cmq ti ritroverai a dover bilanciare in qualche modo l'albero.(Sicuramente esistono soluzioni migliori di questa,ma è già qualcosa....)

da **Nidhogg** » 23/05/2006, 16:59

Uber dai un'occhiata qui!

Ciao!

da **Valerio Capraro** » 23/05/2006, 18:53

grande leonardo... pare molto completo...

Alberi binari di ricerca

Alberi binari di ricerca

Chi c’è in linea