algorithm - real - arboles rojo negro ejercicios
Árboles rojo-negro (13)
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 Informática, todavía tengo que tomar una clase que realmente trate con algoritmos y datos. estructuras de una manera seria.
Revisé las fuentes típicas (Wikipedia, Google) y la mayoría de las descripciones de la utilidad y la implementación (en particular) de los árboles rojo-negro se han vuelto densas y difíciles de entender. Estoy seguro de que para alguien con los antecedentes necesarios, tiene mucho sentido, pero por el momento parece casi un idioma extranjero.
Entonces, ¿qué es lo que hace que los árboles binarios sean útiles en algunas de las tareas comunes que te encuentras realizando durante la programación? Más allá de eso, ¿qué árboles prefiere usar (incluya una implementación de muestra) y por qué?
BSTs hacen que el mundo gire, como dijo Micheal. Si está buscando un buen árbol para implementar, eche un vistazo a los árboles AVL (Wikipedia). Tienen una condición de equilibrio, por lo que se garantiza que sean 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 hashing, pero se ponen feas, rápidas y apresuradas. Además, te encuentras con la paradoja del cumpleaños (también conocido como el problema del casillero).
¿Qué libro de texto estás usando? Utilizamos 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-Negros, e incluso incluye el código necesario para implementar todos los árboles de los que habla.
IME, casi nadie entiende el algoritmo de árbol RB. La gente puede repetir las reglas, pero no entienden por qué esas reglas y de dónde vienen. No soy la excepción :-)
Por esta razón, prefiero el algoritmo AVL, porque es fácil de comprender . Una vez que lo comprenda, puede codificarlo desde cero, porque tiene sentido para usted.
La mejor descripción de los árboles rojo oscuro 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 parcialmente uno (solo inserción). También hay algunos applets como This One en varias páginas web que animan el proceso y le permiten ver y recorrer una representación gráfica del algoritmo que construye una estructura de árbol.
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 un elemento. Si tiene un millón de nodos en una lista vinculada, se necesitan 500,000 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 puede almacenar más memoria. Imagine un árbol donde la mayoría de los nodos tienen un hijo correcto, pero no un hijo izquierdo; es una lista, pero aún tiene que mantener el 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 es bastante claro. El artículo de Wikipedia sobre árboles rojo-negro es claro como el barro, honestamente.
Más allá de los árboles binarios, los B-Trees son árboles donde cada nodo puede tener muchos valores. B-Tree no es un árbol binario, simplemente resulta ser el nombre de él. 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, para que no vaya (lentamente) y encuentre toneladas de cosas diferentes en la memoria que se paginó en el disco. Aquí hay un ejemplo fenomenal del B-Tree .
Los árboles rojo-negros se mantienen equilibrados, por lo que no es necesario atravesar en profundidad para sacar los objetos. El tiempo ahorrado hace que los árboles RB O (log () n)) en el PEOR caso, mientras que los árboles binarios desafortunados puedan entrar en una configuración de lados lope y hacer que las recuperaciones en O (n) sean un mal caso. Esto sucede en la práctica o en datos aleatorios. Por lo tanto, si necesita un código de tiempo crítico (recuperación de bases de datos, servidor de red, etc.) utiliza árboles RB para admitir listas / conjuntos ordenados o no ordenados.
¡Pero los RBTrees son para noobs! Si está haciendo AI y necesita realizar una búsqueda, encontrará que bifurca mucho la información del estado. Puede usar un persistente rojo-negro para tejer nuevos estados en O (log (n)). Un árbol negro rojo persistente guarda una copia del árbol antes y después de una operación morfológica (insertar / eliminar), pero sin copiar todo el árbol (normalmente y la operación O (log (n))). He abierto un árbol persistente rojo-negro para Java
Los árboles rojos y negros son buenos para crear árboles bien equilibrados. El principal problema con los árboles de búsqueda binarios es que puedes desequilibrarlos muy fácilmente. Imagine que su primer número es un 15. Entonces, todos los números que siguen son cada vez más pequeños que 15. Tendrá un árbol que es muy pesado en el lado izquierdo y no tiene nada en el lado derecho.
Los árboles rojos negros lo resuelven obligando a que tu árbol esté equilibrado cada vez que lo insertes o elimines. Lo logra a través de una serie de rotaciones entre nodos antecesores y nodos secundarios. El algoritmo es bastante directo, aunque es un poco largo. Sugiero recoger 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 lo mejor para incluirla aquí. Sin embargo, los árboles se usan ampliamente para aplicaciones de alto rendimiento que necesitan acceso a una gran cantidad de datos. Proporcionan una forma muy eficiente de encontrar nodos, con una sobrecarga relativamente pequeña de inserción / eliminación. Una vez más, sugiero consultar CLRS para leer cómo se usan.
Mientras que BSTs no se pueden usar explícitamente, un ejemplo del uso de árboles en general se encuentra en casi todos los RDBMS modernos. De forma similar, su sistema de archivos se representa casi con certeza como un tipo de estructura de árbol, y los archivos también se indexan de esa manera. Los árboles alimentan a Google. Los árboles alimentan casi todos los sitios web en Internet.
Me gustaría abordar solo la pregunta "Entonces, ¿qué hace que los árboles binarios sean útiles en algunas de las tareas comunes que te encuentras realizando durante la programación?"
Este es un gran tema en el que muchas personas no están de acuerdo. Algunos dicen que los algoritmos que se enseñan en un grado CS, como los árboles binarios de búsqueda y los gráficos dirigidos, no se utilizan en la programación diaria y, por lo tanto, son irrelevantes. Otros están en desacuerdo, diciendo que estos algoritmos y estructuras de datos son la base de toda nuestra programación y es esencial comprenderlos, incluso si nunca tiene que escribir uno para usted. 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 cuestión. Recuerde este debate; personas con experiencia no están de acuerdo.
En la programación comercial típica, es posible que no necesite crear árboles binarios o incluso árboles muy a menudo. Sin embargo, usará muchas clases que operan internamente usando árboles. Muchas de las clases centrales de organización en todos los idiomas usan árboles y hash para almacenar y acceder a los datos.
Si está involucrado en más emprendimientos o situaciones de alto rendimiento que están algo fuera de la norma de la programación comercial, encontrará árboles para ser un amigo inmediato. Como dijo otro afiche, los árboles son estructuras de datos centrales para bases de datos e índices de todo tipo. Son útiles en la visualización y extracción de datos, gráficos avanzados (2d y 3d) y una serie de otros problemas de cómputo.
He usado árboles binarios en forma de árboles BSP (partición de espacio binario) en gráficos 3D. Actualmente estoy buscando árboles nuevamente para ordenar grandes cantidades de datos geocodificados y otros datos para la visualización de información en aplicaciones Flash / Flex. Siempre que esté presionando el límite del hardware o desee ejecutar las especificaciones de hardware más bajas, comprender y seleccionar el mejor algoritmo puede marcar la diferencia entre el fracaso y el éxito.
Montones y montones de 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, por ejemplo, una matriz, que no puede tomar una clave y devolver un valor asociado, bueno, a menos que sea una "clave" entera en un índice escaso 0% de enteros contiguos. Una matriz no puede crecer en tamaño tampoco (sí, también sé de realloc (), pero bajo las cubiertas que requiere una nueva matriz y luego una memcpy ()), por lo que si tiene alguno de estos requisitos, una matriz no funcionará . La eficiencia de la memoria de una matriz es perfecta. Cero desperdicio, pero no muy inteligente o flexible - no obstante, realloc ().
En segundo lugar , en contraste con un bsearch () en una matriz de elementos, que ES una estructura de datos asociativa, un árbol RB puede crecer (Y contraerse) en tamaño de forma dinámica. El bsearch () funciona bien para indexar una estructura de datos de un tamaño conocido, que permanecerá en ese tamaño. Por lo tanto, si no conoce el tamaño de sus datos por adelantado, o si necesita agregar o borrar elementos nuevos, un bsearch () está desactivado. 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 mi favorito 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, señalando el miembro struc {}, por ejemplo, que desea comparar, y luego reorganizando el puntero en la matriz de punteros de modo que leer los punteros en orden al final de la ordenación del puntero da sus datos en orden ordenado. Usar esto con archivos de datos mapeados en memoria es extremadamente eficiente en cuanto a la memoria, rápido y bastante fácil. Todo lo que necesita hacer es agregar algunos "*" a sus funciones de comparación.
En tercer lugar , 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ágicamente 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 un hashtable es O (1), ese 1 puede ser un cálculo hash muy caro. Los números enteros múltiples de 1 reloj de un árbol a menudo superan los cálculos de 100 horas + hash, para no decir nada del reajuste, y el espacio malloc () para colisiones hash y refueños. Finalmente, si desea acceder a ISAM, así como acceso a sus datos, se descarta un hash, ya que no hay ordenamiento de los datos inherentes a la tabla hash, en contraste con el ordenamiento natural de los datos en cualquier implementación de árbol. El uso clásico de una tabla hash es proporcionar acceso por clave a una tabla de palabras reservadas para un compilador. Su eficiencia de memoria es excelente.
En cuarto lugar , y muy bajo en cualquier lista, está la lista vinculada, o doblemente enlazada, que, a diferencia de una matriz, naturalmente soporta 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 solo sabe cómo llegar al siguiente elemento, por lo que debe buscar, en promedio, (element_knt / 2) enlaces para encontrar su datum. Se usa principalmente cuando 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 pueda aumentar de tamaño. Si se queda sin tamaño con una matriz, puede realloc () una matriz más grande. El STL hace esto para ti "debajo de las sábanas" cuando usas un vector. Crudo, pero potencialmente 1,000 veces más rápido si no necesita inserciones, eliminaciones o búsquedas codificadas. Su eficiencia de memoria es pobre, especialmente para listas doblemente vinculadas. De hecho, una lista doblemente enlazada, que requiere dos punteros, es exactamente igual a la memoria ineficiente que un árbol rojo-negro sin tener NINGUNA de sus características de recuperación ordenadas y rápidas.
En quinto lugar , los árboles admiten muchas operaciones adicionales en sus datos ordenados que cualquier otra estructura de datos. Por ejemplo, muchas consultas de bases de datos hacen uso del hecho de que un rango de valores de hoja se puede especificar fácilmente especificando su elemento primario común, y luego enfocando el procesamiento posterior en la parte del árbol que el padre "posee". El potencial de multithreading ofrecido por este enfoque debería ser obvio, ya que solo una pequeña región del árbol debe estar bloqueada, es decir, solo los nodos que posee el padre y el propio padre.
En resumen, los árboles son el Cadillac de las estructuras de datos. Usted paga un alto precio en términos de memoria utilizada, pero obtiene una estructura de datos totalmente autosuficiente. Es por eso que, como se señala en otras respuestas aquí, las bases de datos de transacciones usan árboles casi exclusivamente.
Ninguna de las respuestas menciona para qué son exactamente buenas las BST.
Si lo que desea hacer es solo buscar por valores, entonces una tabla hash es mucho más rápida, O (1) inserción y búsqueda (mejor caso amortizado).
Una BST será la búsqueda O (log N) donde N es la cantidad de nodos en el árbol, las inserciones también son O (log N).
Los árboles RB y AVL son importantes como otra respuesta mencionada debido a esta propiedad, si se crea una BST simple con valores en orden, entonces 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 los reequilibrios, mientras que los árboles RB son O (1). Un ejemplo del beneficio de esta complejidad constante es que, en caso de que mantenga una fuente de datos persistente, si necesita rastrear los cambios para deshacer, tendría que rastrear O (registrar N) los posibles cambios con un árbol AVL.
¿Por qué estaría dispuesto a pagar por el costo de un árbol en una tabla hash? ¡ORDEN! Las tablas Hash no tienen ningún orden, las BST, por otro lado, siempre se ordenan naturalmente en virtud de su estructura. Entonces, si se encuentra lanzando una gran cantidad de datos en una matriz u otro contenedor y luego ordenándola más tarde, una BST puede ser una mejor solución.
La propiedad de orden del árbol le proporciona una serie de capacidades de iteración ordenadas, en orden, primero en profundidad, ancho en primer lugar, preorden, después del pedido. Estos algoritmos de iteración son útiles en diferentes circunstancias si desea buscarlos.
Los árboles negros rojos se usan internamente en casi todos los contenedores ordenados de bibliotecas de idiomas, C ++ Set and Map, .NET SortedDictionary, Java TreeSet, etc ...
Entonces, los árboles son muy útiles, y puedes usarlos bastante a menudo sin siquiera saberlo. Probablemente nunca necesite escribir uno usted mismo, aunque lo recomendaría altamente como un ejercicio de programación interesante.
Red Black Trees y B-trees se usan en todo tipo de almacenamiento persistente; debido a que los árboles están equilibrados, se mitiga el rendimiento de los recorridos de amplitud y profundidad.
Casi todos los sistemas modernos de bases de datos usan árboles para el almacenamiento de datos.
Si desea ver cómo se supone que un árbol Rojo-Negro se vea gráficamente, he codificado una implementación de un árbol Rojo-Negro que puede descargar aquí
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
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 no es equivalente a un árbol binario (como se le preguntó en su pregunta).
Aquí hay un recurso excelente que describe la abstracción inicial conocida como el árbol binario binario simétrico que más tarde se convirtió en el árbol RB. Necesitarás una buena comprensión de los árboles B antes de que tenga sentido. En resumen: un enlace "rojo" en un árbol Rojo Negro es una forma de representar nodos que son parte de un nodo B-tree (valores dentro de un rango de clave), mientras que los enlaces "negros" son nodos que están conectados verticalmente en un B -árbol.
Entonces, esto es lo que obtienes cuando traduces las reglas de un árbol Red Black en términos de un B-tree (estoy usando el formato Red Black tree rule => B Tree equivalent ):
1) Un nodo es rojo o negro. => Un nodo en un b-tree 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 se puede considerar como parte de un nodo raíz interno 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.) => Como una forma de representar un árbol RB es omitiendo las hojas, podemos descartarlo.
4) Ambos niños 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 la misma cantidad de nodos negros. => Un árbol B se mantiene equilibrado ya que requiere que todos los nodos hoja estén a la misma profundidad (por lo tanto, la altura de un nodo B-Tree se representa por el número de enlaces negros desde la raíz hasta la hoja de un árbol Red Black )
Además, hay una implementación más simple ''no estándar'' por Robert Sedgewick aquí : (Él es el autor del libro Algoritmos junto con Wayne)