Estructura de datos. Árboles (página 2)

Partes: 1, 2

Ejemplos
Tamaño:
Cant(t:AB) ? Naturales (cantidad de nodos del árbol)
Cant( [] ) = 0
Cant([izq,a,der]) = 1 + Cant(izq) + Cant(der), donde a es el tipo e izq y der son árboles AB.
Prof (t:AB) ? Naturales (profundidad – niveles del árbol)

Prof ([]) = 0
Prof([izq, a, der]) = 1 + max( Prof(izq), Prof (der) )

Máximo de un árbol binario de naturales
Max: Naturales AB ? Naturales (precondición: el argumento debe ser un árbol no vacío)
Max ( [], n, [] ) = n
Max ( [], n, der) = max (n, Max (der))
Max ( izq, n, [] ) = max (n, Max (izq) )
Max (izq, n, der) = max3 (n, Max (izq), Max (der) )
(en las tres últimas ecuaciones suponemos izq y der no vacíos).
Ejemplos

Recorridas de árboles binarios:
En general, son procedimientos que visitan todos los nodos de un árbol binario efectuando cierta acción sobre cada uno de ellos.
La forma de estos procedimientos depende del orden que se elija para visitar los nodos.
Obviamente, recorrer un árbol vacío es trivial. Para recorrer un árbol no vacío hay tres órdenes naturales, según si la raíz sea visitada antes
que los subárboles, entre las recorridas de
los subárboles o después de recorrer los subárboles.

Tipos de Recorrida de Árboles

Árboles Binarios Ordenados (de búsqueda)
Consideremos árboles binarios de naturales (más generalmente, de cualquier tipo sobre el cual pueda definirse un orden lineal).
Un árbol binario de naturales está ordenado si cada nodo es mayor que todo nodo de su subárbol izquierdo y menor que todo nodo de su subárbol derecho.

Árboles Binarios Ordenados (de búsqueda)
Definición inductiva:
un árbol binario ordenado (de naturales) es:
o bien vacío
o bien consta de un natural n y dos árboles binarios ordenados: izq y der, tales que todo elemento de izq es menor que n y todo elemento de der es mayor que n.
(En esta definición no consideramos elementos repetidos – La generalización a este caso es obvia).
Recordar búsqueda binaria en vectores ordenados, por bipartición.

Árboles Binarios de búsqueda- Propiedades
Los árboles binarios de búsqueda representan directamente la estructura de la búsqueda binaria:
esMiembro: Nat x Nat AB ? Bool
esMiembro (n, [] ) = false
esMiembro (n, (izq, m, der) ) =
case
n < m ? esMiembro (n, izq)
n = m ? true
n > m ? es Miembro (n, der)
end

Árboles Binarios de búsqueda- Propiedades
Otra propiedad interesante de los árboles binarios ordenados es:
su linealización en (segundo) orden es una lista ordenada
lo cual da una idea para un algoritmo de ordenamiento de listas:
dada la lista a ser ordenada, formar con sus elementos un árbol binario ordenado.
luego, listar este árbol en orden.
(TreeSort)
Para resolver el primero de estos dos pasos, debe escribirse un algoritmo de inserción de un elemento en un árbol binario ordenado, de modo que el orden sea respetado.

Representación de Árboles Binarios en C
Caben las mismas consideraciones que para las listas:
hay árboles de tamaño arbitrario
interesa representarlos como estructuras dinámicas
Por ello, la representación natural es con punteros

Representación de Árboles Binarios en C
Definimos entonces:
typedef struct nodoIntAB{
int elem;
nodoIntAB *izq,*der;
}*intAB;

Representación de Árboles Binarios en C
Veamos ahora la función profundidad en C:
int profAB(intAB arbol){
if(arbol == NULL)
return 0;
else
return (1 + max(profAB(arbol->izq), profAB(arbol->der)));
}

Procedimiento de recorrida de un árbol binario en orden
Se aplica a cada nodo un procedimiento P que suponemos dado
Por ejemplo P podría ser: desplegar el elemento contenido en cada nodo
void intABRecorridaP(intAB arbol){
if ( arbol == NULL)
< < acción final>>
else{
intABRecorridaP (arbol->izq);
P(arbol->elem);
intABRecorridaP (arbol->der);
}
}

