Che cosa succede agli elementi uguali quando si inseriscono in un albero di ricerca binario?

Question

Che cosa succede agli elementi uguali quando si inseriscono in un albero di ricerca binario?

#1 da (1 voti)

0

La maggior parte degli esempi di BST mostrano un esempio di un BST con valori unici; principalmente per dimostrare l'ordine dei valori. per esempio. i valori nella sottostruttura di sinistra sono più piccoli della radice e i valori nella sottostruttura di destra sono più grandi.

Questo perché i BST sono normalmente usati solo per rappresentare i SET?

Se inserisco un elemento che dice 4 che già esiste nel BST, che cosa dovrebbe accadere? per esempio. Nel mio caso, 4 è associato a un carico utile. Significa che ignoro il payload del nodo esistente.

data-structures trees

posta Bon Ami 19.04.2014 - 20:05

fonte

1 risposta

Leggi altre domande sui tag data-structures trees

Prestazioni di una API o di più API Progettazione di autorizzazione flessibile nelle pagine ASP.NET?

score 1 · Accepted Answer

I classici esempi del BST dimostrano un set dove c'è una voce per un dato valore in la struttura. Un esempio di questo è il TreeSet in Java (sì, questo è un albero rosso-nero dietro le quinte - ma è un albero e un set).

Tuttavia, non c'è nulla che dice che non ci possono essere valori aggiuntivi memorizzati nella posizione indicata dal valore. Una volta che hai deciso di farlo, diventa un array associativo (a volte chiamato mappa). Anche in questo caso, andando in Java per l'esempio, c'è la TreeMap .

Un esempio di questo potrebbe essere:

TreeMap<Integer, String> ageToName = new TreeMap<Integer, String>();
ageToName.put(4,"Alice");
ageToName.put(25,"Bob");
ageToName.put(16,"Charlie");

La struttura di questo sarebbe:

      16 -> Charlie          
     /             \         
    /               \        
4 -> Alice          25 -> Bob

Un albero binario bilanciato (la parte rosso-nero di quella struttura) con un figlio sinistro e un bambino destro. Puoi accedervi cercando il valore 4, o 16, o 25 e recuperare i dati associati memorizzati in quel nodo.

Un aspetto dell'albero è che non puoi avere due valori diversi con lo stesso indice. Non c'è modo con questo design di inserire anche David a 16 anni. Tuttavia, potrebbe inserire un'altra struttura di dati come un elenco anziché String nel nodo e consentire di memorizzare più elementi in tale elenco.

Ma l'albero (binario), di per sé, è un insieme che richiede che gli indici siano confrontabili (ordinabili) e che contenga solo valori distinti (senza duplicati).

Comprendi che ognuno è libero di implementare i propri alberi e set e come si occupano dell'aggiunta di un altro oggetto con la stessa chiave. Con un set di alberi, se si aggiunge un valore già esistente, la funzione di aggiunta restituisce false e lascia il set invariato. Con una TreeMap, se chiami put con una chiave già esistente, sostituisce il vecchio valore e restituisce il valore sostituito (null se non c'era nulla).

Che dovrebbe accadere è tutto ciò che è necessario che si verifichi per tale implementazione. Non ci sono tavolette inscritte che firmino tutti gli scienziati informatici che dettano come dovrebbe comportarsi qualsiasi struttura di dati astratti. Si comportano come dovrebbero e quando devono comportarsi in altri modi, documentarlo e farlo in quel modo.