El uso de un árbol 2-3-4 en lugar de un árbol biselado
-
10-10-2019 - |
Pregunta
Estoy en un curso de estructuras de datos en este momento y hemos aprendido acerca de 2-3-4 árboles y árbol biselado. Me preguntaba en qué circunstancias utilizar un árbol 2-3-4 en lugar de un árbol biselado? Los dos son auto equilibrio y ordenados, así que no veo que gran parte de la diferencia entre ellos.
Solución
2-3-4 árbol sólo cambia la estructura de inserciones y supresiones, mientras que un splay-árbol también reorganiza los nodos en las búsquedas.
árbol biselado será, gracias a la reorganización de las operaciones de búsqueda, proporcionar respuestas más rápido si su patrón de uso típico pasa a buscar un pequeño subconjunto de los elementos de la mayoría de las veces.
Es posible implementar un árbol 2-3-4 de tal manera que el elemento más pequeño se puede consultar en O (1), pero en general tanto la inserción oferta y deleción en O amortizado (log n).