Mejor BST autoequilibrante para la inserción rápida de una gran cantidad de nodos

Question

He podido encontrar detalles sobre varios autoconfigurados BST a 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 un BST que 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 utilizarlo 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.

Answer 1

Red-black 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 donde es más probable que se visualicen elementos vistos más recientemente, querrá usar splay trees.

Answer 2

Los dos BST s autobalanceados que estoy más familiarizado con son de color rojo-negro y AVL, así que no puedo decir con certeza si algunas otras soluciones son mejores, pero por lo que recuerdo, rojo-negro tiene la inserción más rápida y una recuperación más lenta en comparación con AVL.

Por lo tanto, si la inserción tiene una prioridad mayor que la recuperación, rojo-negro puede ser una solución mejor.

Answer 3

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

La única razón para usar un BST sería si quisiera enumerar el contenido del contenedor en orden de 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?

Answer 4

tablas hash [han] O (1) de 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).

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 observa una cantidad finita de salida de la función hash (de la cual es probable que sea solo una salida finita 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 un lote, 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?