Clasificación de árboles

Un algoritmo de ordenación por árbol construye un árbol de búsqueda binaria a partir de los elementos que se van a ordenar y luego recorre el árbol ( en orden ) para que los elementos salgan ordenados. ^{[ 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.

El algoritmo de ordenación por árbol puede utilizarse como una ordenación única, pero es equivalente a Quicksort , ya que ambos particionan recursivamente los elementos en función de un pivote. Dado que Quicksort se ejecuta in situ y tiene menor sobrecarga, el algoritmo de ordenación por árbol presenta pocas ventajas sobre Quicksort. Si bien ofrece una mejor complejidad en el peor de los casos cuando se utiliza un árbol autoequilibrado, su sobrecarga es aún mayor.

Agregar un elemento a un árbol de búsqueda binaria es, en promedio, un proceso de O (log n ) (en notación Big O ). Agregar n elementos es un proceso de O ( n log n ) , lo que convierte la ordenación de árboles en un proceso de "ordenación rápida". Agregar un elemento a un árbol binario desequilibrado requiere un tiempo de O ( n ) en el peor de los casos: cuando el árbol se asemeja a una lista enlazada ( árbol degenerado ). Esto resulta en un peor caso de tiempo de O ( n² ) para este algoritmo de ordenación. Este peor caso ocurre cuando el algoritmo opera sobre un conjunto ya ordenado, o uno que está casi ordenado, invertido o casi invertido. Sin embargo, se puede lograr un tiempo esperado de O ( n log n ) reordenando el arreglo, pero esto no ayuda para elementos iguales.

El comportamiento en el peor de los casos se puede mejorar utilizando un árbol de búsqueda binaria autoequilibrado . Usando dicho árbol, el algoritmo tiene un rendimiento en el peor de los casos de O ( n log n ) , por lo que es óptimo en grado para una ordenación por comparación . Sin embargo, los algoritmos de ordenación de árboles requieren que se asigne memoria separada para el árbol, a diferencia de los algoritmos in situ como quicksort o heapsort . En la mayoría de las plataformas comunes, esto significa que se debe usar memoria de montón , lo que es una pérdida de rendimiento significativa en comparación con quicksort y heapsort . Cuando se usa un árbol 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 los devuelve en orden ascendente:

ESTRUCTURA BinaryTree BinaryTree : LeftSubTree Object : Node BinaryTree : RightSubTree PROCEDIMIENTO Insertar ( BinaryTree : searchTree , Object : item ) SI searchTree . Node ES NULO ENTONCES ESTABLECER searchTree . Node EN item SINO SI item ES MENOR QUE searchTree . Node ENTONCES Insertar ( searchTree . LeftSubTree , item ) SINO Insertar ( searchTree . RightSubTree , item ) PROCEDIMIENTO EnOrden ( BinaryTree : searchTree ) SI searchTree . Node ES NULO ENTONCES SALIR DEL PROCEDIMIENTO SINO EnOrden ( searchTree . LeftSubTree ) EMITIR searchTree . Nodo EnOrden ( searchTree . RightSubTree ) PROCEDIMIENTO OrdenarÁrbol ( Colección : items ) ÁrbolBinario : searchTree PARA CADA elementoIndividual EN items Insertar ( searchTree , elementoIndividual ) EnOrden ( searchTree )

En una forma de programación funcional simple , el algoritmo (en Haskell ) se vería algo 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 streesort :: 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 escenarios de peor caso O ( n ²) .

• Applet de Java sobre árbol binario y su explicación en Wayback Machine (archivado el 29 de noviembre de 2016)
• Ordenación en árbol de una lista enlazada en Wayback Machine (archivado el 10 de agosto de 2016)
• Ordenación de árboles en C++ en la Wayback Machine (archivado el 21 de enero de 2022)