Tengo una comprensión básica de cómo 2-3-4 trees mantiene la operación de propiedad de equilibrio de altura después de la operación para asegurarse de que incluso las operaciones en el peor de los casos sean O (n logn).¿Por qué no utilizamos 2-3 o 2-3-4-5 árboles?
Pero no lo entiendo lo suficiente como para saber por qué solo 2-3-4?
¿Por qué no 2-3 o 2-3-4-5, etc.?
Para ser sincero, no tenía conocimiento de 2-3-4 árboles. En mi clase Data Structures, nos enseñaron de 2 a 3 árboles, y para ser honestos, la mayoría de nosotros implementamos árboles AVL para la parte húmeda del ejercicio.
Pero aparentemente, hay una generalización de este tipo de árbol: (a,b) tree.
¡Interesante! Esto significa que no podemos tener 3-4 árboles, y no estoy seguro de por qué? – Lazer
No estoy seguro tampoco. Este parece ser un árbol bastante teórico, y no uno usualmente explorado ... No hay mucho en (a, b) árboles en la red. – cha0site
Un árbol de vectores, agradable. :-) –
La implementación de 2-3-4 árboles generalmente requiere varias clases (2NODE, 3NODE, 4NODE) o simplemente tiene NODO que tiene una matriz de elementos. En el caso de múltiples clases, se pierde mucho tiempo construyendo y destruyendo instancias de nodo y reparentándolas es engorroso. Si utiliza una sola clase con matrices para contener elementos y elementos secundarios, entonces cambia el tamaño de las matrices constantemente, lo que es un desperdicio similar o termina gastando más de la mitad de su memoria en elementos de matriz no utilizados. Simplemente no es muy eficiente en comparación con los árboles Rojo-Negro.
Los árboles rojo-negro tienen solo un tipo de estructura de nodo. Como los árboles Rojo-Negros tienen una dualidad con 2-3-4 árboles, los árboles RB pueden usar los mismos algoritmos exactos que los árboles 2-3-4 (sin necesidad de las implementaciones estúpidamente confusas/complejas descritas en Cormen, Leiserson y Rivest que llevaron a árboles AA que no son menos complejos que el algoritmo 2-3-4).
Por lo tanto, árboles rojo-negro por su facilidad de implementación más su eficiencia de memoria/CPU. (Los árboles AVL también son buenos. Producen árboles más equilibrados y son estúpidos simplemente para codificar, pero tienden a ser menos eficientes porque trabajan muy a menudo para mantener solo un árbol un poco más compacto). 3-4-5-6 ... etc no se hacen porque no se gana nada. 2-3-4 tiene una ganancia neta de 2-3 árboles porque pueden realizarse fácilmente sin recurrencia (la recursión tiende a ser menos eficiente, especialmente cuando no se puede codificar de forma recursiva). Sin embargo, B-Trees y Bplus-Trees son casi 2-3-4-5-6-7-8-9-etc árboles donde el tamaño máximo de los nodos, n, se elige para que n registros se puedan almacenar en un solo sector de disco. (es decir, cada sector de disco es un nodo en el árbol y el tamaño del sector es equivalente a la cantidad de elementos almacenados en el nodo). Esto se debe a que el tiempo de búsqueda de 512 registros linealmente en la memoria es MUCHO más rápido que el desplazamiento hacia abajo un nivel en el árbol que requiere otro disco de búsqueda/recuperación. y O (512) sigue siendo O (1) y por lo tanto mantiene O (lg n) para el árbol.
Si alguna vez implementó un árbol 2-3-4 o rojo-negro, sabría que no es muy trivial hacerlo bien y luego probarlo. Incluso hay una versión simplificada del árbol rojo-negro, el [árbol AA] (http://en.wikipedia.org/wiki/AA_tree), que es menos simétrico que el árbol rojo-negro, pero parece ser una una buena alternativa que tiene una menor complejidad de implementación. Cuando necesita más subnodos o árboles más planos, opta por árboles b y admite explícitamente muchos subnodos de manera uniforme. –
Además, siempre existe la preocupación sobre la ubicación de los datos y la sobrecarga por nodo (debido a los costos del asignador). Este tipo de preocupaciones tienden a fomentar soluciones basadas en matrices (por ejemplo, tablas hash) en la práctica. –