Árboles rojo-negros

Question

He visto árboles binarios y búsqueda binaria mencionados en varios libros que he leído últimamente, pero como todavía estoy al comienzo de mis estudios en Ciencias de la Computación, todavía tengo que tomar una clase que realmente trate sobre algoritmos y datos. estructuras de manera seria.

Revisé las fuentes típicas (Wikipedia, Google) y la mayoría de las descripciones de la utilidad y la implementación de (en particular) los árboles Rojo-Negro resultaron densas y difíciles de entender.Estoy seguro de que para alguien con la formación necesaria tiene mucho sentido, pero por el momento se lee casi como un idioma extranjero.

Entonces, ¿qué hace que los árboles binarios sean útiles en algunas de las tareas comunes que realiza mientras programa?Más allá de eso, ¿qué árboles prefiere usar (incluya una implementación de muestra) y por qué?

Answer 1

Los árboles Rojo Negro son buenos para crear árboles bien equilibrados.El principal problema con los árboles de búsqueda binarios es que se pueden desequilibrar muy fácilmente.Imagina que tu primer número es un 15.Entonces todos los números posteriores son cada vez más pequeños que 15.Tendrás un árbol que es muy pesado en el lado izquierdo y no tiene nada en el lado derecho.

Los árboles Rojo Negro resuelven esto obligando a que su árbol esté equilibrado cada vez que lo inserta o lo elimina.Lo logra mediante una serie de rotaciones entre nodos ancestros y nodos secundarios.En realidad, el algoritmo es bastante sencillo, aunque un poco largo.Sugeriría tomar el libro de texto CLRS (Cormen, Lieserson, Rivest y Stein), "Introducción a los algoritmos" y leer sobre RB Trees.

La implementación tampoco es tan corta, por lo que probablemente no sea mejor incluirla aquí.Sin embargo, se utilizan árboles. extensamente para aplicaciones de alto rendimiento que necesitan acceso a una gran cantidad de datos.Proporcionan una manera muy eficiente de encontrar nodos, con una sobrecarga relativamente pequeña de inserción/eliminación.Nuevamente, sugeriría consultar CLRS para leer sobre cómo se usan.

Si bien los BST no se pueden usar explícitamente, un ejemplo del uso de árboles en general se encuentra en casi todos los RDBMS modernos.De manera similar, es casi seguro que su sistema de archivos esté representado como una especie de estructura de árbol, y los archivos también se indexan de esa manera.Los árboles impulsan a Google.Los árboles impulsan casi todos los sitios web de Internet.

Answer 2

Me gustaría abordar únicamente la pregunta "¿Qué hace que los árboles binarios sean útiles en algunas de las tareas comunes que realiza mientras programa?"

Este es un tema importante en el que muchas personas no están de acuerdo.Algunos dicen que los algoritmos que se enseñan en una carrera de informática, como los árboles de búsqueda binaria y los gráficos dirigidos, no se utilizan en la programación diaria y, por lo tanto, son irrelevantes.Otros no están de acuerdo y dicen que estos algoritmos y estructuras de datos son la base de toda nuestra programación y que es esencial comprenderlos, incluso si nunca tienes que escribir uno por ti mismo.Esto se filtra en conversaciones sobre buenas prácticas de entrevistas y contratación.Por ejemplo, Steve Yege tiene un artículo sobre entrevista en google que aborda esta cuestión.Recuerde este debate;las personas experimentadas no están de acuerdo.

En la programación empresarial típica, es posible que no necesite crear árboles binarios o incluso árboles con mucha frecuencia.Sin embargo, utilizará muchas clases que operan internamente utilizando árboles.Muchas de las clases de organización principales en todos los idiomas utilizan árboles y hashes para almacenar y acceder a datos.

Si está involucrado en proyectos de alto rendimiento o en situaciones que están algo fuera de la norma de la programación empresarial, encontrará que los árboles serán sus amigos inmediatos.Como decía otro cartel, los árboles son estructuras de datos centrales para bases de datos e índices de todo tipo.Son útiles en extracción y visualización de datos, gráficos avanzados (2D y 3D) y una serie de otros problemas computacionales.

He usado árboles binarios en forma de Árboles BSP (partición de espacio binario) en gráficos 3D.Actualmente estoy mirando árboles nuevamente para ordenar grandes cantidades de datos geocodificados y otros datos para visualización de información en aplicaciones Flash/Flex.Siempre que esté superando los límites del hardware o desee ejecutar con especificaciones de hardware más bajas, comprender y seleccionar el mejor algoritmo puede marcar la diferencia entre el fracaso y el éxito.

Answer 3

Ninguna de las respuestas menciona para qué sirven exactamente los BST.

Si lo que quiere hacer es simplemente buscar por valores, entonces una tabla hash es mucho más rápida, insertar O(1) y buscar (mejor caso amortizado).

