4.0 Estructuras de Datos No Lineales

4.0 Estructuras de Datos No Lineales.
A las estructuras de datos no lineales se les llama también estructuras de datos multienlazadas.
Cada elemento puede estar enlazado a cualquier otro componentes.
Se trata de estructuras de datos en las que cada elemento puede tener varios sucesores y/o varios predecesores.
Árboles.
Grafos.
Árboles.
● Cada elemento sólo puede estar enlazado con supredecesor y sus sucesores.
Puede tener varios sucesores.
Estructura no lineal jerárquica en la que cada elemento tiene un único antecesor y puede tener varios sucesores.
Existe un único camino entre el primer nodo de la estructura y cualquier otro nodo.

Se utilizan para representar todo tipo de jerarquías: árbol genealógico, taxonomías, diagramas de organización, etc.
En informática seutilizan para aplicaciones algorítmicas (ordenación, búsqueda), compilación (árboles sintácticos, árboles de expresiones), etc.
Formalmente, un árbol A es un conjunto finito de elementos con 0 o más nodos de forma que:
Se trata de una estructura vacía.
Si tiene componentes, los nodos restantes se dividen en uno o más conjuntos disjuntos cada uno de los cuales es a su vez un árbol. A estos nodosse les llama subárboles del raíz.
Se trata de una estructura recursiva.
Grafos.
● Cada elemento puede estar enlazado a cualquier otro.
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 puedeseguir 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 se pueden 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 perfectamente balanceado.
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).
         Árbolbalanceado ó AVL (Adelson-Velskii y Landis).
Es un árbol binario de búsqueda, con una condició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 2descendientes, 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 oiguales al valor del nodo T ”.
Por lo mismo se pueden realizar las operaciones de bú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 compararsela clave a insertar con la raíz del árbol. Si es mayor, debe avanzarse hacia el subárbol derecho. 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...