Árboles Binarios y Algoritmos de Ordenación: Conceptos y Ejemplos

Definiciones de Árboles Binarios

Árbol Equilibrado

Un árbol es equilibrado si:

Árbol Perfectamente Equilibrado

Un árbol está perfectamente equilibrado si:

Árbol Binario Completo

Un árbol binario completo es un árbol en el que hasta el penúltimo nivel tiene el máximo número de nodos posibles y en el último nivel todos los nodos están colocados de izquierda a derecha sin dejar huecos.

Árbol Binario Lleno

Un árbol binario es lleno si todos los nodos del árbol tienen:

hijos excepto los del último nivel.

Recorridos de Árboles Binarios

Hay tipos.

Recorrido en Anchura

Se recorren todos los niveles empezando por el nivel y cada nivel de izquierda a derecha.

Recorrido en Profundidad

Los prefijos pre, en, post hacen referencia a cuándo se visita al padre.

• Preorden: Primero se visita al padre, después al hijo izquierdo y después al hijo derecho.
• Enorden: Se visita al hijo izquierdo, luego al padre y luego al derecho.
• Postorden: Se visita al hijo izquierdo, después al hijo derecho y después al padre.

Árbol Binario de Búsqueda

Un árbol binario de búsqueda es un árbol binario en el que para todo nodo del árbol todo lo que está a la izquierda es menor y todo lo que está a la derecha es mayor.

Árboles AVL

Un árbol AVL es un árbol binario de búsqueda equilibrado.

Ejemplo de Construcción de un Árbol AVL

Dada la lista construir el árbol AVL.

Si vamos insertando enseguida obtenemos un árbol que no es AVL. Necesitamos aplicar una operación que nos permita construir un AVL. Estas operaciones son las rotaciones. Hay 4 que se explican debajo. Al insertar el surge el primer problema que se resuelve con la rotación 1). Al insertar el debemos aplicar la rotación 2). Al insertar el 7 también necesito efectuar la misma rotación. Seguimos insertando sin problema hasta llegar al nodo 15 en el que hay que emplear la rotación 3).

Rotaciones en Árboles AVL

Solo tenemos que examinar los caminos de búsqueda del nodo que acabamos de insertar. El camino de búsqueda son los nodos que van del nodo raíz al nodo que acabamos de insertar.

Rotación Simple Derecha

Ocurre en este caso: Cuando y con subárboles y pueden ser vacíos. Resulta el árbol equivalente de la derecha pero que sí es AVL.

Rotación Simple Izquierda

Cuando y con subárboles y pueden ser vacíos. Se aplica esta rotación obteniendo el AVL de la derecha.

Rotación Doble Izquierda

Habíamos visto que los dos eran positivos o los dos eran negativos. Sin embargo ahora tenemos que y . Aplicamos esta rotación en la que ahora hay que identificar tres nodos.

Rotación Doble Derecha

Habíamos visto que los dos eran positivos o los dos eran negativos. Sin embargo ahora tenemos que y . Aplicamos esta rotación en la que ahora hay que identificar tres nodos.

Borrado de Nodos en Árboles AVL

Si borro el por ejemplo deja de ser un árbol AVL. Podría aplicar una rotación. El 3 se queda con factor de equilibrio 2 y el con factor de equilibrio . No cuadra con ninguna rotación pero si aplico la rotación simple izquierda o la rotación doble izquierda que son las que más se parecen porque la raíz tiene factor de equilibrio 2 conseguimos un AVL.

Algoritmos de Ordenación

Los algoritmos de ordenación ordenan un conjunto de datos de acuerdo a uno de los campos. Ejemplo: en una guía telefónica los campos de cada individuo son el nombre del individuo y su número de teléfono, puedo ordenarla alfabéticamente o poniendo sus números en orden. Como vemos en el ejemplo la ordenación puede ser numérica o alfabética.

Tipos de Ordenación

• Externa: si lo que se ordena es un archivo.
• Interna: si es un TAD que tenemos en el propio programa.

Vamos a ver tres tipos de algoritmos básicos:

• Algoritmo de selección.
• Algoritmo de inserción.
• Algoritmo de burbuja.

Y tres algoritmos complejos:

• Heapsort.
• Quicksort.
• Mergesort.

Algoritmo de Selección

Supongamos que queremos ordenar . Buscamos el más pequeño (el 2) lo cambiamos con el primero (el 9). Volvemos a hacer lo mismo pero solo cogiendo los últimos números. Cuando encontramos el mínimo (el 5) cambiamos el segundo (el 9) con el mínimo que hayamos encontrado. Seguimos hasta terminar.

Algoritmo de Inserción

Supongamos que queremos ordenar . Metemos el primer elemento en la parte ordenada. Sacamos el segundo elemento de la parte desordenada y lo comparamos de atrás hacia adelante la parte ordenada. Si el primero es mayor lo pongo a la izquierda, si el segundo es mayor lo pongo a la derecha. En nuestro ejemplo: . etc. En general mientras haya elementos en la parte ordenada, saco uno y lo comparo con el último de la parte ordenada, si el que he sacado es mayor que el último de la parte ordenada lo pongo ahí, si no lo comparo con el anterior, etc. Si llego al final lo pongo el primero en la parte ordenada.

Ejercicio: Un vector contiene los siguientes 6 elementos . Los dos primeros elementos se han ordenado utilizando el algoritmo de inserción. ¿Cuál será el estado del vector después de tres pasadas más del algoritmo de inserción? .

Algoritmo de Burbuja

Se compara el primer elemento con el segundo. Si el primero es menor se queda igual. Si es mayor se intercambian. Después el segundo con el tercero etc. Contamos los intercambios que ha habido y si ha habido 0 la lista está ordenada. Si no tenemos que volver a repetirlo.

Ejercicio: ¿Cuántas pasadas realiza el algoritmo de burbuja para ordenar la siguiente lista ?

Ejercicio: Tenemos el siguiente vector: . Después de dos pasadas de un algoritmo de ordenación el vector queda de la siguiente forma: ¿Qué algoritmo se ha utilizado? Es el de selección.