Árboles Rojo-Negro

Me gustaría abordar solo la pregunta " Entonces, ¿qué hace que los árboles binarios sean útiles en algunas de las tareas comunes que se encuentran haciendo mientras programan?"

Este es un gran tema en el que muchas personas no están de acuerdo. Algunos dicen que los algoritmos enseñados en un grado CS, como los árboles de búsqueda binarios 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, diciendo que estos algoritmos y estructuras de datos son la base para toda nuestra programación y es esencial entenderlos, incluso si nunca tienes que escribir uno para ti mismo. Esto se filtra en las conversaciones sobre buenas prácticas de entrevista y contratación. Por ejemplo, Steve Yegge tiene un artículo sobre entrevistas en Google que aborda esta pregunta. Recuerde este debate; la gente experimentada no está de acuerdo.

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

Si está involucrado en esfuerzos o situaciones de alto rendimiento que están algo fuera de la norma de la programación empresarial, encontrará que trees es un amigo inmediato. Como dijo otro póster, los árboles son estructuras de datos básicos para bases de datos e índices de todo tipo. Son útiles en la minería y visualización de datos, gráficos avanzados (2d y 3d) y un host de otros problemas computacionales.

He utilizado árboles binarios en forma de BSP (binary space partitioning) árboles en gráficos 3d. Actualmente estoy buscando árboles de nuevo para ordenar grandes cantidades de datos geocodificados y otros datos para la visualización de información en aplicaciones Flash/Flex. Siempre que esté empujando el límite del hardware o desee ejecutar especificaciones de hardware más bajas, comprender y seleccionar el mejor algoritmo puede marcar la diferencia entre el fallo y éxito.

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

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

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

Los árboles RB y AVL son importantes como otra respuesta mencionada debido a esta propiedad, si se crea un BST plano con valores en orden, el árbol será tan alto como el número de valores insertados, esto es malo para el rendimiento de búsqueda.

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

Por qué ¿estaría dispuesto a pagar por el costo de un árbol sobre una tabla de hash? ORDEN! Las tablas Hash no tienen orden, por otro lado, las BST siempre están ordenadas naturalmente en virtud de su estructura. Así que si te encuentras lanzando un montón de datos en una matriz u otro contenedor y luego ordenarlo más tarde, un BST puede ser una mejor solución.

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

Los árboles negros rojos se usan internamente en casi todos los contenedores ordenados de bibliotecas de lenguaje, Conjuntos y Mapas de C++,. NET SortedDictionary, conjuntos de árboles de Java, etc...

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

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

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

Los BST hacen que el mundo gire, como dijo Micheal. Si está buscando un buen árbol para implementar, eche un vistazo a AVL trees (Wikipedia). Tienen una condición de equilibrio, por lo que están garantizados para ser O(logn). Este tipo de eficiencia de búsqueda hace que sea lógico poner en cualquier tipo de proceso de indexación. Lo único que sería más eficiente sería una función de hash, pero esos se ponen feos rápido, rápido, y en un apuro. Además, te encuentras con la Paradoja de Cumpleaños (también conocido como el problema del palomar).

¿Qué libro de texto estás usando? Utilizamos Estructuras de datos y Análisis en Java por Mark Allen Weiss. En realidad 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.

Los árboles rojo-negro se mantienen equilibrados, por lo que no tienes que atravesar profundidad para sacar objetos. El tiempo ahorrado hace que los árboles RB O (log () n)) en el PEOR de los casos, mientras que los árboles binarios desafortunados pueden entrar en una configuración lop sided y causar recuperaciones en O (n) un mal caso. Esto sucede en la práctica o en datos aleatorios. Entonces, si necesita un código crítico de tiempo (recuperación de bases de datos, servidor de red, etc.) se utilizan árboles RB para soportar listas/conjuntos ordenados o desordenados .

Pero RBTrees son para noobs! Si usted es haciendo IA y necesita realizar una búsqueda, encuentra que bifurca la información del estado mucho. Puede usar un rojo-negro persistente para bifurcar nuevos estados en O (log (n)). Un árbol rojo negro persistente mantiene una copia del árbol antes y después de una operación morfológica (insertar / eliminar), pero sin copiar todo el árbol (normalmente y O(log(n)) operación). He abierto un persistente árbol rojo-negro para java

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

La mejor descripción de los árboles rojo-negro que he visto es la de la Introducción a los Algoritmos de Cormen, Leisersen y Rivest. Incluso pude entenderlo lo suficiente como para implementar parcialmente uno (solo inserción). También hay bastantes applets como Este en varias páginas web que animan el proceso y le permiten ver y pasar por una representación gráfica del algoritmo que construye una estructura de árbol.

Ya que preguntas qué árbol usan las personas, 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 preguntó en su pregunta).

Aquí es un excelente recurso que describe la abstracción inicial conocida como el árbol B binario simétrico que más tarde evolucionó en el RBTree. Necesitarías una buena comprensión de los árboles B antes de que tenga sentido. Para resumir: un enlace 'rojo' en un árbol Rojo Negro es un forma de representar nodos que son parte de un nodo de árbol B (valores dentro de un rango de claves), mientras que los enlaces '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 Negro => Equivalente de árbol B):

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 negro. (Esta regla a veces se omite, ya que no afecta el análisis) => El nodo raíz puede ser considerado como una parte de un nodo raíz interno como un 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 ruta simple desde un nodo dado a cualquiera de sus hojas descendientes contiene el mismo número de nodos negros. = > Un árbol B se mantiene equilibrado, ya que requiere que todos los nodos de la hoja 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 negro rojo)

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

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 de enteros contiguos al 0%. Un array tampoco puede crecer en tamaño (sí, también sé sobre realloc (), pero bajo las cubiertas que requiere un nuevo array y luego un memcpy ()), así que si tienes cualquiera de estos requisitos, una matriz no servirá. La eficiencia de memoria de una matriz es perfecta. Cero residuos, pero no muy inteligente, o flexible-realloc () no soporta.

