Gestione chiavi duplicate all'interno di un albero AVL

Question

Voglio rendere il mio avl-tree supporto chiavi duplicate ma c'è un problema con il comportamento predefinito dello binary search tree con duplicati che la rotazione potrebbe fare nodi con chiave uguale sia a sinistra sia a destra di il genitore.

Per esempio, quando l'aggiunta di tre nodi il tutto con il tasto A farà sì che 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 di sta facendo ciascuna esercizi nodo un array di duplicati così quando si aggiunge un nuovo elemento che esiste già sarà solo l'aggiunta di un nuovo elemento dell'array, rimuovendo elemento con chiave verrà cancellata nodo mentre il trova tutti gli elementi con chiave restituirà quell'array.

Esistono altri metodi per gestire i duplicati?

L'elemento di inserimento accetta una chiave e un valore .. quindi è necessario memorizzare i valori in ordine per restituirli tramite findAll con un determinato metodo chiave.

Answer 1

Un altro approccio generale consiste nel rendere internamente il valore parte della chiave in modo da non avere più chiavi duplicate. Avrai bisogno sia della chiave che del valore per eliminare una voce da un albero che consente duplicati.

Per cercare una chiave senza conoscere il valore, si dovrebbe quindi fare qualcosa di simile (pseudo-codice):

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

Answer 2

Ogni nodo contiene un conteggio: l'aggiunta di duplicati incrementerà il conteggio, le rimozioni diminuiranno il conteggio a meno che non sia 1, nel qual caso verrà rimosso l'intero nodo.