Ordenamiento con arbol binario

Solo disponible en BuenasTareas
  • Páginas : 4 (764 palabras )
  • Descarga(s) : 0
  • Publicado : 29 de mayo de 2011
Leer documento completo
Vista previa del texto
**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 irconstruyendo 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 in orden.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 in orden 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.
**ÁRBOLES**
Introducción
Es una estructura de datos no lineal que posee raíz, ramas y hojas,técnicamente constituye un grafo finito y sin ciclos. Un árbol define ciertos niveles jerárquicos precedidos por la raíz (1er. nivel), en donde las hojas constituyen el nivel más bajo.
Componentes
Raíz: Nodoque constituye la única entrada a la estructura (por ello es necesario tener un puntero sobre él).
Ramas o Arcos: Conexión entre dos nodos del árbol que representa una relación de jerarquía.
Hojas:Nodo sin hijos.
Características
Nivel o profundidad de un nodo: Longitud del camino para ir desde la raíz al nodo. Por definición la raíz está en el nivel 0. Por ejemplo: profundidad(Y)=2,profundidad(raíz)=0, profundidad(árbol)= profundidad(hoja más profunda).
[pic]
Altura de un nodo: Longitud del camino más largo desde el nodo a una hoja. Por ejemplo:
Altura(X)=1, Altura(Y)=0,Altura(árbol)=Altura(raíz)=profundidad(árbol)
Grado de nodo: Cantidad de hijos de un nodo cualquiera.
Grado de árbol: Cantidad máxima de hijos posibles de asociar a un nodo del árbol
Clasificación
Según...
tracking img