Usando rojo negro árboles de clasificación

Question

El peor caso de tiempo de ejecución de la inserción en un red-black tree es O(lg n) y si puedo realizar una in-order walk en el árbol, esencialmente me visita cada nodo, por lo que el total de peor caso de tiempo de ejecución para la impresión de la colección ordenada sería O(n lg n)

Tengo curiosidad, ¿por qué red-black trees no preferido para la clasificación de más de quick sort (cuyo promedio de caso tiempo de ejecución es O(n lg n).

Veo que tal vez sea porque red-black trees no clasifica en el lugar, pero no estoy seguro, así que tal vez alguien pueda ayudar.

Answer 1

Saber que tipo de algoritmo se comporta mejor en realidad dependen de los datos y de la situación.

Si usted está hablando en general/términos prácticos,

Quicksort (donde se selecciona el pivote al azar/escoger una de ellas fija, haciendo el peor de los casos Omega(n^2)) podría ser mejor que el Rojo-Negro Árboles, porque (no necesariamente en orden de importancia)

• Quicksort es en el lugar.El mantiene su huella de memoria baja.Decir esto quicksort rutina era parte de un programa que se ocupa de una gran cantidad de datos.Si se mantiene el uso de grandes cantidades de memoria, el sistema operativo podría empezar a cambiar su proceso de la memoria y de la basura de su perf.

• Quicksort accesos a la memoria están localizados.Este juega bien con el almacenamiento en caché/intercambio.

• Quicksort puede ser fácilmente paralelizado (probablemente más relevante en estos días).

• Si usted fuera a tratar y optimizar el árbol binario de clasificación (utilizando árbol binario sin equilibrio) mediante una matriz en lugar de eso, usted va a terminar haciendo algo como Quicksort!

• Rojo-Negro árboles tienen la memoria de los gastos generales.Usted tiene que asignar los nodos posiblemente varias veces, sus requisitos de memoria con los árboles es de dobles/triples que el uso de matrices.

• Después de la clasificación, dicen que usted quiere que la 1045th (decir) elemento, será necesario mantener estadísticas de orden en su árbol (de memoria extra costo, debido a que de esta) y tenga O(logn) tiempo de acceso!

• Rojo-negro árboles gastos generales sólo para tener acceso al elemento siguiente (puntero de búsquedas)

• Rojo-negro árboles no jugar bien con el caché y el puntero de accesos podría inducir a más de intercambio.

• Rotación en rojo-negro árboles aumentará el factor constante en la O(nlogn).

• Quizás la razón más importante (pero no es válido si tiene lib etc disponible), Quicksort es muy sencillo de entender y de aplicar.Incluso un niño puede entender!

Yo diría que intenta medir tanto las implementaciones y a ver qué pasa!

También, Bob Sedgewick hizo una tesis sobre quicksort!Podría ser vale la pena leer.

Answer 2

Hay un montón de algoritmos de ordenación que son peor de los casos O(n log n) - por ejemplo, la combinación de ordenación.La razón quicksort es preferido es porque es más rápido en la práctica, aunque a través de algoritmos que pueden no ser tan buenos como otros algoritmos.

A menudo incorporada tipo de uso de una combinación de varios métodos, dependiendo de los valores de n.

Answer 3

Hay muchos casos donde el rojo-back de los árboles no son malos para la clasificación.Mis pruebas mostraron que, en comparación con los naturales de combinación de tipo, que rojo-negro árboles de excel donde:

Los árboles son mejores para los paquetes de actualización de dell: Todas las pruebas en las que el dup necesitan ser eleminated, algoritmo de árbol es mejor.Esto no es sorprendente, ya que el árbol puede ser mantenido muy pequeños desde el comienzo, por lo que los algoritmos que están diseñados para en línea de la matriz de ordenación podría pasar alrededor de grandes segmentos para un tiempo más largo.

Los árboles son mejores para Random: Todas las pruebas con el azar, el algoritmo de árbol es mejor.Eso no es sorprendente, ya que en un árbol de la distancia entre los elementos es más corto y el cambio no es necesario.Tan repetidamente la inserción en un árbol podría necesitan menos esfuerzo que la ordenación de una matriz.

Así, tenemos la impresión de que los naturales de combinación de ordenación sólo se destaca en forma ascendente y descendente casos especiales.Que no puede ser dicho para la ordenación rápida.

Gist con los casos de prueba aquí.

P. S.:cabe señalar que el uso de árboles de clasificación no es trivial.Uno no sólo tiene que proporcionar una inserción en una rutina, pero también una rutina que puede alinear el árbol de una matriz.Actualmente estamos utilizando un get_last y un predecesor de rutina, que no necesita de una pila.Pero estas rutinas no son O(1), ya que contienen bucles.

Answer 4

Big-O el tiempo de las medidas de la complejidad no suelen tener en cuenta a escalar factores, p. ej., O(2n) y O(4n) son por lo general reduce a O(n).Tiempo de análisis de la complejidad se basa en los pasos de funcionamiento en un nivel algorítmico, no en el estricto nivel de programación, es decir, no hay código fuente o nativo de instrucción de la máquina consideraciones.

Quicksort es generalmente más rápido que el árbol de clasificación basada dado que (1) los métodos tienen el mismo algorítmica tiempo promedio complejidad, y (2) la búsqueda y el intercambio de las operaciones requieren un menor número de programa de comandos y accesos de datos cuando se trabaja con matrices sencillas que con el rojo-negro árboles, incluso si el árbol se utiliza una matriz subyacente basado en la aplicación.Mantenimiento de el árbol rojo-negro restricciones requiere adicional a los pasos de funcionamiento, valor de campo de datos de almacenamiento/acceso (nodo color), etc que la simple matriz de partición de intercambio pasos de un quicksort.

El resultado neto es que el rojo-negro árboles más altos coeficientes escalares de quicksort hace que se produzcan por la norma O(n log n) tiempo medio de análisis de la complejidad resultado.

Algunas otras consideraciones prácticas relacionadas con arquitecturas de máquina se discuten brevemente en el Quicksort artículo en la Wikipedia

Answer 5

En general, las representaciones de O(nlgn) algoritmos puede ser ampliado a Un*nlgn + B donde a y B son constantes.Hay muchos algoritmos pruebas que muestran que los coeficientes de quicksort son más pequeños que los de otros algoritmos.Que es en el mejor de los casos (ordenación rápida realiza horriblemente en datos ordenados).

Answer 6

Hola la mejor manera de explicar la diferencia entre la totalidad de rutina de ordenación es, en mi opinión.(Mi respuesta es para las personas que están confundidos de lo rápido que tipo es más rápido en la práctica de otra clasificación de algo).

"Creo que la u se ejecutan en un ordenador muy lento".

1. Primero una comparación de la operación es de 1 hora.
2. Un desplazamiento de la operación dura 2 horas.

"Yo soy el uso de la hora sólo para hacer que la gente entienda lo importante que es".

Ahora de todas las operaciones de ordenación de ordenación rápida tienen muy menos comparaciones y mucho menos para el intercambio de elementos.

Quick-sort es más rápido por esta razón principal.