Una clasificación de árbol es un algoritmo de clasificación que crea un árbol de búsqueda binario a partir de los elementos que se van a clasificar y luego atraviesa el árbol ( en orden ) para que los elementos salgan en orden. Su uso típico es ordenar elementos en línea : después de cada inserción, el conjunto de elementos vistos hasta ahora está disponible en orden ordenado.
Clase | Algoritmo de clasificación |
---|---|
Estructura de datos | Formación |
Rendimiento en el peor de los casos | O ( n ²) (desequilibrado) O ( n log n ) (equilibrado) |
Rendimiento en el mejor de los casos | O ( n log n ) [ cita requerida ] |
Rendimiento medio | O ( n log n ) |
Complejidad espacial en el peor de los casos | Θ ( n ) |
La ordenación de árbol se puede usar como una ordenación única, pero es equivalente a la ordenación rápida, ya que ambos particionan de forma recursiva los elementos en función de un pivote y, dado que la ordenación rápida está en el lugar y tiene una sobrecarga más baja, tiene pocas ventajas sobre la ordenación rápida. Tiene una mayor complejidad en el peor de los casos cuando se usa un árbol de autoequilibrio, pero aún más sobrecarga.
Eficiencia
Agregar un elemento a un árbol de búsqueda binaria es en promedio un proceso O (log n ) (en notación O grande ). Agregar n elementos es un proceso O ( n log n ) , lo que hace que la clasificación de árboles sea un proceso de 'clasificación rápida'. Agregar un elemento a un árbol binario desequilibrado requiere O ( n ) tiempo en el peor de los casos: cuando el árbol se parece a una lista vinculada ( árbol degenerado ). Esto da como resultado un caso más desfavorable de tiempo O ( n ²) para este algoritmo de clasificación. Este peor caso ocurre cuando el algoritmo opera en un conjunto ya ordenado, o uno que está casi ordenado, invertido o casi invertido. Esperado O ( n log n ) tiempo, sin embargo se puede conseguir por revolver la matriz, pero esto no ayuda para los artículos iguales.
El comportamiento en el peor de los casos se puede mejorar utilizando un árbol de búsqueda binario autoequilibrado . Al utilizar un árbol de este tipo, el algoritmo tiene un rendimiento en el peor de los casos O ( n log n ) , por lo que es un grado óptimo para una clasificación de comparación . Sin embargo, los algoritmos de ordenación de árboles requieren que se asigne una memoria separada para el árbol, a diferencia de los algoritmos in situ como la ordenación rápida o la ordenación en pila . En la mayoría de las plataformas, esto significa que se debe usar memoria dinámica , lo que representa un impacto significativo en el rendimiento en comparación con el ordenamiento rápido y el ordenamiento dinámico [ cita requerida ] . Cuando se utiliza un árbol biselado como el árbol de búsqueda binaria, el algoritmo resultante (llamada splaysort ) tiene la propiedad adicional de que es una especie de adaptación , lo que significa que su tiempo de ejecución es más rápida que O ( n log n ) para las entradas que están casi ordenados.
Ejemplo
El siguiente algoritmo de ordenación de árboles en pseudocódigo acepta una colección de elementos comparables y genera los elementos en orden ascendente:
ESTRUCTURA BinaryTree BinaryTree : LeftSubTree Objeto : Nodo BinaryTree : RightSubTree PROCEDIMIENTO Insertar ( BinaryTree : searchTree , Object : item ) SI searchTree . El nodo ES NULO ENTONCES SET searchTree . Nodo TO elemento ELSE SI el elemento ES MENOR QUE searchTree . Nodo THEN Insert ( searchTree . LeftSubTree , elemento ) ELSE Insert ( searchTree . RightSubTree , elemento ) PROCEDIMIENTO InOrder ( BinaryTree : searchTree ) SI searchTree . El nodo ES NULO LUEGO SALIR DEL PROCEDIMIENTO ELSE InOrder ( searchTree . LeftSubTree ) EMIT searchTree . Nodo InOrder ( searchTree . RightSubTree ) PROCEDIMIENTO TreeSort ( Colección : elementos ) BinaryTree : searchTree PARA CADA elemento individual EN elementos Insertar ( árbol de búsqueda , elemento individual ) InOrder ( árbol de búsqueda )
En una forma de programación funcional simple , el algoritmo (en Haskell ) se vería así:
árbol de datos a = Hoja | Nodo ( árbol a ) a ( árbol a ) insertar :: Ord a => a -> Árbol a -> Árbol a inserto x Hoja = Nodo Hoja x Hoja inserto x ( Nodo t y s ) | x <= y = Nodo ( inserte x t ) y s | x > y = Nodo t y ( inserte x s ) aplanar :: Árbol a -> [ a ] aplanar Hoja = [] aplanar ( Nodo t x s ) = aplanar t ++ [ x ] ++ aplanar s treesort :: Ord a => [ a ] -> [ a ] treesort = aplanar . foldr inserto Leaf
En la implementación anterior, tanto el algoritmo de inserción como el algoritmo de recuperación tienen O ( n ²) el peor de los casos.
enlaces externos
- Applet y explicación de Java del árbol binario en Wayback Machine (archivado el 29 de noviembre de 2016)
- Tipo de árbol de una lista vinculada
- Clasificación de árboles en C ++