Albero di ricerca binario con ID e valori duplicati

Question

Albero di ricerca binario con ID e valori duplicati

#1 da (3 voti)

1

Ho difficoltà a trovare risorse per questa implementazione che sto cercando di capire. Voglio salvare i nodi in un albero di ricerca binario (auto bilanciamento) contenente un ID e un valore

struct Score
{  
  int id;
  int score;    
};

Se voglio cancellare (id = 2, score = 7), come posso cancellare questo nodo senza cancellare id = 6 o id = 5? Se cerco il nodo di cancellazione in base al valore del punteggio, allora mi scontro con gli altri nodi.

Stavo pensando di mantenere una struttura dati separata per tenere traccia delle posizioni. Devo tenere una tabella hash che salva i puntatori ai nodi padre di ciascun id?

c++ data-structures algorithms

posta Christian Gabor 06.11.2018 - 20:10

fonte

1 risposta

Leggi altre domande sui tag c++ data-structures algorithms

Come controllare le librerie comuni di versione? [duplicare] Quando utilizzare il modello di Messenger (Mediatore) nel design MVVM

score 3 · Answer 1

Un albero di ricerca binario non può avere chiavi duplicate. Tuttavia il tuo punteggio non è unico. Possibili soluzioni:

non ordinare per punteggio, ma per tupla (punteggio, id). Ad esempio, l'ID può essere usato per rompere i legami.
ogni nodo rappresenta un insieme di elementi piuttosto che un singolo elemento.

Nel tuo caso particolare, la duplicazione della chiave non è fatale se stai scrivendo la tua implementazione dell'albero: invece di cancellare ciecamente per chiave (punteggio) puoi facilmente aggiungere la verifica che l'ID corrisponda. Tuttavia, dovrai ricordare che i nodi figli possono avere chiavi uguali e devono anche essere cercati. In questo modo si ottengono i vantaggi dell'utilizzo di un BST, e io ti incoraggio vivamente a utilizzare una soluzione alternativa (come ordinare una tupla score-id).