La mejor BST de auto compensación para la inserción rápida de una gran cantidad de nodos

votos
8

He podido encontrar detalles sobre varios auto-equilibradores BSTa través de varias fuentes, pero no he encontrado ninguna buena descripción que detalle cuál es la mejor para usar en diferentes situaciones (o si realmente no importa).

Quiero una BSTque sea óptima para almacenar más de diez millones de nodos. El orden de inserción de los nodos es básicamente aleatorio, y nunca necesitaré eliminar nodos, por lo que el tiempo de inserción es lo único que debería optimizarse.

Tengo la intención de usarlo para almacenar estados de juegos visitados previamente en un juego de rompecabezas, para que pueda verificar rápidamente si ya se ha encontrado una configuración previa.

Publicado el 05/08/2008 a las 16:40
fuente por usuario
En otros idiomas...                            


4 respuestas

votos
3

¿Por qué utilizar un BSTen absoluto? Según su descripción, un diccionario funcionará igual de bien, sino mejor.

La única razón para usar un BSTsería si quisiera enumerar el contenido del contenedor en orden clave. Ciertamente no parece que quieras hacer eso, en cuyo caso ve a la tabla hash. O(1)inserción y búsqueda, no se preocupe por la eliminación, ¿qué podría ser mejor?

Respondida el 29/08/2008 a las 01:10
fuente por usuario

votos
3

Rojo-negro es mejor que AVL para aplicaciones de inserción pesada. Si prevé una búsqueda relativamente uniforme, entonces Rojo-negro es el camino a seguir. Si prevé una búsqueda relativamente desequilibrada en la que es más probable que se visualicen elementos vistos más recientemente, querrá utilizar árboles desplegables .

Respondida el 05/08/2008 a las 16:59
fuente por usuario

votos
0

Los dos auto-balanceadores con BSTlos que estoy más familiarizado son rojo-negro y AVL, por lo que no puedo decir con certeza si hay otras soluciones mejores, pero según recuerdo, el rojo-negro tiene una inserción más rápida y una recuperación más lenta en comparación con AVL.

Entonces, si la inserción tiene una prioridad mayor que la recuperación, el rojo y negro puede ser una mejor solución.

Respondida el 05/08/2008 a las 16:50
fuente por usuario

votos
-2

[las tablas hash tienen] O (1) inserción y búsqueda

Creo que esto está mal.

En primer lugar, si limita el espacio de teclas para que sea finito, puede almacenar los elementos en una matriz y hacer una exploración lineal O (1). O puede ordenar aleatoriamente la matriz y luego hacer una exploración lineal en O (1) tiempo esperado. Cuando las cosas son finitas, las cosas son fácilmente O (1).

Entonces digamos que su tabla hash almacenará cualquier cadena de bits arbitraria; no importa mucho, siempre y cuando haya un conjunto infinito de claves, cada una de las cuales es finita. Luego debe leer todos los bits de cualquier consulta e inserción, de lo contrario inserto y0 en un hash vacío y consulta en y1, donde y0 e y1 difieren en una posición de bit único que no mira.

Pero digamos que las longitudes de las claves no son un parámetro. Si su inserción y búsqueda toman O (1), en particular el hash toma O (1) vez, lo que significa que solo mira una cantidad finita de salida de la función hash (de la cual es probable que haya solo un resultado finito, concedido )

Esto significa que con un número finito de cubos, debe haber un conjunto infinito de cadenas que tienen el mismo valor hash. Supongamos que inserto mucho, es decir, ω (1), y empiezo a consultar. Esto significa que su tabla hash tiene que recurrir a algún otro mecanismo de inserción / búsqueda O (1) para responder mis consultas. ¿Cuál, y por qué no solo usar eso directamente?

Respondida el 01/02/2009 a las 13:49
fuente por usuario

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more