Árbol negro rojo sobre árbol avl

108

Los árboles AVL y rojo negro se autoequilibran, excepto el rojo y el negro en los nodos. ¿Cuál es la razón principal para elegir árboles negros rojos en lugar de árboles AVL? ¿Cuáles son las aplicaciones de los árboles negros rojos?

algorithm data-structures red-black-tree suren
fuente
2
posible duplicado de ¿Por qué se implementa std :: map como árbol rojo-negro?
Lior Kogan
1
Además, los desarrolladores de Rust optaron por usar un árbol B en lugar de cualquiera de estos para su mapa ordenado estándar.
Tom Anderson

Respuestas:

122

¿Cuál es la razón principal para elegir árboles negros rojos en lugar de árboles AVL?

Ambos árboles rojo-negro y árboles AVL son los más comúnmente utilizados equilibradas árboles de búsqueda binaria y apoyan la inserción, eliminación y consulta de la garantía O(logN) time. Sin embargo, existen los siguientes puntos de comparación entre los dos:

  • Los árboles AVL tienen un equilibrio más rígido y, por lo tanto, proporcionan búsquedas más rápidas. Por lo tanto, para una tarea intensiva de búsqueda, use un árbol AVL.
  • Para insertar tareas intensivas, utilice un árbol rojo-negro.
  • Los árboles AVL almacenan el factor de equilibrio en cada nodo. Esto ocupa O(N)espacio adicional. Sin embargo, si sabemos que las claves que se insertarán en el árbol siempre serán mayores que cero, podemos usar el bit de signo de las claves para almacenar la información de color de un árbol rojo-negro. Por lo tanto, en tales casos, el árbol rojo-negro no ocupa espacio adicional.

¿Cuáles son las aplicaciones del árbol negro rojo?

Los árboles rojo-negros son de uso más general. Lo hacen relativamente bien en agregar, eliminar y buscar, pero los árboles AVL tienen búsquedas más rápidas a costa de agregar / quitar más lentamente. El árbol rojo-negro se usa en lo siguiente:

  • Java: java.util.TreeMap,java.util.TreeSet
  • C ++ STL (en la mayoría de las implementaciones): mapa, multimapa, multiset
  • Kernel de Linux: programador completamente justo, linux / rbtree.h
Nikunj Banka
fuente
43
In general, the rotations for an AVL tree are harder to implement and debug than that for a Red-Black tree.no es verdad.
Jingguo Yao
9
Para ser pedante, el estándar C ++ no exige eso std:: mapy los amigos usan una estructura en particular. Eso queda a la implementación, aunque libstdc ++ y Dinkumware al menos usan árboles rojo-negro, y parece que tiene razón en la práctica.
mbozzi
25
El factor de equilibrio almacenado en cada nodo de un árbol AVL es de dos bits (-1 / 0 / +1). Un árbol rojo-negro almacena un bit de información de color en cada nodo. Por lo tanto, en total, ambos árboles requieren memoria O (N) para la información adicional.
Seppo Enarvi
5
"Para insertar tareas intensivas, use un árbol rojo-negro". ¿Por qué? La inserción del árbol AVL solo requiere una rotación en el peor de los casos, mientras que el árbol Rojo Negro puede tomar dos.
Daniel
3
Esto debería actualizarse según el análisis de Ben Pfaff de 2003 sobre el rendimiento de BST: los árboles AVL son de uso más general y funcionan mejor. Sería interesante rastrear las razones históricas exactas por las que Java, C ++ y el kernel de Linux eligieron la implementación más lenta.
David McManamon
16

Intenta leer este artículo

Ofrece buenas perspectivas sobre diferencias, similitudes, rendimiento, etc.

Aquí hay una cita del artículo:

Los árboles RB son, al igual que los árboles AVL, autoequilibrados. Ambos proporcionan rendimiento de búsqueda e inserción de O (log n).

La diferencia es que RB-Trees garantiza O (1) rotaciones por operación de inserción. Eso es lo que realmente cuesta rendimiento en implementaciones reales.

