Lo he leído en un par de lugares que avl búsqueda de árbol más rápido, pero no puedo entender. Como yo lo entiendo: altura máxima de árbol rojo-negro = 2 * log (N + 1) altura del árbol AVL = 1,44 logotipo * (N + 1)¿Por qué es el árbol avl más rápido para buscar que el árbol negro rojo?
¿Es porque AVL es más corto?
Sí.
El número de pasos necesarios para encontrar un artículo depende de la distancia entre el elemento 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.
La empaquetadura extra apretada 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 es una inserción intensiva o una búsqueda intensiva ...
+1 Buena explicación – cnicutar
Una buena explicación. Solo puedo agregar algunos números: la diferencia máxima entre las profundidades del nodo en el árbol AVL es 1, en el árbol R-B un nodo puede ser dos veces más profundo que el otro nodo (la profundidad es la distancia entre el nodo y la raíz). Pero las inserciones y eliminaciones en el árbol R-B requieren 3 rotaciones al máximo, mientras que el árbol AVL podría requerir un número de rotaciones igual a la profundidad del árbol. (la rotación es una operación fundamental en árboles equilibrados, no la describiré aquí) –
Árbol AVL es mejor que el árbol rojo-negro si la tecla de entrada es casi ascendente/descendente porque entonces tendríamos que hacer una sola rotación (caso izquierda-izquierda 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ía como mucho una rotación involucrada en la inserción, mientras que podría haber dos para RBTree.
RBTree solo requieren como máximo tres rotaciones en el borrado, 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, es decir, de forma intuitiva, todo el árbol está rígidamente equilibrado.
Pero cuando se trata de un árbol de RB, la regla se vuelve más "floja", ya que la propiedad de RBTree solo puede garantizar que la profundidad de un árbol no sea más del doble del logaritmo del número total de nodos.
Acá algunos datos que pueden ser más preciso:
altura deUn AVL árbol es estrictamente menor que: 1.44log (n + 2) -0,328 (aproximadamente)
A red- la altura del árbol 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.
Lea un libro sobre estructuras de datos. Pero si recuerdo (fuera de mi cabeza) correctamente, un árbol AVL se aproxima más a estar perfectamente equilibrado que un árbol RB, a costa de un inserto en un AVL que es considerablemente más caro que un RB. –
Sí porque es más corto y, por lo tanto, tiene menos nodos de arriba a abajo. Tal vez una imagen sería útil: http://en.wikipedia.org/wiki/File:AVL_Tree_Rebalancing.svg – 0x4f3759df