Segundo, en contraste con una bsearch() en una matriz de elementos, que ES una estructura de datos asociativa, un árbol RB puede crecer (Y encogerse) 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. Así que si usted no sabe el tamaño de sus datos de antemano, o nuevo los elementos necesitan ser añadidos, o eliminados, una bsearch () está fuera. Bsearch () y qsort () están bien soportados en classic C, y tienen una 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 estás tratando con 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 struc {}, por ejemplo, que desea comparar, y luego reorganizar el puntero en la matriz de punteros de tal manera que la lectura de los punteros en orden al final de la ordenación del puntero produce sus datos en orden ordenado. Usar esto con archivos de datos mapeados en memoria es extremadamente eficiente, rápido y bastante fácil. Todo lo que necesita hacer es agregar algunas " * " s a su función/s de comparación.

Tercero, en contraste con una tabla hash, que también debe ser de un tamaño fijo, y no se puede cultivar una vez rellenado, un árbol RB crecerá automáticamente y se equilibrará a 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 a pesar de que la complejidad de una hashtable 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 100 reloj+, por no hablar de rehashing, y malloc () ing espacio para colisiones de hash y rehashes. Por último, si desea el acceso ISAM, así como el acceso clave a sus datos, se descarta un hash, ya que no hay un 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 con clave a una tabla de palabras reservadas para un compilador. Su eficiencia de memoria es excelente.

La cuarta, y muy baja en cualquier lista, es la lista enlazada, o doblemente enlazada, que, en contraste con una matriz, naturalmente soporta inserciones y eliminaciones de elementos, y como eso implica, redimensionar. Es el más lento de todas las estructuras de datos, ya que cada elemento solo sabe cómo llegar al siguiente elemento, por lo que debe buscar, en promedio, enlaces (element_knt/2) para encontrar su datum. Se utiliza principalmente donde las inserciones y eliminaciones en algún lugar en el medio de la lista son comunes, y especialmente, donde 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 usar una matriz arbitrariamente grande en lugar de una lista vinculada si su único requisito es que puede aumentar de tamaño. Si te quedas sin tamaño con un array, puedes realloc() un array más grande. El STL hace esto por usted "bajo las cubiertas" cuando se utiliza un vector. Crudo, pero potencialmente 1,000 s de veces más rápido si no necesita inserciones, eliminaciones o búsquedas con llave. Su eficiencia de memoria es pobre, especialmente para listas doblemente vinculadas. De hecho, una lista doblemente vinculada, que requiere dos punteros, es exactamente tan ineficiente como un árbol rojo-negro sin tener ninguno de sus atractivos rápidos, características de recuperación ordenada.

Quinto , los árboles soportan muchas operaciones adicionales en sus datos ordenados que cualquier otra estructura de datos. Por ejemplo, muchas consultas de base de datos hacen uso del hecho de que un rango de valores de hoja se puede especificar fácilmente especificando su padre común, y luego enfocando el procesamiento posterior en la parte del árbol que el padre "posee". El potencial de multi-threading que ofrece este enfoque debe ser obvio, ya que solo una pequeña región del árbol necesita estar bloqueado, es decir, solo los nodos que posee el padre y el padre mismo.

En resumen, los árboles son el Cadillac de las estructuras de datos. Usted paga un alto precio en términos de memoria utilizada, pero se obtiene una estructura de datos completamente auto-mantenimiento. Esta es la razón por la que, como se señaló en otras respuestas aquí, las bases de datos de transacciones utilizan árboles casi exclusivamente.

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

IME, casi nadie entiende el algoritmo del árbol RB. La gente puede repetirte las reglas, pero no entienden por qué esas reglas y de dónde vienen. No soy una excepción: -)

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

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 quinientos miles de comparaciones en promedio para encontrar el mismo elemento.

Si el árbol está desequilibrado, sin embargo, puede ser tan lento como una lista, y también tomar más memoria para almacenar. Imagine un árbol donde la mayoría de los nodos tienen un hijo derecho, pero no un hijo izquierdo; es una lista, pero usted todavía tiene que mantener espacio de memoria para poner 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 sobre él es bastante claro. El artículo de Wikipedia sobre los árboles rojo-negro es claro como el barro, honestamente.

Más allá de los árboles binarios, los árboles B son árboles donde cada nodo puede tener muchos valores. B-Tree es no un árbol binario, simplemente pasa a ser el nombre de la misma. Son realmente útiles para utilizar la memoria eficientemente; cada nodo del árbol se puede dimensionar para que quepa en un bloque de memoria, de modo que no estés (lentamente) yendo y encontrando toneladas de cosas diferentes en la memoria que se paginaron en el disco. He aquí un ejemplo fenomenal del Árbol B .

Si quieres echar un vistazo a mi implementación de Red Black Tree. http://code.google.com/p/cstl/source/browse/src/c_rb.c