Ordenamiento con árbol binario

El ordenamiento con árbol binario es un algoritmo de ordenamiento, el cual ordena sus elementos haciendo uso de un árbol binario de búsqueda. Se basa en ir construyendo poco a poco el árbol binario introduciendo cada uno de los elementos, los cuales quedarán ya ordenados. Después, se obtiene la lista de los elementos ordenados recorriendo el árbol en inorden.

Complejidad

Insertar elementos en un árbol binario de búsqueda tiene una complejidad O(log n). Entonces, agregar n elementos a un árbol cualquiera da como resultado una complejidad O(n log n). Además, recorrer los elementos del árbol en inorden tiene complejidad O(n).

Características

• Tiene un buen rendimiento.
• Es estable (no cambia el orden relativo de elementos iguales).
• No requiere espacio de almacenamiento extra.
• Puede ordenar listas tal cual las recibe.

Enlaces externos

• Wikilibros en inglés alberga distintas implementaciones del Ordenamiento con árbol binario.
• Distintas implementaciones del algoritmo en RosettaCode (inglés)