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
editarInsertar 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)
Datos: Q863521