Procedimiento de recorrida de un árbol binario en orden
Suponemos aquí que P actúa solamente sobre los elementos (información en los nodos) y no sobre los punteros (estructura del árbol).
Dejamos abierta la posibilidad de una < < acción final>>, a realizar para cada subárbol vacío.

¿Cómo se escriben algoritmos iterativos sobre árboles?
recordemos las ideas de los algoritmos que recorren estructuras lineales (vectores, listas):
Vectores:

Listas:

¿Cómo se escriben algoritmos iterativos sobre árboles?
¿Qué pasa en el caso de los árboles binarios?
Debemos utilizar un puntero p para indicar el siguiente nodo a visitar.
Dado que estamos considerando la recorrida en pre-orden, entonces aplicaremos la acción que nos interese al nodo corriente y luego continuaremos la recorrida, primero por el subárbol izquierdo y luego por el derecho.

¿Cómo se escriben algoritmos iterativos sobre árboles?
Por lo tanto, al continuar hacia el subárbol izquierdo, dejamos pendiente la recorrida del subárbol derecho.
La situación al mover el puntero p es como sigue:

¿Cómo se escriben algoritmos iterativos sobre árboles?
Veamos el árbol representado con punteros, de acuerdo a las definiciones dadas antes:

¡¡¡ Y NO HAY MANERA DE VOLVER A ÉL DESDE DONDE ESTAMOS !!!

¿Cómo se escriben algoritmos iterativos sobre árboles?
Conclusión: hay que guardar en alguna estructura de datos los punteros a los subárboles que van quedando "pendientes".

¿Cuál es la estructura de datos que necesitamos?

¿Cómo se escriben algoritmos iterativos sobre árboles?
Consideremos un caso más simple:

¿Cómo se escriben algoritmos iterativos sobre árboles?
Al avanzar p aparecerá otro subárbol pendiente:

¿Cómo se escriben algoritmos iterativos sobre árboles?
De hecho tenemos que recordar todos los sucesivos subárboles derechos que van apareciendo durante la recorrida.
Cada nuevo subárbol derecho que aparece debe ser recorrido antes que los aparecidos anteriormente (*)
Por lo tanto, podemos apilar los punteros de los subárboles pendientes.

¿Cómo se escriben algoritmos iterativos sobre árboles?
Dicho de otra forma: estructuramos los punteros a subárboles pendientes en una pila.
El tope será el primer subárbol pendiente a recorrer. Debido a la observación marcada con (*) arriba, cada nuevo subárbol derecho que aparezca deberá ser colocado como nuevo tope de la pila.

¿Cómo se escriben algoritmos iterativos sobre árboles?
Conclusión: la estructura de datos a ser utilizada para recorrer un árbol binario es como sigue:

¿Cómo se escriben algoritmos iterativos sobre árboles?
Con esta idea puede completarse la versión iterativa del algoritmo de recorrida en pre-orden. (Ejercicio).
Se concluye que, en general, la programación iterativa de algoritmos en árboles es MUCHO más compleja que la recurrente.
Dado que los programas iterativos son en general más eficientes, se hace interesante estudiar métodos de transformación de algoritmos recurrentes en iterativos equivalentes.

¿Cómo se escriben algoritmos iterativos sobre árboles?
Si estos métodos pudieran ser automatizados, entonces podrían ser aplicados directamente por un compilador.
En tal caso, podríamos construir programas simples (recurrentes) sin tener que preocuparnos por la pérdida de eficiencia.

Inserción en un árbol binario ordenado:
void indABInsertar(int x, intAB &arbol){
//Precondición: t está ordenado //Postcond: x es insertado en árbol, manteniendo el orden. If (arbol == NULL){
arbol = new (intAB);
arbol->elem = x;
arbol->izq = NULL; arbol->der = NULL;
}
else if ( x < arbol->elem)
indABInsertar(x, arbol-> izq);
else // x >= arbol->elem
indABInsertar(x, arbol->der);
}

Inserción en un árbol binario ordenado:
Notar que se inserta siempre una nueva hoja:
insertar 5 resulta en

Representación de Árboles Finitarios como Binarios
Dado un árbol finitario:

puede representarse la misma información en un árbol binario.
La regla de la transformación es:
cada nodo apunta por izquierda a su
primer hijo, los hermanos se encadenan por
derecha.

Representación de Árboles Finitarios como Binarios