Tema: Arboles

1. DEFINICIONES Y PROPIEDADES

Definiciones (I)

-Un Árbol consiste en un nodo (r, denominado nodo raíz) y una lista o conjunto de subárboles (A1, A2, .. A k).
-Si el orden de los subárboles importa, entonces forman una lista, y se denomina árbol ordenado (por defecto un árbol se supone que es ordenado). En caso contrario los subárboles forman un conjunto, y se denomina árbol no ordenado.
-Se definen como nodos hijos de "r" a los nodos raíces de los subárboles A1, A2, .. Ak
-Si "b" es un nodo hijo de a entonces a es el nodo padre de "b"
-Un nodo puede tener cero o más hijos, y uno o ningún padre. El único nodo que no tiene padre es el nodo raíz del árbol.
-Un nodo sin hijos se denomina nodo hoja o externo. En caso contrario se denomina nodo interno.

Definiciones (II)

-Se define un camino en un arbol como cualquier secuencia de nodos del arbol, n 1 ... n p, que cumpla que cada nodo es padre del siguiente en la secuencia (es decir, que ni es el padre de ni+1). La longitud del camino se define como el número de nodos de la secuencia menos uno (p-1).
-Los descendientes de un nodo (c en el diagrama) son aquellos nodos accesibles por un camino que comience en el nodo.
-Los ascendientes de un nodo ( f en el diagrama) son los nodos del camino que va desde la raiz a él.

Altura

-Se define la altura de un nodo en un árbol como la longitud del camino más largo que comienza en el nodo y termina en una hoja. 

    *La altura de un nodo hoja es 0 

    *La altura de un nodo es igual a la mayor altura de sus hijos + 1 

-La altura de un árbol se define como la altura de la raíz. 

-La altura de un árbol determina la eficiencia de la mayoría de operaciones definidas sobre árboles.

Profundidad

-Se define la profundidad de un nodo en un árbol como la longitud del camino (único) que comienza en la raíz y termina en el nodo. También se denomina nivel. 

-La profundidad de la raíz es 0 

-La profundidad de un nodo es igual a la profundidad de su padre + 1

Recorrido de árboles

-Preorden: Se pasa por la raiz y luego se recorre en preorden cada uno de los subárboles. Recursivo. -

-Postorden: Se recorre en postorden cada uno de los subárboles y luego se pasa por la raíz. Recursivo. 

-Inorden: Se recorre en inorden el primer subárbol (si existe). Se pasa por la raíz y por último se recorre en inorden cada uno de los subárboles restantes. Tiene sentido fundamentalmente en árboles binarios. Recursivo. 

-Por Niveles: Se etiquetan los nodos según su profundidad (nivel). Se recorren ordenados de menor a mayor nivel, a igualdad de nivel se recorren de izquierda a derecha. 

-No recursivo: Se introduce el raíz en una cola y se entra en un bucle en el que se extrae de la cola un nodo, se recorre su elemento y se insertan sus hijos en la cola.

Recorrido de árboles (II)

-Preorden: a,b,c,e,f,g,d 

-Postorden: b,e,g,f,c,d,a 

-Inorden: b,a,e,c,g,f,d 

-Por Niveles: a,b,c,d,e,f,g 

-Preorden: a (b) (c (e) (f (g))) (d) g 

-Postorden: (b) ((e) ((g) f) c) (d) a 

-Inorden: (b) a ((e) c ((g) f)) (d) 

-Por Niveles: (a) (b c d) (e f) (g)

Expresiones matemáticas 

-Preorden -> Notación prefija : * 1 + ^ 3 4 2 

-Postorden -> Notación postfija: 1 3 4 ^ 2 + * 

-Inorden -> Notación habitual: 1 * ((3 ^ 4) + 2)

Evaluación de expresiones

Se recorre el arbol en postorden: Si es un operando, se inserta en pila Si es un operador: 

   *Se extraen dos operandos 

   *Se aplica el operador 

Se inserta en pila el resultado 

Al final, la pila debe contener un único valor, el resultado.

2. ÁRBOLES BINARIOS

Árbol binario

-Es un árbol que o bien esta vacío (sin contenido) o bien consta de un nodo raiz con dos subárboles binarios, denominados izquierdo y derecho. 

   *La existencia de árboles vacíos es una convención para que no exista ambigüedad al identificar el         subarbol izquierdo y derecho. Se representa por un cuadrado. 

   *La altura de un árbol vacío es -1

   *Cada nodo puede tener 0 hijos (subárbol izquierdo y derecho vacíos), 1 hijo (algún subárbol vacío)        o 2 hijos.

