1. DEFINICIONES Y PROPIEDADES
Definiciones (I)
-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
-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:
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]
