Ordenamiento con árbol binario
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2b/Binary_tree_sort%282%29.png/220px-Binary_tree_sort%282%29.png)
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[editar]
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[editar]
- 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[editar]
Wikilibros en inglés alberga distintas implementaciones del Ordenamiento con árbol binario.
- Distintas implementaciones del algoritmo en RosettaCode (inglés)