Una BST será una búsqueda O (log N), donde N es el número de nodos en el árbol, las inserciones también son O (log N).

Los árboles RB y AVL son importantes, como se mencionó en otra respuesta, debido a esta propiedad. Si se crea un BST simple con valores en orden, el árbol será tan alto como el número de valores insertados, lo que es malo para el rendimiento de la búsqueda.

La diferencia entre los árboles RB y AVL está en las rotaciones necesarias para reequilibrar después de una inserción o eliminación, los árboles AVL son O (log N) para reequilibrios mientras que los árboles RB son O (1).Un ejemplo del beneficio de esta complejidad constante es en el caso en el que podría mantener una fuente de datos persistente, si necesita realizar un seguimiento de los cambios para revertir, tendría que realizar un seguimiento de O (log N) posibles cambios con un árbol AVL.

¿Por qué estaría dispuesto a pagar el costo de un árbol en lugar de una tabla hash?¡ORDEN!Las tablas hash no tienen orden; las BST, por otro lado, siempre están ordenadas de forma natural en virtud de su estructura.Entonces, si se encuentra arrojando una gran cantidad de datos en una matriz u otro contenedor y luego clasificándolos más tarde, un BST puede ser una mejor solución.

La propiedad de orden del árbol le brinda una serie de capacidades de iteración ordenada, en orden, primero en profundidad, primero en amplitud, pre-orden, post-orden.Estos algoritmos de iteración son útiles en diferentes circunstancias si desea buscarlos.

Los árboles rojos y negros se utilizan internamente en casi todos los contenedores ordenados de bibliotecas de lenguajes, C++ Set and Map, .NET SortedDictionary, Java TreeSet, etc.

Así que los árboles son muy útiles y puedes usarlos con bastante frecuencia sin siquiera saberlo.Lo más probable es que nunca lo hagas necesidad escribir uno usted mismo, aunque lo recomendaría ampliamente como un interesante ejercicio de programación.

Answer 4

Los árboles Red Black y los árboles B se utilizan en todo tipo de almacenamiento persistente;debido a que los árboles están equilibrados, se mitiga el rendimiento de los recorridos en anchura y profundidad.

Casi todos los sistemas de bases de datos modernos utilizan árboles para el almacenamiento de datos.

Answer 5

Las BST hacen girar el mundo, como dice Micheal.Si estás buscando un buen árbol para implementar, echa un vistazo a árboles AVL (Wikipedia).Tienen una condición de equilibrio, por lo que se garantiza que serán O (logn).Este tipo de eficiencia de búsqueda hace que sea lógico incluirlo en cualquier tipo de proceso de indexación.Lo único que sería más eficiente sería una función hash, pero se vuelven feas rápidamente y con prisa.Además, te topas con el Paradoja del cumpleaños (también conocido como el problema del casillero).

¿Qué libro de texto estás usando?Nosotros usamos Estructuras de datos y análisis en Java por Mark Allen Weiss.De hecho, lo tengo abierto en mi regazo mientras escribo esto.Tiene una gran sección sobre árboles Rojo-Negro, e incluso incluye el código necesario para implementar todos los árboles de los que habla.

Answer 6

Los árboles rojo-negros se mantienen equilibrados, por lo que no es necesario avanzar profundamente para sacar los elementos.El tiempo ahorrado hace que los árboles RB sean O(log()n)) en el PEOR caso, mientras que los árboles binarios desafortunados pueden entrar en una configuración desequilibrada y provocar recuperaciones en O(n) en un mal caso.Esto sucede en la práctica o con datos aleatorios.Entonces, si necesita código en el que el tiempo es crítico (recuperaciones de bases de datos, servidores de red, etc.), utilice árboles RB para admitir listas/conjuntos ordenados o desordenados.

¡Pero los RBTrees son para novatos!Si está utilizando IA y necesita realizar una búsqueda, descubrirá que bifurca mucho la información del estado.Puede utilizar un rojo-negro persistente para bifurcar nuevos estados en O(log(n)).Un árbol negro rojo persistente mantiene una copia del árbol antes y después de una operación morfológica (insertar/eliminar), pero sin copiar el árbol completo (normalmente y operación O(log(n))).He abierto un árbol rojo-negro persistente para Java.

http://edinburghhacklab.com/2011/07/a-java-implementation-of-persistent-red-black-trees-open-sourced/

Answer 7

La mejor descripción de árboles rojo-negros que he visto es la de 'Introducción a los algoritmos' de Cormen, Leisersen y Rivest.Incluso podría entenderlo lo suficiente como para implementar uno parcialmente (solo inserción).También hay bastantes subprogramas como Éste en varias páginas web que animan el proceso y le permiten observar y recorrer una representación gráfica del algoritmo construyendo una estructura de árbol.

