El mejor BST autoequilibrado para la inserción rápida de una gran cantidad de nodos

Question

He podido encontrar detalles sobre varios sistemas de autoequilibrio. BSTBuscamos en varias fuentes, pero no he encontrado ninguna buena descripción que detalle cuál es mejor usar en diferentes situaciones (o si realmente no importa).

quiero un BST eso es óptimo 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 anteriormente en un juego de rompecabezas, de modo que pueda verificar rápidamente si ya se ha encontrado una configuración anterior.

Answer 1

Negro rojo es mejor que AVL para aplicaciones con mucha inserción.Si prevé una apariencia relativamente uniforme, entonces el rojo-negro es el camino a seguir.Si prevé una búsqueda relativamente desequilibrada en la que es más probable que los elementos vistos más recientemente se vuelvan a ver, le recomendamos utilizar árboles extendidos.

Answer 2

¿Por qué utilizar un BST ¿en absoluto?Según su descripción, un diccionario funcionará igual de bien, si no mejor.

La única razón para utilizar un BST sería si quisiera enumerar el contenido del contenedor en orden de claves.Ciertamente no parece que quieras hacer eso, en cuyo caso opta por la tabla hash. O(1) inserción y búsqueda, no te preocupes por la eliminación, ¿qué podría ser mejor?

Answer 3

Los dos autoequilibrados BSTLos que más conozco son el rojo y el negro. AVL, por lo que no puedo decir con certeza si otras soluciones son 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 es una prioridad más alta que la recuperación, el rojo-negro puede ser una mejor solución.

Answer 4

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

Creo que esto está mal.

En primer lugar, si limita el espacio de claves para que sea finito, puede almacenar los elementos en una matriz y realizar un escaneo lineal O(1).O puede ordenar aleatoriamente la matriz y luego realizar una exploración lineal en el tiempo esperado O(1).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 sea finita.Luego debe leer todos los bits de cualquier consulta y entrada de inserción; de lo contrario, inserto y0 en un hash vacío y consulto en y1, donde y0 e y1 difieren en una posición de un solo bit que no se 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) tiempo, lo que significa que solo observa una cantidad finita de salida de la función hash (de la cual es probable que ser sólo una producción finita, por supuesto).

Esto significa que con un número finito de depósitos, debe haber un conjunto infinito de cadenas que tengan el mismo valor hash.Supongamos que inserto mucho, es decir.ω(1), de esos, y comience 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 usarlo directamente?