Variantes de árboles binarios

Árbol estricto: 

-Si un subárbol está vacío, el otro también. Cada nodo puede tener 0 ó 2 hijos. 

Árbol lleno: 

-Árbol estricto donde en cada nodo la altura del subárbol izquierdo es igual a la del derecho, y ambos subárboles son árboles llenos. 

Árbol completo: 

-Arbol lleno hasta el penúltimo nivel. En el último nivel los nodos están agrupados a la izquierda.

Árboles completos (I)

Los árboles llenos son los árboles con máximo número de nodos ( n) para una altura ( h) dada. Se cumple que n = 2 h+1-1 

   *El número de nodos de un árbol lleno sólo puede ser una potencia de dos menos uno: 1, 3, 7, 15, 31, … 

Los árboles completos pueden almacenar cualquier número de nodos y se sigue cumpliendo que su altura es proporcional al logaritmo del número de nodos: h O(log n ) 

Además tienen la propiedad de que conocido el recorrido por niveles del árbol es posible reconstruirle:

Árboles completos (II)

Es posible almacenar un árbol completo en un vector en el orden dado por su recorrido por niveles, y a partir del índice de un elemento en el vector conocer el índice de su nodo padre y los de sus nodos hijos:

3. MONTÍCULOS (BINARIOS)

Montículo 

-Un montículo (binario) es un arbol completo cuyos nodos almacenan elementos comparables mediante < y donde todo nodo cumple la propiedad de montículo: 

-Propiedad de montículo: Todo nodo es menor que sus descendientes. (montículo de mínimos).

Ejemplo:

Propiedades del Montículo 

-El nodo raíz (en primera posición del vector) es el mínimo. 

-La altura de un montículo es logarítmica respecto al número de elementos almacenados (por ser arbol completo). 

-Si un sólo elemento no cumple la propiedad de montículo, es posible restablecer la propiedad mediante ascensos sucesivos en el árbol (intercambiándole con su padre) o mediante descensos en el árbol (intercambiándole con el mayor de sus hijos). El número de operaciones es proporcional a la altura. 

-Para insertar un nuevo elemento se situa al final del vector (última hoja del árbol) y se asciende hasta que cumpla la propiedad. 

-Para eliminar la raiz se intercambia con el último elemento (que se elimina en O(1)) y se desciende la nueva raiz hasta que cumpla la propiedad.

Utilidad 

-Un montículo es una representación extremadamente útil para el TAD Cola de Prioridad: 

   *El acceso al mínimo es O(1). 

   *La inserción por valor es O(log n) (tiempo amortizado). 

   *El borrado del mínimo es O(log n). 

   *No usa una representación enlazada, sino un vector. 

   *La creación a partir de un vector es O(n) y no requiere espacio adicional. 

   *El borrado o modificación de un elemento, conocida su posición en el montículo, es O(log n). 

-Existen otras operaciones para las que no se comporta bien: 

   *Para la búsqueda y acceso al i-ésimo menor se comporta igual que un vector desordenado. 

   *La fusión de montículos (binarios) es O(n).

Representación en Java

Elevación de un nodo 

Descanso de un nodo

Acceso al mínimo e inserción

Ejemplo de inserción

Borrado del mínimo

Ejemplo: Borrado mínimo

Creación a partir de array 

Es posible crear un montículo directamente de un array, sin necesidad de realizar "n" inserciones: 

Se hace un recorrido por niveles, del penúltimo hacia arriba, descendiendo la raíz de esos subárboles. El orden es O(n) y no se requiere espacio extra.

Ordenación por montículos 

-La ordenación por montículos se basa en la posibilidad de crear un montículo directamente sobre el propio array, y del efecto colateral del borrado del mínimo, que (al intercambiarle con el último) lo coloca en la última posición. 

   *Primero se reorganiza un vector desordenado como montículo: Esta operación tarda O(n). 

   *A continuación se realizan n extracciones del mínimo: O(n log n). 

-El resultado es un montículo vacío (num = 0), pero en el vector que lo sostenía se han depositado los elementos borrados en las posiciones inversas: Se obtiene un vector ordenado de mayor a menor. 

   *Con un montículo de máximos se obtendría un vector ordenado de menor a mayor. 

-El tiempo es O(n log n) y el espacio O(1).

Otros montículos 