Simplificado, los RB-Trees obtienen esta ventaja al ser conceptualmente 2-3 árboles sin llevar la sobrecarga de las estructuras dinámicas de los nodos. Físicamente, los árboles RB se implementan como árboles binarios, las banderas rojas / negras simulan un comportamiento 2-3

Según mi propio entendimiento, los árboles AVL y los árboles RB no están muy lejos en términos de rendimiento. Un árbol RB es simplemente una variante de un árbol B y el equilibrio se implementa de manera diferente a un árbol AVL.

Jordán
fuente
1
AFIAK, un árbol AVL también tiene O (1) rotación por inserción. Para RB-tree y AVL, una inserción puede tener 1 o 0 rotaciones. Si ocurre la rotación, los algoritmos se detienen. Si no sucede, por lo general, los algoritmos continúan revisando / repintando los nodos desde la parte inferior hasta la raíz del árbol. Entonces, a veces la rotación O (1) puede ser mejor porque elimina el escaneo de los elementos restantes O (log (n)). Debido a que el árbol AVL, en promedio, hace más rotación, el árbol AVL generalmente tiene un mejor equilibrio ~ 1,44 log (N) que el árbol RB 2 log (N).
Sergey Shandar
4

Nuestra comprensión de las diferencias en el rendimiento ha mejorado a lo largo de los años y ahora la razón principal para usar árboles rojo-negro sobre AVL sería no tener acceso a una buena implementación de AVL, ya que son un poco menos comunes, quizás porque no están cubiertos en CLRS.

Ambos árboles ahora se consideran formas de árboles de rango equilibrado, pero los árboles rojo-negro son consistentemente más lentos en aproximadamente un 20% en las pruebas del mundo real . O incluso un 30-40% más lento cuando se insertan datos secuenciales .

Entonces, las personas que han estudiado árboles rojo-negros pero no árboles AVL tienden a elegir árboles rojo-negro. Los usos principales de los árboles rojo-negro se detallan en la entrada de Wikipedia para ellos .

David McManamon
fuente
1
¡Gracioso! en mi lectura, el artículo de libavl parece decir que AVL y RB están cara a cara, y ninguno es claramente mejor que el otro en general (cuál es mejor depende de la carga de trabajo). No veo en ninguna parte una afirmación de que AVL sea en general un 20% más rápido.
Stefan
3

Otras respuestas aquí resumen bien los pros y los contras de los árboles RB y AVL, pero encontré esta diferencia particularmente interesante:

Los árboles AVL no admiten el costo de actualización amortizado constante [pero los árboles rojo-negro sí]

Fuente: Mehlhorn y Sanders (2008) (sección 7.4)

Entonces, mientras que los árboles RB y AVL garantizan O (log (N)) en el peor de los casos para la búsqueda, inserción y eliminación, la restauración de la propiedad AVL / RB después de insertar o eliminar un nodo se puede hacer en O (1) tiempo amortizado para árboles rojo-negros.

emanek
fuente
Creo que la inserción del árbol AVL tiene el mismo costo amortizado / similar, pero produce un árbol mejor equilibrado (1.44log (N) vs 2log (N)). Al mismo tiempo, la eliminación en el árbol AVL puede requerir más rotaciones. En mi humilde opinión, esto se aborda en WAVL en.wikipedia.org/wiki/WAVL_tree
Sergey Shandar
1

A los programadores generalmente no les gusta asignar memoria dinámicamente. El problema con el árbol avl es que para "n" elementos necesitas al menos log2 (log2 (n)) ... (altura-> log2 (n)) bits para almacenar la altura del árbol. Entonces, cuando maneja datos enormes, no puede estar seguro de cuántos bits asignar para almacenar la altura en cada nodo.

Por ejemplo, si usa 4 bytes int (32 bits) para almacenar la altura. La altura máxima puede ser: 2 ^ 32 y, por lo tanto, la cantidad máxima de elementos que puede almacenar en el árbol es 2 ^ (2 ^ 32) - (parece ser muy grande, pero en esta era de datos, supongo que nada es demasiado grande). Y, por lo tanto, si supera este límite, debe asignar dinámicamente más espacio para almacenar la altura.