Answer 8

Ya que preguntas qué árbol usa la gente, necesitas saber que un árbol Rojo Negro es fundamentalmente un árbol B 2-3-4 (es decir, un árbol B de orden 4).Un árbol B es no equivalente a un árbol binario (como se pregunta en su pregunta).

AquíEs un excelente recurso que describe la abstracción inicial conocida como árbol B binario simétrico que luego evolucionó hasta convertirse en RBTree.Necesitaría tener un buen conocimiento de los árboles B antes de que tenga sentido.Para resumir:un vínculo 'rojo' en un árbol Rojo Negro es una forma de representar nodos que son parte de un nodo de árbol B (valores dentro de un rango clave), mientras que los vínculos 'negros' son nodos que están conectados verticalmente en un árbol B.

Entonces, esto es lo que obtienes cuando traduces las reglas de un árbol Rojo Negro en términos de un árbol B (estoy usando el formato Regla del árbol rojo y negro => B Árbol equivalente):

1) Un nodo es rojo o negro.=> Un nodo en un árbol b puede ser parte de un nodo o como un nodo en un nuevo nivel.

2) La raíz es negra.(Esta regla a veces se omite, ya que no afecta el análisis) => El nodo raíz puede considerarse como parte de un nodo raíz interno o como hijo de un nodo padre imaginario.

3) Todas las hojas (NIL) son negras.(Todas las hojas son del mismo color que la raíz). => Dado que una forma de representar un árbol RB es omitiendo las hojas, podemos descartar esto.

4) Ambos hijos de cada nodo rojo son negros.=> Los hijos de un nodo interno en un árbol B siempre se encuentran en otro nivel.

5) Cada camino simple desde un nodo determinado hasta cualquiera de sus hojas descendientes contiene la misma cantidad de nodos negros.=> Un árbol B se mantiene equilibrado ya que requiere que todos los nodos de las hojas estén a la misma profundidad (por lo tanto, la altura de un nodo del árbol B está representada por el número de enlaces negros desde la raíz hasta la hoja de un árbol Rojo Negro )

Además, hay una implementación "no estándar" más simple realizada por Robert Sedgewick. aquí:(Él es el autor del libro Algoritmos junto con Wayne)

Answer 9

Mucho calor aquí, pero no mucha luz, así que veamos si podemos proporcionar algo.

Primero, un árbol RB es una estructura de datos asociativa, a diferencia de, digamos, una matriz, que no puede tomar una clave y devolver un valor asociado, bueno, a menos que sea una "clave" entera en un índice disperso del 0% de enteros contiguos.Una matriz tampoco puede crecer en tamaño (sí, también conozco realloc(), pero bajo las sábanas eso requiere una nueva matriz y luego un memcpy()), por lo que si tiene alguno de estos requisitos, una matriz no servirá .La eficiencia de la memoria de una matriz es perfecta.Cero desperdicio, pero no muy inteligente ni flexible, a pesar de realloc().

Segundo, a diferencia de bsearch() en una matriz de elementos, que ES una estructura de datos asociativa, un árbol RB puede crecer (Y reducirse) en tamaño dinámicamente.bsearch() funciona bien para indexar una estructura de datos de un tamaño conocido, que seguirá siendo ese tamaño.Entonces, si no conoce el tamaño de sus datos de antemano, o es necesario agregar o eliminar nuevos elementos, bsearch() está descartado.Bsearch() y qsort() están bien soportados en C clásico y tienen buena eficiencia de memoria, pero no son lo suficientemente dinámicos para muchas aplicaciones.Sin embargo, son mis favoritos porque son rápidos, fáciles y, si no se trata de aplicaciones en tiempo real, a menudo son lo suficientemente flexibles.Además, en C/C++ puede ordenar una matriz de punteros a registros de datos, apuntando al miembro struct{}, por ejemplo, que desea comparar, y luego reorganizar el puntero en la matriz de punteros de modo que se puedan leer los punteros en orden. al final del puntero, ordenar muestra sus datos en orden ordenado.Usar esto con archivos de datos asignados en memoria es extremadamente eficiente en términos de memoria, rápido y bastante fácil.Todo lo que necesita hacer es agregar algunos "*" a sus funciones de comparación.

