Ir al contenido

Ordenamiento con árbol binario

De Wikipedia, la enciclopedia libre
Esta es una versión antigua de esta página, editada a las 07:59 16 ene 2020 por SeroBOT (discusión · contribs.). La dirección URL es un enlace permanente a esta versión, que puede ser diferente de la versión actual.

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