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 aparezcan 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.
La ordenación de árbol se puede usar como una ordenación de una sola vez, 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.
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 el peor de los casos de O ( n ²)tiempo 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. Sin embargo, el tiempo O ( n log n ) esperado se puede lograr barajando la matriz, pero esto no ayuda para elementos iguales.
El comportamiento en el peor de los casos se puede mejorar mediante el uso de un árbol de búsqueda binario autoequilibrado . Al usar 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 utilizar 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 usa un árbol de splay como árbol de búsqueda binaria, el algoritmo resultante (llamado splaysort ) tiene la propiedad adicional de que es una ordenación adaptativa , lo que significa que su tiempo de ejecución es más rápido que O ( n log n ) para entradas que están casi ordenadas.
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:
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.