Ordenamiento con árbol binario

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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.