Una ordenación de árbol es un algoritmo de ordenación que construye un árbol de búsqueda binario a partir de los elementos que se van a ordenar y luego recorre el árbol ( en orden ) para que los elementos salgan en orden ordenado. [1] Su uso típico es la ordenación de elementos en línea : después de cada inserción, el conjunto de elementos vistos hasta el momento está disponible en orden ordenado.
La ordenación en árbol se puede utilizar como una ordenación de una sola vez, pero es equivalente a la ordenación rápida , ya que ambas dividen recursivamente los elementos en función de un pivote y, dado que la ordenación rápida se realiza en el lugar y tiene menos sobrecarga, la ordenación en árbol tiene pocas ventajas sobre la ordenación rápida. Tiene una mejor complejidad en el peor de los casos cuando se utiliza un árbol autoequilibrado, pero incluso más sobrecarga.
Añadir un elemento a un árbol binario de búsqueda es en promedio un proceso O (log n ) (en notación O mayúscula ). Añadir n elementos es un proceso O ( n log n ) , lo que hace que la ordenación de árboles sea un proceso de "ordenación rápida". Añadir un elemento a un árbol binario desequilibrado requiere un tiempo O ( n ) en el peor de los casos: cuando el árbol se parece a una lista enlazada ( árbol degenerado ). Esto da como resultado un tiempo O ( n² ) en el peor de los casos para este algoritmo de ordenació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 mezclando la matriz, pero esto no ayuda para elementos iguales.
El comportamiento en el peor de los casos se puede mejorar utilizando un árbol binario de búsqueda autoequilibrado . Al utilizar un árbol de este tipo, el algoritmo tiene un rendimiento en el peor de los casos de O ( n log n ) , por lo que es óptimo en cuanto a grados para una ordenación por comparación . Sin embargo, los algoritmos de ordenación en árbol requieren que se asigne memoria separada para el árbol, a diferencia de los algoritmos in situ como quicksort o heapsort . En las plataformas más comunes, esto significa que se debe utilizar memoria de montón , lo que supone un importante impacto en el rendimiento en comparación con quicksort y heapsort [ cita requerida ] . Cuando se utiliza un árbol splay como árbol binario de búsqueda, 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 ordenamiento 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 , Objeto : item ) SI searchTree . Nodo ES NULO ENTONCES ESTABLECER searchTree . Nodo A item DE LO CONTRARIO SI item ES MENOR QUE searchTree . Nodo ENTONCES Insertar ( searchTree . LeftSubTree , item ) DE LO CONTRARIO Insertar ( searchTree . RightSubTree , item ) PROCEDIMIENTO InOrder ( BinaryTree : searchTree ) SI searchTree . Nodo ES NULO ENTONCES SALIR PROCEDIMIENTO DE LO CONTRARIO InOrder ( searchTree . LeftSubTree ) EMITir searchTree . Nodo InOrder ( searchTree.RightSubTree ) PROCEDIMIENTO TreeSort ( Collection : items ) BinaryTree : searchTree PARA CADA elemento individual EN elementos Insertar ( searchTree , elemento individual ) InOrder ( searchTree ) En una forma de programación funcional simple , el algoritmo (en Haskell ) se vería así:
datos Árbol a = Hoja | Nodo ( Árbol a ) a ( Árbol a ) insertar :: Ord a => a -> Árbol a -> Árbol a insertar x Hoja = Nodo Hoja x Hoja insertar x ( Nodo t y s ) | x <= y = Nodo ( insertar x t ) y s | x > y = Nodo t y ( insertar 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 . hoja de inserción plegable En la implementación anterior, tanto el algoritmo de inserción como el algoritmo de recuperación tienen O ( n² ) escenarios de peor caso.
