Bilanciamento un albero di ricerca ternario

Question

Come si fa a 'bilanciamento' un albero di ricerca ternario? La maggior parte delle implementazioni TST non affrontano il bilanciamento, ma suggeriscono l'inserimento in un ordine ottimale (che non posso controllare.)

Answer 1

L'articolo in Dr. Dobbs sulla ternario Cerca Alberi dice: D.D. Sleator e R.E. Tarjan descrivere algoritmi di bilanciamento teorici per alberi di ricerca ternari in "Auto-Regolazione Binary Search Trees" (Journal of the ACM, luglio 1985). Potete trovare le versioni online di questo documento con il vostro motore di ricerca preferito.

Answer 2

Una semplice ottimizzazione è quello di rendere un albero rosso-nero, che può evitare alcuni scenari peggiori. TST sono davvero alberi binari solo quando il valore di un dato nodo è un altro TST. Così, il bambino "di mezzo" di un nodo non è realmente parte dell'albero che viene bilanciata ad ogni livello, in quanto non può passare a un genitore diverso in ogni caso.

In questo modo, ogni livello del trie è attraversato nel registro tempo (R), anche se probabilmente si potrebbe fare ancora meglio, tenendo conto delle dimensioni dei subtries in ogni nodo. Che sembra essere molto più complicato però!

Answer 3

Una generalizzazione del albero binario di ricerca è il B-Tree , che lavora per fanout ovunque da 2 e fino. Questo non è l'unico modo per farlo, ma è un comune.

Circa il modo in cui funziona è che se un inserto o cancellare avrebbe messo l'albero fuori equilibrio, ruba un elemento o uno spazio da un nodo adiacente. Se anche questo non è sufficiente per mantenere l'albero in equilibrio, la sua altezza sarà cambiato per fare spazio.

Answer 4

leggere questo articolo:

"Self-regolazione del ternario Cerca cerca Utilizzando condizionale rotazioni e randomizzato euristica" di "Ghada Hany Badr * e B. Giovanni Oommen †"

che vi aiuterà a capire di auto-regolazione e bilanciamento TST.