Árboles

Antes de comenzar a trabajar sobre árboles es importante estudiar recursividad

Introducción

Algunas definiciones:

• Un árbol es una estructura de datos enlazada que organiza elementos en forma jerárquica. Es decir, hay una relación padre/hijos.
• Cada nodo puede tener más de un hijo, pero un solo padre.
• Existe un nodo que no tiene padre denominado raiz.
• Los nodos que no tienen hijos se denominan hojas
• Un árbol es de orden N (o N-ario) cuando la máxima cantidad de hijos que puede tener un nodo es N.
• La profundidad de un árbol es la distancia (saltos entre nodos) desde la raiz hasta la hoja más lejana.

Visión Recursiva

Cada rama de un árbol puede ser visto como un sub-árbol. De esta forma, el árbol genealógico de la abuela Bouvier está compuesto por el árbol de Marge, el de Patty y el de Selma. Esto repercute en el estilo de programación: todas las funciones que recorren o modifican el árbol hacen uso de características recursivas. Esto significa que a veces el término nodo y árbol se usan indistintamente, lo cual puede causar confusión al desprevenido.

Ejemplo de un árbol en python

definición

Haciendo uso de la noción recursiva de un árbol, podemos definir un árbol como la unión de un elemento y sus ramas.

class Arbol:

    def __init__(self, elemento):

        self.hijos = []

        self.elemento = elemento

agregar elementos

Una forma de agregar elementos podría ser:

abuela = "Jacqueline Gurney"

marge = "Marge Bouvier"

patty = "Patty Bouvier"

selma = "Selma Bouvier"

bart = "Bart Simpson"

lisa = "Lisa Simpson"

maggie = "Maggie Simpson"

ling = "Ling Bouvier"

arbol = Arbol(abuela)

agregarElemento(arbol, patty, abuela)

agregarElemento(arbol, selma, abuela)

agregarElemento(arbol, ling, selma)

agregarElemento(arbol, marge, abuela)

agregarElemento(arbol, bart, marge)

agregarElemento(arbol, lisa, marge)

agregarElemento(arbol, maggie, marge)

Para lo cual necesitamos escribir el método agregarElemento que recibe el árbol, el elemento a agregar, y el padre de dicho elemento. Este método obtiene el sub-árbol que contiene al elemento padre y le agrega una nueva rama (árbol) con el nuevo elemento.

Es importante entender que la búsqueda del sub-árbol debe ser recursiva. La condición de corte es si el elemento está en el árbol actual, si no se busca en cada uno de los hijos.

def agregarElemento(arbol, elemento, elementoPadre):

    subarbol = buscarSubarbol(arbol, elementoPadre);

    subarbol.hijos.append(Arbol(elemento))

def buscarSubarbol(arbol, elemento):

    if arbol.elemento == elemento:

        return arbol

    for subarbol in arbol.hijos:

        arbolBuscado = buscarSubarbol(subarbol, elemento)

        if (arbolBuscado != None):

            return arbolBuscado

    return None   

Profundidad y grado

• La profundidad de un árbol es 1 + la profundidad del hijo más profundo
• El grado es el maximo entre la cantidad de sus hijos directos y el grado de sus hijos

def profundidad(arbol):

    if len(arbol.hijos) == 0: 

        return 1

    return 1 + max(map(profundidad,arbol.hijos)) 

def grado(arbol):

    return max(map(grado, arbol.hijos) + [len(arbol.hijos)])

Recorridos

Recorrer un árbol significa comenzar a visitar a cada uno de los elementos (tanto al elemento de la raiz como a los elementos de sus descendientes). A veces se realiza porque se quiere ejecutar algo por cada uno u otras veces es porque se está buscando uno en particular.

Existen dos maneras de recorrer un árbol: profundidad primero y ancho primero.

Profundidad Primero

Esta forma es la más sencilla: consiste en explorar toda una rama antes de pasar a la siguiente. Es decir, hasta no terminar de recorrer toda la rama de marge, no iniciará con Patty.

Acá un diagrama que muestra el órden de recorrido sobre un árbol:

En el método que vimos anteriormente de buscarSubArbol estamos usando esta estrategia para encontrar el elemento. A continuación un ejemplo de una función de orden superior que ejecuta sobre cada elemento del árbol:

Al utilizarlo con una función que imprime un elemento :

def printElement(element):

    print element

ejecutarProfundidadPrimero(arbol, printElement)

podemos ver el siguiente resultado:

Jacqueline Gurney

Patty Bouvier

Selma Bouvier

Ling Bouvier

Marge Bouvier

Bart Simpson

Lisa Simpson

Maggie Simpson

Ancho Primero

Esta forma es un poco más compleja pero puede ser conveniente dependiendo del problema. En nuestro ejemplo irá recorriendo generación a generación: Primero la abuela, luego todas las hijas, y luego todos los nietos.

Acá otro diagrama a modo esquemático:

Para poder resolver este algoritmo, es necesario retrasar la ejecución de la función sobre los hijos hasta que no se haya terminado de ejecutar todos los hermanos/primos. Por eso se usa una cola (Primero que entra, Primero que sale) para lograr esto. Cuando se visita a un nodo, ejecuta la función, agrega sus hijos a la cola, y luego llama a la función recursiva pero en lugar de hacerlo sobre algún hijo suyo (como hacía profundidad primero) lo hace sobre el próximo de la cola, que seguramente es un alguien de su nivel si aún quedan o el primero del próximo nivel.

def ejecutarAnchoPrimero(arbol, funcion, cola = deque()):

    funcion(arbol.elemento)

    if (len(arbol.hijos) > 0):

        cola.extend(arbol.hijos)

    if (len(cola) != 0):

        ejecutarAnchoPrimero(cola.popleft(), funcion, cola)   

Se usa de la siguiente manera:

def printElement(element):

    print element

ejecutarAnchoPrimero(arbol, printElement)

Veamos paso a paso que ocurre:

Invocación:1

Elemento: Jackeline

Invocación:2

Elemento: Patty

No tiene hijos, por lo tanto no agrega elementos a la cola

Invocación:3

Elemento: Selma

Agrega a Ling a la cola

Invocación:4

Elemento: Marge

Agrega a Bart, Lisa y Maggie

Invocación:5

Elemento: Ling

Invocación:6

Elemento: Bart

Invocación:7

Elemento: Lisa

Invocación:8

Elemento: Maggie

Código fuente

El código fuente de árboles que vimos acá está adjunto a esta página como un export de un proyecto PyDev de eclipse.

Igualmente, está online en éste link:

http://xp-dev.com/svn/uqbar/examples/prog2/unidad5-recursividadYArboles/arboles