-Los montículos que hemos visto son los montículos binarios. Existen otros tipos de montículos, generalmente basados en representación enlazada (se sigue manteniendo la propiedad de montículo)      *Montículo binomial: La operación de fusión de montículos es O(log n), en vez de O(n) como en          los binarios. Sin embargo, el acceso al mínimo es O(log n) en vez de O(1). 

   *Montículo de Fibonacci: Las operaciones de acceso al mínimo, inserción y fusión son O(1) en            tiempo amortizado. La operación de borrado del mínimo es O(log n), también en tiempo                      amortizado. 

   *Montículo Min-Max: Cada nodo en nivel par es menor que sus descendientes, y cada nodo en              nivel impar es mayor que sus descendientes.

4. ÁRBOLES BINARIOS DE BÚSQUEDA

Árbol Binario de Búsqueda 

-Un árbol binario de búsqueda (árbol BB) es un árbol binario cuyos nodos almacenan elementos comparables mediante < y donde todo nodo cumple la propiedad de ordenación: 

-Propiedad de ordenación: Todo nodo es mayor que los nodos de su subárbol izquierdo, y menor que los nodos de su subárbol derecho.

Ejemplo de árbol Binario de Búsqueda

Propiedades y operaciones 

-Un recorrido inorden por el árbol recorre los elementos en orden de menor a mayor. 

-El elemento mínimo es el primer nodo sin hijo izquierdo en un descenso por hijos izquierdos desde la raíz. 

-El elemento máximo es el primer nodo sin hijo derecho en un descenso por hijos derechos desde la raíz. 

-Para buscar un elemento se parte de la raíz y se desciende escogiendo el subárbol izquierdo si el valor buscado es menor que el del nodo o el subárbol derecho si es mayor. 

-Para insertar un elemento se busca en el árbol y se inserta como nodo hoja en el punto donde debería encontrarse. 

-Para borrar un elemento, se adaptan los enlaces si tiene 0 o 1 hijo. Si tiene dos hijos se intercambia con el máximo de su subárbol izquierdo y se borra ese máximo.

Representación en Java

Acceso por valor (Búsqueda)

Inserción

Borrado(I)

Borrado(II)

Ejemplo de borrado – 0 hijos

Ejemplo de borrado – 1 hijos

Ejemplo de borrado – 2 hijos

5. ÁRBOLES B 

Motivación

Los sistemas de almacenamiento masivo suelen tener un tiempo de acceso mucho mayor que el tiempo de transferencia: La localización de un elemento es mucho más costosa que la lectura secuencial de datos, una vez localizados.
Esto se aplica sobre todo a discos duros, pero también, aunque en menor medida, a memorias de estado sólido (flash) e incluso a memorias volátiles.
Esto supone un problema para estructuras enlazadas, como los árboles AVL, donde las operaciones acceden a bastantes nodos de pequeño tamaño.
Para grandes volúmenes de datos, sería conveniente reducir el número de accesos, a cambio de que esos accesos contuvieran elementos de mayor tamaño

Caso practico (arboles  Adelson-Velskii y Landis)

El SACYL trabaja con una base de datos de unas 2.500.000 tarjetas sanitarias, ocupando cada una aprox. 1 Kb de datos.
Si se almacenan en un árbol AVL, su altura (árbol de Fibonacci) sería:

Lo que supone entre 25-31 accesos a disco para cualquier búsqueda de un elemento.
En cambio, si se almacenan en un Árbol B de orden 1.000 (aproximadamente 1 Mb por nodo) tendría altura 3, o 2 con una ocupación media del 80%.
Sólo se necesitarían 1 ó 2 accesos a disco (la raíz reside en memoria) para cada búsqueda.
El orden para ambos casos es logarítmico, pero si el tiempo de acceso es dominante, la segunda solución sería 10-30 veces más rápida.


Arboles (a.b)

Los árboles (a,b) son árboles generales (no binarios) donde cada nodo interno puede tener un número de hijos, m+1, en el rango [a,b].
Cada nodo almacena "m" claves (elementos comparables por <), ordenadas de menor a mayor, que sirven para que se pueda usar como un árbol de búsqueda.  El contenido típico de un nodo consiste en:
   *Un entero, m "pertenece a" [a-1, b-1], que indica el número de claves almacenadas.
   *Un vector, c, de capacidad b-1, que almacena las m claves.
   *Un vector, e, de capacidad b, que almacena los m+1 enlaces a hijos.
Propiedad de ordenación: Nodo e[i] almacena claves menores que c[i]