Tercero, a diferencia de una tabla hash, que también debe tener un tamaño fijo y no puede crecer una vez llena, un árbol RB crecerá automáticamente y se equilibrará para mantener su garantía de rendimiento O(log(n)).Especialmente si la clave del árbol RB es un int, puede ser más rápido que un hash, porque aunque la complejidad de una tabla hash es O(1), ese 1 puede ser un cálculo hash muy costoso.Las comparaciones de enteros múltiples de 1 reloj de un árbol a menudo superan los cálculos de hash de más de 100 relojes, por no hablar del refrito y la asignación de espacio para colisiones de hash y refritos.Finalmente, si desea acceso ISAM, así como acceso clave a sus datos, se descarta un hash, ya que no hay ningún orden de los datos inherente en la tabla hash, en contraste con el orden natural de los datos en cualquier implementación de árbol.El uso clásico de una tabla hash es proporcionar acceso mediante clave a una tabla de palabras reservadas para un compilador.Su eficiencia de memoria es excelente.

Cuatro, y muy abajo en cualquier lista, está la lista enlazada o doblemente enlazada, que, a diferencia de una matriz, naturalmente admite inserciones y eliminaciones de elementos y, como eso implica, cambiar el tamaño.Es la más lenta de todas las estructuras de datos, ya que cada elemento sólo sabe cómo llegar al siguiente elemento, por lo que tienes que buscar, en promedio, (element_knt/2) enlaces para encontrar tu dato.Se utiliza principalmente cuando las inserciones y eliminaciones en algún lugar en el medio de la lista son comunes y, especialmente, cuando la lista es circular y alimenta un proceso costoso que hace que el tiempo para leer los enlaces sea relativamente pequeño.Mi RX general es utilizar una matriz arbitrariamente grande en lugar de una lista vinculada si su único requisito es que pueda aumentar de tamaño.Si se le acaba el tamaño de una matriz, puede reasignar() una matriz más grande.El STL hace esto por usted "bajo las sábanas" cuando usa un vector.Crudo, pero potencialmente miles de veces más rápido si no necesita inserciones, eliminaciones o búsquedas con clave.Su eficiencia de memoria es pobre, especialmente para listas doblemente enlazadas.De hecho, una lista doblemente enlazada, que requiere dos punteros, es exactamente tan ineficiente en memoria como un árbol rojo-negro y no tiene NINGUNA de sus atractivas características de recuperación rápida y ordenada.

Quinto, los árboles admiten muchas operaciones adicionales sobre sus datos ordenados que cualquier otra estructura de datos.Por ejemplo, muchas consultas de bases de datos aprovechan el hecho de que se puede especificar fácilmente un rango de valores de hoja especificando su padre común y luego centrando el procesamiento posterior en la parte del árbol que ese padre "posee".El potencial de subprocesos múltiples que ofrece este enfoque debería ser obvio, ya que sólo es necesario bloquear una pequeña región del árbol, es decir, sólo los nodos que posee el padre y el padre mismo.

En resumen, los árboles son el Cadillac de las estructuras de datos.Paga un alto precio en términos de memoria utilizada, pero obtiene una estructura de datos completamente automantenible.Es por eso que, como se señaló en otras respuestas aquí, las bases de datos de transacciones utilizan árboles casi exclusivamente.

Answer 10

Si desea ver gráficamente cómo se supone que debe verse un árbol Rojo-Negro, he codificado una implementación de un árbol Rojo-Negro que puede descarga aquí

Answer 11

IME, casi nadie comprende el algoritmo del árbol RB.Las personas pueden repetirte las reglas, pero no las entienden. por qué esas reglas y de dónde vienen.Yo no soy una excepción :-)

Por esta razón, prefiero el algoritmo AVL, porque es fácil de comprender.Una vez que lo entiendas, podrás codificarlo desde cero, porque tiene sentido para ti.

Answer 12

Los árboles pueden ser rápidos.Si tiene un millón de nodos en un árbol binario equilibrado, se necesitan veinte comparaciones en promedio para encontrar cualquier elemento.Si tiene un millón de nodos en una lista vinculada, se necesitan quinientas mil comparaciones en promedio para encontrar el mismo elemento.

Sin embargo, si el árbol está desequilibrado, puede ser tan lento como una lista, y También requiere más memoria para almacenar.Imagine un árbol donde la mayoría de los nodos tienen un hijo derecho, pero ningún hijo izquierdo;él es una lista, pero aún debe tener espacio en la memoria para colocarlo en el nodo izquierdo si aparece uno.

De todos modos, el árbol AVL fue el primer algoritmo de árbol binario equilibrado y el artículo de Wikipedia al respecto es bastante claro.Honestamente, el artículo de Wikipedia sobre árboles rojo-negros es claro como el barro.

Más allá de los árboles binarios, los B-Trees son árboles donde cada nodo puede tener muchos valores.El árbol B es no un árbol binario, resulta que es su nombre.Son realmente útiles para utilizar la memoria de manera eficiente;cada nodo del árbol se puede dimensionar para que quepa en un bloque de memoria, de modo que no esté (lentamente) buscando toneladas de cosas diferentes en la memoria que se paginaron en el disco.He aquí un ejemplo fenomenal de la Árbol B.