Equilibrio de un árbol de búsqueda ternario

Question

¿Cómo hace uno para 'equilibrar' un árbol de búsqueda ternario? La mayoría de las implementaciones tst No balanceo de dirección, pero sugieren la inserción en un orden óptimo (que no puedo controlar.)

Answer 1

El artículo de Dr. Dobbs sobre ternario Buscar Árboles dice: D. D. Sleator y R. E. Tarjan describir algoritmos de equilibrio teóricas para ternarios árboles de búsqueda en "autoajustables árboles de búsqueda binaria" (Diario de la ACM, julio de 1985). Puede encontrar versiones en línea de este trabajo con su motor de búsqueda favorito.

Answer 2

Una optimización sencilla es hacer que sea un árbol rojo-negro, que puede evitar algunos peores escenarios. TST son realmente los árboles binarios solo cuando el valor de un nodo dado es otro TST. Así, el niño "medio" de un nodo no es realmente parte del árbol que está siendo balanceado en cada nivel, ya que no puede pasar a un padre diferente de todos modos.

Esto asegura que cada nivel del trie es recorrido en el tiempo de registro (R), a pesar de que probablemente podría hacerlo aún mejor teniendo en cuenta el tamaño de las subtries en cada nodo. Eso parece ser mucho más complicado, aunque!

Answer 3

Una generalización del árbol de búsqueda binaria es la href="http://en.wikipedia.org/wiki/B-tree" rel="nofollow">

A grandes rasgos la forma en que funciona es que si una inserción o eliminar pondría el árbol fuera de balance, se roba un elemento o un espacio de un nodo vecino. Si eso no es suficiente para mantener el árbol en equilibrio, su altura será cambiado para hacer espacio.

Answer 4

leer este artículo:

"autoajustables del ternario búsqueda intenta Uso Condicional rotaciones y aleatorizado Heurística" por "Ghada Hany * Badr y B. John Oommen †"

que le ayudará a la comprensión de auto-ajuste y el equilibrio de TST.