¿Cómo se puede 'equilibrar' un árbol de búsqueda ternario? La mayoría de las implementaciones de tst no abordan el equilibrio, pero sugieren insertarlas en un orden óptimo (que no puedo controlar)Equilibrar un árbol de búsqueda ternario
El artículo en el Dr. Dobbs sobre Ternary Search Trees dice: D.D. Sleator y R.E. Tarjan describe algoritmos de equilibrio teóricos para árboles de búsqueda ternarios en "árboles de búsqueda binaria autoajustables" (Journal of the ACM, julio de 1985). Puede encontrar versiones en línea de este documento con su motor de búsqueda favorito.
Una generalización del árbol de búsqueda binaria es B-Tree, que funciona para fanouts desde 2 en adelante. Esa no es la única forma de hacerlo, pero es común.
En términos generales, la forma en que funciona es que si un inserto o eliminación pone al árbol fuera de balance, roba un elemento o un espacio de un nodo vecino. Si incluso eso no es suficiente para mantener el árbol en equilibrio, se cambiará su altura para hacer espacio.
El OP habla de árboles de búsqueda ** ternarios **. – hmuelner
No estoy del todo claro acerca de cómo un 1-2 B-Tree difiere de un árbol ternario. Me lo puedes explicar? – SingleNegationElimination
Un B-Tree (normalmente) contiene las claves completas en los nodos. En un árbol de búsqueda ternario, la clave está definida por la ruta al nodo. – hmuelner
lea este artículo:
"auto-ajustable de búsqueda intenta ternario El uso de condicionales rotaciones y aleatorizado Heurística" por "Ghada Hany * Badr y B. John Oommen †"
que le ayudará para entender TST autoajustable y equilibrado.
¿Qué tamaño tiene un árbol de búsqueda? –
Un par de miles de palabras que van desde 4 hasta 20 caracteres. No estoy seguro si eso es grande o pequeño, pero es grande para mí. – uroc
Suena como tirar el árbol cuando llega a cierto punto y reemplazarlo con un árbol construido con "el orden óptimo" es su mejor opción: debería tomar milisegundos, si puede dedicarle tiempo. –