Alberi binari di ricerca
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...
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...
Risposte
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è..
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è..
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)?
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)?
volevo cavarmela con meno...
insomma, concorderai che ordinare completamente
un array per trovare un elemento solo è tremendamente
dispendioso
insomma, concorderai che ordinare completamente
un array per trovare un elemento solo è tremendamente
dispendioso
"ubermensch":
insomma, concorderai che ordinare completamente
un array per trovare un elemento solo è tremendamente
dispendioso
concordo pienamente
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....)
grande leonardo... pare molto completo...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo