Albero di ricerca binario per intenzioni specifiche

Question

Sappiamo tutti che ci sono un sacco di alberi binari di ricerca auto-bilanciati (BST), che sono i più famosi Red-Black e AVL. Potrebbe essere utile dare un'occhiata anche agli alberi AA e agli alberi di capro espiatorio.

Voglio eliminare le inserzioni e le ricerche, come qualsiasi altro BST. Tuttavia, sarà comune eliminare tutti i valori in un determinato intervallo o eliminare interi sottotitoli. Quindi:

1. Voglio inserire, cercare, rimuovere valori in O (log n) (albero bilanciato).
2. Vorrei eliminare una sottostruttura, mantenendo l'intero albero bilanciato, in O (log n) (caso peggiore o ammortizzato)
3. Potrebbe essere utile per eliminare più valori di una riga, prima di bilanciare l'albero
4. io molto spesso inserisco 2 valori immediatamente, tuttavia questa non è una regola (solo un suggerimento nel caso ci sia una struttura di dati ad albero che ne tiene conto)

esiste una variante di AVL o RB questo mi aiuta su questo? Gli alberi del capro espiatorio assomigliano più a questo, ma avrebbero bisogno anche di alcuni cambiamenti, chiunque abbia esperienza con loro può condividere alcuni pensieri?

Più precisamente, quale procedura di bilanciamento e/o procedura di rimozione mi aiuterebbe a mantenere questa azione efficiente in termini di tempo?

Answer 1

È possibile eliminare un intervallo di valori un BST in O (logn + oggetti num).

Il modo più semplice che conosco è di lavorare con la struttura dati Deterministic Skip List (si potrebbe voler leggere un po 'su questa struttura dati prima di andare avanti). Nell'elenco dei salti deterministici tutti i valori reali sono memorizzati nel livello inferiore e vi sono dei puntatori ai livelli superiori. Inserisci, cerca e rimuovi sono fatti in O (logn).

L'operazione gamma eliminazione può essere fatto secondo il seguente algoritmo:

• Trova il primo elemento della gamma - O (log n)
• Vai avanti nella lista collegata, e rimuovere tutti gli elementi che sono ancora nel raggio d'azione. Se ci sono elementi con puntatori ai livelli superiori - rimuovili anche tu, fino a raggiungere il livello più alto (rimozione da un elenco collegato) - O (numero di oggetti cancellati)
• Correggi i puntatori per adattarli all'elenco dei salti deterministici (2-3) elementi tra ogni puntatore verso l'alto)

La complessità totale dell'eliminazione del campo è O (logn + numero di oggetti nell'intervallo). Si noti che se si sceglie di lavorare con un elenco di salto casuale, si ottiene la stessa complessità, ma in media, e non nel peggiore dei casi. Il vantaggio è che non è necessario correggere i puntatori di livello superiore per soddisfare la domanda 2-3.

Una lista di salto deterministico ha una mappatura 1-1 su un albero 2-3, quindi con un po 'più di lavoro, la procedura descritta sopra potrebbe funzionare anche per un albero 2-3.

Answer 2

Hmm, che dire degli alberi B? Sono anche bilanciati, e se scegli uno di grande ordine --- dipende da quanti oggetti hai ---, risparmierai un sacco di tempo di creazione/distruzione dell'oggetto.

A 2. Se si dispone di un albero B di ordine 100, è possibile rimuovere fino a 100 voci mediante una chiamata di funzione.

A 3. Questa funzione può essere applicata a quasi tutti gli alberi, basta implementare una funzione RemoveSome() che rimuove gli elementi N e fa un ribilanciamento. Per gli alberi B, è un po 'più complicato, ma può essere fatto.

Nota: suppongo che tu sia un programmatore. Se hai bisogno di una soluzione completa, testata e pronta per l'acquisto, hai bisogno di un'altra risposta.

Answer 3

Molto tempo fa nei giorni pre-STL ho scritto il mio algoritmo B-Tree (BST) perché avevo un set di dati piuttosto grande al momento (circa 700K elementi in 2 alberi che erano interdipendenti). Ho trovato che riequilibrare dopo ogni 100-200 inserzioni/delezioni era il picco di prestazioni che potevo ottenere in quel momento sulla base della sperimentazione su hardware 486 e SGI. Questo numero potrebbe essere diverso ora o forse no dal momento che sembra essere un limite di ottimizzazione algoritmica a meno che non si converta in un modello parallelo.

In breve, è possibile applicare un trigger di modifica per il ribilanciamento e consentire il riequilibrio forzato quando si sono completate tutte le modifiche.

Il miglioramento è stato notevole. Il carico rettilineo iniziale non era completo dopo 25m (ha ucciso il processo). Il ribilanciamento, anche quando siamo andati, è stato ucciso dopo 15 m. La modifica limitata carica con un ribilanciamento ogni 100 mod caricate e corse in meno di 3m. Si noti che durante la parte "run", c'erano 0-8 modifiche all'albero per ogni voce iniziale. Hai davvero bisogno di considerare se hai sempre bisogno di essere in equilibrio quando l'albero verrà nuovamente modificato nel breve periodo.

Answer 4

Dovrebbe essere facile implementare l'eliminazione di un nodo e dei suoi sottonodi in un albero AVL se ogni nodo memorizza la sua altezza anziché un fattore di equilibrio. Dopo aver eliminato un nodo, continua a ruotare finché i due nodi figlio non differiscono di uno. Quindi sposta l'albero e ripeti. L'unica vera differenza rispetto a una cancellazione normale sarà un while anziché uno if per il test delle altezze.

Answer 5

L'implementazione Set nella libreria standard OCaml è un albero AVL puramente funzionale che soddisfa tutte le vostre esigenze e, in particolare, ha implementazioni molto efficienti di operazioni teoriche dell'insieme (unione, intersezione, differenza). Inserimento e cancellazione sono O (log n). È possibile rimuovere sottostrutture ed esecuzioni di elementi rappresentandoli come un insieme e utilizzando la differenza di set. È possibile inserire due elementi contemporaneamente creando un set di 2 elementi e applicando il set union.