Crear un árbol de búsqueda binaria equilibrada a partir de una secuencia de enteros

Question

Acabo de terminar una entrevista de trabajo y estaba luchando con esta pregunta, que me parece una pregunta muy difícil para dar una entrevista de 15 minutos.

Escriba la siguiente pregunta: Escriba una función que genere un flujo de enteros (desordenados) y genere un árbol de búsqueda equilibrado. Ahora, no puede esperar a que finalice la entrada (es una secuencia), por lo que necesita equilibrar el árbol sobre la marcha.

Mi primera respuesta fue utilizar un árbol Rojo-Negro, que por supuesto hace el trabajo, pero tengo que suponer que no esperaban que implementara un árbol negro rojo en 15 minutos.

Entonces, ¿hay alguna solución simple para este problema que no conozco?

Gracias,

de Dave

Answer 1

AA Trees son un poco más simple que los árboles rojo-Negro, pero no pude poner en práctica uno de la parte superior de la cabeza.

Answer 2

Personalmente, creo que la mejor manera de hacerlo sería buscar un árbol de búsqueda binaria aleatorio como treap. Esto no garantiza absolutamente que el árbol estará equilibrado, pero con una alta probabilidad, el árbol tendrá un buen factor de equilibrio. Un fraude funciona aumentando cada elemento del árbol con un número uniformemente aleatorio, y luego asegurando que el árbol es un árbol de búsqueda binario con respecto a las claves y un montón con respecto a los valores aleatorios uniformes. La inserción en un fraude es extremadamente fácil:

1. Elija un número aleatorio para asignar al elemento recién agregado.
2. Inserte el elemento en la BST utilizando la inserción estándar BST.
3. Mientras que la clave del elemento recién insertado es mayor que la clave de su elemento principal, realice una rotación de árbol para colocar el nuevo elemento por encima de su elemento primario.

Ese último paso es el único realmente difícil, pero si tuvieras algo de tiempo para resolverlo en una pizarra, estoy bastante seguro de que podrías implementarlo sobre la marcha en una entrevista.

Otra opción que podría funcionar sería usar un splay tree. Es otro tipo de BST rápida que puede implementarse suponiendo que tiene una función de inserción BST estándar y la capacidad de hacer rotaciones de árboles. Es importante destacar que los árboles de separación son extremadamente rápidos en la práctica, y se sabe que son (dentro de un factor constante) al menos tan buenos como cualquier otro árbol de búsqueda binaria estático.

Dependiendo de lo que significa "árbol de búsqueda", también podría considerar almacenar los enteros en una estructura optimizada para la búsqueda de enteros. Por ejemplo, puede usar un bitwise trie para almacenar los números enteros, lo que permite una búsqueda en tiempo proporcional al número de bits en una palabra de máquina. Esto se puede implementar bastante bien utilizando una función recursiva para examinar los bits y no requiere ningún tipo de rotaciones. Si necesitara lanzar una implementación en quince minutos, y si el entrevistador le permite desviarse de los árboles de búsqueda binarios estándar, entonces esta podría ser una gran solución.

Espero que esto ayude!

Answer 3

Uno de los árboles de búsqueda binaria más simple es el árbol BB (α). Usted elige la constante α, que dice cuánto puede desequilibrarse el árbol. En todo momento, #descendants(child) <= (1-α) × #descendants(node) debe contener. Lo trata como un árbol de búsqueda binaria normal, pero cuando la fórmula ya no se aplica a ningún nodo, simplemente reconstruye esa parte del árbol desde cero, de modo que esté perfectamente equilibrado.

La complejidad del tiempo amortizado para la inserción o eliminación sigue siendo O (log N), al igual que con otros árboles binarios balanceados.