c++ - negro - avl algoritmo
¿Por qué es el árbol avl más rápido para buscar que el árbol negro rojo? (3)
Sí.
La cantidad de pasos necesarios para encontrar un artículo depende de la distancia entre el artículo y la raíz.
Como el árbol AVL está más ajustado (es decir, tiene una altura máxima más baja), significa que hay más elementos más cerca de la raíz que en el caso rojo-negro.
El empaque apretado adicional también significa que el árbol AVL requiere más trabajo al insertar elementos. La mejor opción para cualquier aplicación depende de si se trata de una inserción intensiva o de una búsqueda intensiva ...
Lo he leído en un par de lugares que avl búsqueda de árbol más rápido, pero no puedo entender. Según tengo entendido: altura máxima del árbol rojo-negro = 2 * log (N + 1) altura del árbol AVL = 1.44 * logotipo (N + 1)
¿Es porque AVL es más corto?
El árbol AVL es mejor que el árbol rojo-negro si la tecla de entrada está casi ascendiendo / descendiendo porque entonces tendríamos que hacer una sola rotación (caso izquierda-derecha o derecha-derecha) para agregar este elemento. Además, dado que el árbol estaría bien equilibrado, la búsqueda también sería más rápida.
Pero para la clave de entrada seleccionada al azar, RBTree es mejor ya que requieren menos rotación para la inserción en comparación con AVL.
En general, depende de la secuencia de entrada, que decidiría qué tan inclinado está nuestro árbol, y la operación realizada. Para uso intensivo de inserción Árbol Rojo-Negro y para uso intensivo de búsqueda AVL.
AVL tree y RBTree tienen sus respectivas ventajas y desventajas. Lo percibirás mejor si ya has aprendido cómo funcionan.
AVL es ligeramente más rápido que RB Tree en la operación de inserción porque habrá como mucho una rotación involucrada en la inserción, mientras que puede haber dos para RBTree.
RBTree solo requiere como máximo tres rotaciones en la eliminación, pero esto no está garantizado en AVL. Por lo tanto, puede eliminar nodos más rápido que AVL.
Sin embargo, sobre todo, ambos tienen una altura de árbol logarítmica estricta.
Elija cualquier subárbol, la propiedad que hace AVL "equilibrado" garantiza que la diferencia de altura entre dos subárboles secundarios es, como máximo, uno, lo que quiere decir que, intuitivamente, todo el árbol está rígidamente equilibrado.
Pero cuando se trata de un árbol RB, la regla se vuelve probablemente "más flexible", ya que la propiedad de RBTree solo puede garantizar que la profundidad de un árbol no sea más grande que el logaritmo del número total de nodos.
Aquí hay algunos hechos que pueden ser más precisos:
La altura de un árbol AVL es estrictamente menor que: 1.44log (n + 2) -0.328 (aproximadamente)
La altura de un árbol rojo-negro es como máximo 2log (n + 1)
Consulte https://en.wikipedia.org/wiki/AVL_tree#Comparison_to_other_structures para obtener información detallada.