¡Esta es una respuesta sugerida por un profesor de mi universidad que me pareció razonable! Espero tener sentido.

Ediciones: los árboles AVL están más equilibrados en comparación con los árboles rojos y negros, pero pueden causar más rotaciones durante la inserción y eliminación. Entonces, si su aplicación implica muchas inserciones y eliminaciones frecuentes, entonces se deberían preferir los árboles Red Black. Y si las inserciones y eliminaciones son menos frecuentes y la búsqueda es una operación más frecuente, entonces se debe preferir el árbol AVL sobre el árbol rojo negro. --Fuente GEEKSFORGEEKS.ORG

Prakhar Agrawal
fuente
1
Yo diría que esto es interesante pero poco práctico. Si bien es cierto que en el caso más compacto sería una tarea difícil elegir la cantidad más eficiente de bits para asignar la altura, en la práctica cualquier espacio sobrante que sea menor a un byte definitivamente no se utilizará, y todo lo que sobra en un espacio de 4 o incluso 8 bytes es casi seguro que no se utilizará. La memoria no se asigna sin alinear por razones de rendimiento que anulan en gran medida el beneficio de recuperar una pequeña cantidad de espacio. Los punteros a los hijos y el valor ocupan 24 bytes; Es poco probable que 8 más tengan algún costo práctico.
Mumbleskates
4
you need need atleast log2(log2(n))...(height->log2(n)) bits to store the height of [an AVL] treeNo necesito la altura de ningún nodo en un árbol AVL para implementarlo. Necesitas un poco de información adicional para cada nodo ( YO SOY EL MÁS GRANDE (el hermano con el subárbol más alto)); Es más conveniente y convencional tener dos bits adicionales (el niño es más alto para izquierda y derecha), como lo presentaron AV & L.
greybeard
4
2 ^ (2 ^ 32) elementos es mucho ... como si pudieras almacenar cada molécula en todo el universo, y cada par posible de esas moléculas, y cada triple posible, y aún ni siquiera comenzar a acercarse ni remotamente a estar dentro de una pequeña fracción de un pequeño porcentaje de la raíz cúbica de ese número dividido por cien quintillones.
punto
4
Esto es muy engañoso. Primero, no necesitamos almacenar la altura en un nodo de un árbol AVL. En segundo lugar, incluso si lo hiciéramos, e incluso si la cantidad típica de memoria disponible se duplica cada año, todavía tenemos 4 mil millones de años hasta que la altura de nuestros árboles supere lo que se puede almacenar en 32 bits.
Gassa
3
2 ^ (2 ^ 32) objects es ridículamente, increíblemente, absolutamente más de lo que cualquier computadora que podamos imaginar ahora puede sostener. Estamos en algo así como 2 ^ 40. Comprueba que eres matemática de nuevo.
Stefan Reich
-1

El reequilibrio del árbol AVL debe cumplir con la siguiente propiedad. (Referencia Wiki - Árbol AVL )

En un árbol AVL, las alturas de los dos subárboles secundarios de cualquier nodo difieren como máximo en uno; si en algún momento difieren en más de uno, se realiza un reequilibrio para restaurar esta propiedad.

Esto implica que la altura total del árbol AVL no puede volverse loca, es decir, las búsquedas serán mejores con los árboles AVL. Y dado que se deben realizar operaciones adicionales (rotaciones) para no dejar que la altura se vuelva loca, las operaciones de modificación del árbol pueden ser un poco costosas.

samshers
fuente
Se mencionan muchos otros lugares, pero la razón por la que esta respuesta no es muy buena es que los árboles AVL y los árboles RB mantienen efectivamente restricciones extremadamente similares: los árboles RB no tendrán más de 2.0 veces la altura requerida, y para los árboles AVL ese factor es alrededor de 1,44. Como consecuencia, los árboles AVL giran un poco más a menudo, pero el costo por rotación es esencialmente el mismo; no es costoso.
Mumbleskates