4 Estructuras No Lineales

4.1.1 CONCEPTO DE ÁRBOL.

Los árboles son estructuras dinámicas no lineales, hasta ahora solo se han manejado estructuras estáticas y dinámicas lineales, es decir a cada elemento de la estructura solo le sigue otro, en el caso de los árboles a estos les puede seguir uno o mas elementos, es decir que un elemento de la estructura puede apuntar a varios, además de esto son dinámicos ya que sepueden crear elementos que conformen el árbol cuando se requiera y en cualquier parte del programa.

Estructuras estáticas | Estructuras dinámicas |
Arreglos | Listas |
Pilas | Árboles |
Colas | |

Estructuras lineales | Estructuras no lineales |
Arreglos | Árboles |
Pilas | Árboles |
Colas | |
Listas | |

4.1.2 CLASIFICACIÓN DE ARBOLES.

· Árbol de búsqueda perfectamentebalanceado.
* Definición: Para todo nodo, la cantidad de nodos de su subárbol izquierdo difiere como máximo en 1 de la cantidad de nodos del subárbol derecho.
* En el peor caso, la búsqueda necesita O(log n).
* La inserción puede necesitar reorganizar todo el árbol, O(n).
· Árbol balanceado ó AVL (Adelson-Velskii y Landis).
* Es un árbol binario de búsqueda, con unacondición de balanceo más débil que hace que no sea tan costoso el proceso de balancear un árbol.
* Definición: Para todo nodo, la altura de sus subárboles difiere como máximo en 1. (Supondremos que la altura del árbol vacío es -1.)

· Árboles Binarios

Un árbol binario, es aquel que tiene como máximo 2 descendientes, es decir cada uno de los nodos del árbol tiene un máximo de 2 hijos;además si es binario de búsqueda se define de manera formal como: “Para todo nodo T del árbol debe cumplirse que todos los valores de los nodos del subárbol izquierdo de T serán menores o iguales al valor del nodo T. De forma similar, todos los valores de los nodos del subárbol derecho de T deben ser mayores o iguales al valor del nodo T ”.
Por lo mismo se pueden realizar las operaciones debúsqueda, inserción y eliminación, de manera más eficiente en este tipo de árbol.
Por ejemplo si tenemos los siguientes valores para insertar en un árbol binario de búsqueda:
34-10-56-82--46-25

4.1.3 OPERACIONES BÁSICAS SOBRE ARBOLES BINARIOS.

INSERCCIÓN EN UN ÁRBOL BINARIO DE BÚSQUEDA:
1. Debe compararse la clave a insertar con la raíz del árbol. Si es mayor, debe avanzarse hacia el subárbolderecho. Si es menor, debe avanzarse hacía el subárbol izquierdo.
2. Repetir sucesivamente el paso 1 hasta que se cumpla alguna de las siguientes condiciones:
1. El subárbol derecho es igual a vacío, o el subárbol izquierdo es igual a vacío, en cuyo caso se procede a insertar el elemento en el lugar que le corresponde.
2. La clave que quiere insertarse es igual a la raíz del árbol, en cuyocaso no se realiza la inserción.
BÚSQUEDA
En el caso de la búsqueda es este tipo de árbol, por lógica, será moviéndose en el árbol, dependiendo si el elemento a buscar es mayor o menor que la raíz, hasta que se encuentre o se determine que no esta en el árbol.
Por ejemplo si del árbol formado anteriormente buscamos el valor 46
Compararíamos el 46 con el 34 que es la raíz, como 46 es mayor nosmoveríamos al subárbol derecho.

Ahora nuestra raíz es 56, comparamos 46 con 56 y vemos que es menor que este, por lo que nos movemos hacía el subárbol izquierdo.

De esta forma encontramos que 46 se encuentra en el árbol.
RECORRIDOS EN ÁRBOLES.
Los recorridos que se pueden hacer en los árboles binarios de búsqueda, son los mismo que en los árboles en general:
Recorrido Preorden:
|Visita la raíz |
| Subárbol izquierdo |
| Subárbol derecho |
Recorrido Inorden:
| Subárbol izquierdo |
| Visita la raíz |
| Subárbol derecho |
Recorrido Postorden:
| Subárbol izquierdo |
| Subárbol derecho |
| Visita la raíz |
Recorrido Preorden: 34,10,25,56,46,82
Recorrido Inorden: 10,25,34,46,56,82
Recorrido Postorden: 25,10,46,82,56,34
BORRADO EN UN ÁRBOL BINARIO DE...