Gestione chiavi duplicati all'interno di un albero AVL

Question

Voglio fare il mio supporto avl-tree chiavi duplicate, ma c'è un problema con il comportamento predefinito del binary search tree con i duplicati che la rotazione potrebbe fare nodi con uguale chiave sulla sinistra e il diritto del genitore.

Per esempio, quando l'aggiunta di tre nodi il tutto con il tasto A causerà l'albero per fare una rotazione di essere qualcosa di simile:

   A
  /  \ 
 A    A

In modo da ottenere tutte le voci con quella chiave sarà un problema ... e la ricerca in entrambe le direzioni non è buona.

La soluzione che ho pensato è fare esercizi ogni nodo un array di duplicati così quando si aggiunge un nuovo elemento già esistente sarà solo l'aggiunta di un nuovo elemento alla matrice, rimozione di voce con il tasto cancellerà l'intero nodo mentre il trovare tutti gli elementi con chiave tornerà tale matrice.

sono ci sono altri metodi per gestire i duplicati?

La voce inserto prende una chiave e un valore .. quindi ho bisogno di memorizzare i valori inorder per restituirli dal findAll con un certo metodo chiave.

Answer 1

Un altro approccio generale è quello di rendere internamente la parte di valore della chiave in modo che non hanno davvero più chiavi duplicate. Avrete bisogno sia la chiave e il valore in ogni caso, al fine di eliminare una voce da un albero che consente duplicati.

Per verificare la chiave senza conoscere il valore, si dovrebbe poi fare qualcosa di simile (pseudo-codice):

searchResult = myTree.SearchGreaterOrEqual(Key);
found = (searchResult != null) && (searchResult.Key == Key);

Answer 2

Vi ciascun nodo contiene un conteggio: aggiunta di duplicati incrementerà il conteggio, appariranno rimozioni diminuire il conteggio meno che non sia 1, nel qual caso verrà rimossa l'intero nodo

.