PDA

Visualizza la versione completa : [ALGORITMO] Albero binario di ricerca


GabbOne
20-11-2006, 17:39
100
/ \
90 130
/ \ / \
90 90 120 150


ragazzi secondo voi questo albero è un albero binario di ricerca BST????
:dhò:

Habanero
20-11-2006, 23:06
se nella definizione è imposto un ordinamento totale dei nodi (come in genere avviene) quello non è un albero di ricerca binaria. Esistono infatti nodi uguali.

GabbOne
22-11-2006, 12:47
La definizione che ho trovato su una dispensa universitaria dice che in BST

1.Ogni nodo contiene una coppia (chiave,elemento)

2.Le chiavi sono estratte da un insieme totalmente ordinato

3.Per ogni nodo v tutte le chiavi del sottoalbero sx di v sono maggiori o al massimo uguali alla chiave di v

4.Per ogni nodo v tutte le chiavi del sottoalbero dx di v sono minori o al massimo uguali alla chiave di v.


Il miei dubbi nascono soprattutto pensando all'ambiguita dll'algoritmo che fa gli inserimenti nell'albero sopra indicato . :(

Habanero
22-11-2006, 13:57
mmm guarda... non sono più sicuro di quello che ti ho detto.. in realtà l'ordinamento totale sussiste (ho detto una stupidaggine).... Il fatto è che ho trovato alcune definizione di BST in cui la relazione d'ordine è < e non =<...

In base alla tua definizione l'albero dovrebbe essere bst.
Preferisco non darti certezze... sono cose molto lontane nel tempo per me.. :-)

rsdpzed
23-11-2006, 06:35
edit
nn aevo letto il post successivo.

king64
23-11-2006, 10:20
Ho per caso sottomano un mio testo universitario Ausiello-Talamo "Strutture per la gestione statica e dinamica dei dati" - Franco Angeli , che recita :"Un albero binario di ricerca è un albero binario in cui la chiave associata ad ogni nodo interno è maggiore di tutte le chiavi associate ai nodi del sottoalbero sinistro e minore di tutte le chiavi associate al sottoalbero destro". Per cui il tuo albero non "sarebbe" un albero binario di ricerca , tuttavia sulla rete ho trovato alcune definizioni di alberi BST che indicano che la relazione d'ordine tra i nodi possa includere anche l'uguaglianza . Il dubbio rimane :master:

doraemon83
23-11-2006, 12:02
Da quel che ricordo del corso di algoritmi e strutture dati all'università un albero binario di ricerca puo avere chiavi ripetute nei propri sottoalberi (sia destro che sinistro). In base a ciò quello è un ABR o BST come preferite chiamarlo.

Quello che normalmente viene fatto in una implementazione reale è quello di mettere le chiavi ripetute sempre e solo in uno dei due sottoalberi, cioè se un nodo vale 30, tutti gli altri 30 vanno messi o tutti nel sottoalbero sinistro o tutti nel sottoalbero destro, in quanto nelle ricerche ci sarebbe maggiore ambiguità nel caso ad esempio si debbano trovare tutti i valori uguali.

Quindi quello è un albero binario di ricerca, ma non efficientissimo in certi casi.

ciao ciao

GabbOne
23-11-2006, 16:49
grazie per le risposte penso ch siamo arrivati ad una conclusione per lo meno coerente :master:

Loading