[ALGORITMO] Albero binario di ricerca

[GabbOne]

                    
                                     100
                                   /      \
                                 90      130
                                /   \     /   \
                              90   90  120 150

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

[Habanero]

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]

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]

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]

edit
nn aevo letto il post successivo.

[king64]

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]

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]

grazie per le risposte penso ch siamo arrivati ad una conclusione per lo meno coerente :master: