ESTRUCTURAS NO LINEALES

ARBOLES

Un árbol consiste en un conjunto de nodos y un conjunto de aristas, de forma que se puede distinguir un nodo llamado raíz
· A cada nodo h, excepto la raíz, le llega una arista de otro nodo p (p padre de h, h uno de los hijos de p).
· Para cada nodo hay un camino (secuencia de aristas) único desde la raíz.

Terminología
· Un nodo es externo, si no tiene hijos (es hoja).
· Un nodo es interno, si tiene uno o más hijos.
· Un nodo es ascendiente de otro, si es padre de él o ascendiente de su padre.
· Un nodo es descendiente de otro, si este es ascendiente del primero.
· Los descendientes de un nodo determinan un subárbol en el que ese nodo hace el papel de raíz.

· Existe un orden lineal para todos sus hijos.
· Un árbol binario es un árbol ordenado, en el que cada nodo tiene 0, 1 o 2 hijos (el hijo izquierdo y el derecho).

Un camino de un nodo a otro, es una secuencia de aristas consecutivas que llevan del primero al segundo. Su longitud es el número de aristas que tiene.
La profundidad de un nodo es la longitud del camino de la raíz a ese nodo.
La altura de un árbol es la profundidad del nodo más profundo.

Factor de equilibrio
Cada nodo, además de la información que se pretende almacenar, debe tener los dos punteros a los árboles derecho e izquierdo, igual que los arboles binarios de busqueda (ABB), y además el dato que controla el factor de equilibrio.
El factor de equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo:
FE = altura subárbol derecho - altura subárbol izquierdo;
Por definición, para un árbol AVL, este valor debe ser -1, 0 ó 1.
Si el factor de equilibrio de un nodo es:
0 -> el nodo está equilibrado y sus subárboles tienen exactamente la misma altura.
1 -> el nodo está equilibrado y su subárbol derecho es un nivel más alto.
-1 -> el nodo está equilibrado y su subárbol izquierdo es un nivel más alto.
Si el factor de equilibrio Fe≥2 o Fe≤-2 es necesario reequilibrar.
Recorrido preorden

Recorrido postorden

Recorridos Preorden: Se recorrido es Raiz - Izquierda - Derecha [*, + , A , B , - , C , D]
Recorridos Inorden: Se recorrido es Izquierda - Raiz - Derecha [A , + , B, * , C , - , D ]
Recorridos Postorden: Su recorrido es Izquierda - Derecha - Raiz [A , B , + , C , D , - , * , ]

Árboles binarios de búsqueda
Un árbol binario de búsqueda es un árbol binario en el que para cada nodo n, todas las claves de los nodos del subárbol izquierdo son menores que la clave de n (o iguales) y todas las del subárbol derecho mayores (o iguales).

Operaciones
· Búsqueda
· Inserción
· Eliminación

EJEMPLO:
Buscamos el “3”:
• 3<4:>2: Subárbol derecho
• 3=3: Elemento encontrado
Inserción
Nos desplazamos dependiendo del resultado de la comparación, cuando lleguemos a una hoja insertamos.
– Si la clave del elemento a insertar coincide con la del nodo raíz el elemento a insertar sustituye al que había.
– Si es menor buscamos en el subárbol izquierdo.
– Si es mayor buscamos en el subárbol derecho.
– Si llegamos a un nodo degenerado .
– Si es menor insertamos a la izquierda.
– Si es mayor insertamos a la derecha.

Eliminación
· Es complicado ya que los nodos internos mantienen al árbol conectado. Para eliminar:
· Si se trata de una hoja se elimina directamente.
· Si tiene un único hijo se elimina el nodo haciendo que su nodo padre pase a referenciar a su nodo hijo.
· Si tiene dos hijos :
· Se sustituye el nodo por el Elimino el 5 (1 hijo).
· Menor elemento de su subárbol derecho.
· Se elimina el nodo correspondiente a dicho menor elemento.