Árboles Binarios

Árboles Binarios

Los árboles binarios tienen sólo dos ramas por cada nodo. Son particularmente interesantes porque se pueden utilizar para mantener un orden entre los elementos: Cualquier elemento menor está en la rama izquierda, mientras que cualquier elemento mayor está en la rama derecha

Este tipo de estructura presenta una ventaja con respecto a las listas enlazadas: En el peor de los casos, un elemento en el árbol se encuentra en una cantidad de pasos igual a la profundidad del mismo, mientras que en una lista ordenada el peor de los casos se encuentra en una cantidad de pasos igual a la cantidad de elementos.

Árbol binario de búsqueda en python

definición:

Para generar un árbol binario, además del elemento vamos a utilizar una función que permita determinar el orden de los elementos,

class ArbolBinario:

    def __init__( self, elemento, esMenorFunction = lambda x,y: x < y ):

        self.derecha = None

        self.izquierda = None

        self.elemento = elemento

        self.esMenor = esMenorFunction

Agregar Elemento

Para agregar un elemento, ya no se le indica el padre, el mismo árbol sabe dónde ubicarlo usando la función de comparación

def agregarElemento(arbol, elemento):

    if (arbol.esMenor(elemento, arbol.elemento)):

        agregarIzquierda(arbol, elemento)      

    else:

        agregarDerecha(arbol, elemento)

def agregarIzquierda(arbol, elemento):

    if arbol.izquierda == None:

        arbol.izquierda = ArbolBinario(elemento, arbol.esMenor)

    else:

        agregarElemento(arbol.izquierda, elemento)

def agregarDerecha(arbol, elemento):

    if arbol.derecha == None:

        arbol.derecha = ArbolBinario(elemento, arbol.esMenor)

    else:

        agregarElemento(arbol.derecha, elemento)

Ejecutemos la siguiente sentencia:

import datetime

arbol = ArbolBinario(Persona("Elisa", datetime.date(1981,12,13)), lambda x,y: x.fechaNacimiento > y.fechaNacimiento)

agregarElemento(arbol, Persona("Yesi", datetime.date(1984,12,1)))

agregarElemento(arbol, Persona("Leo", datetime.date(1980,11,1)))

agregarElemento(arbol, Persona("Pablo", datetime.date(1978,8,13)))

agregarElemento(arbol, Persona("Javier", datetime.date(1982,4,29)))

agregarElemento(arbol, Persona("Azul", datetime.date(2011,11,2)))

agregarElemento(arbol, Persona("Zoe", datetime.date(2007,6,4)))

Aquí la definición de la clase Persona que usamos para los ejemplos

import datetime

class Persona:

    def __init__(self, nombre, fechaNacimiento):

        self.nombre = nombre

        self.fechaNacimiento = fechaNacimiento

    def __str__(self):

        return self.nombre + "[" + self.fechaNacimiento.strftime("%d-%m-%Y") + "]"

Recorridos

Existen tres variantes del algorirmo de profundidad primero para árboles binarios: pre-orden, in-orden, post-orden. Lo que varía entre cada uno es el orden en el que se ejecuta la función sobre el nodo:

• pre-orden: nodo actual -> rama izquierda -> rama derecha
• in-orden: rama izquierda -> nodo actual -> rama derecha
• post-orden: rama izquierda -> rama derecha -> nodo actual

Teniendo en cuenta que hay una relación entre la rama izquierda y la derecha (en uno están los menores y en el otro los mayores), esto significa que:

• pre-orden: primero se ejecuta sobre la raiz, despues sobre todos los menores y despues sobre todos los mayores
• in-orden: se ejecuta primero todos los menores, luego la raiz, y luego los mayores, siendo éste el órden normal entre todos los elementos
• post-orden: primero se ejecuta sobre todos los menores, luego sobre todos los mayores y finalmente la raiz

Estas son las funciones de orden superior que recorren los árboles:

def ejecutarPreOrden(arbol, funcion):

    if (arbol != None):

        funcion(arbol.elemento)

        ejecutarPreOrden(arbol.izquierda, funcion)

        ejecutarPreOrden(arbol.derecha, funcion)

def ejecutarInOrden(arbol, funcion):

    if (arbol != None):

        ejecutarInOrden(arbol.izquierda, funcion)

        funcion(arbol.elemento)

        ejecutarInOrden(arbol.derecha, funcion)

def ejecutarPostOrden(arbol, funcion):

    if (arbol != None):

        ejecutarPostOrden(arbol.izquierda, funcion)

        ejecutarPostOrden(arbol.derecha, funcion)

        funcion(arbol.elemento)

Código que lo usa:

def imprimir(elemento):

    print elemento

print "in-orden:"

ejecutarInOrden(arbol, imprimir)

print "\npre-orden"

ejecutarPreOrden(arbol, imprimir)

print "\npost-orden"

ejecutarPostOrden(arbol, imprimir)

Y la salida por consola:

in-orden:

Azul[02-11-2011]

Zoe[04-06-2007]

Yesi[01-12-1984]

Javier[29-04-1982]

Elisa[13-12-1981]

Leo[01-11-1980]

Pablo[13-08-1978]

pre-orden

Elisa[13-12-1981]

Yesi[01-12-1984]

Azul[02-11-2011]

Zoe[04-06-2007]

Javier[29-04-1982]

Leo[01-11-1980]

Pablo[13-08-1978]

post-orden

Zoe[04-06-2007]

Azul[02-11-2011]

Javier[29-04-1982]

Yesi[01-12-1984]

Pablo[13-08-1978]

Leo[01-11-1980]

Elisa[13-12-1981]

Eliminación de elementos en Árboles Binarios

Hasta el momento trabajamos con árboles que agregan elementos pero nunca los remueven. La remoción de un elemento se vuelve dificultosa cuando se trata de la raiz, ya que al igual que nos sucede en las listas enlazadas, los usuarios de nuestro árbol tienen una referencia a la raiz que no se puede cambiar. Por eso todas las implementaciones de árboles binarios que soportan la eliminación de elementos utilizan dos clases: una que simplemente se encarga de tener un elemento a la raiz (Que generalmente se llama árbol) y otra que contiene al elemento y las ramas (que generalmente se llama nodo). Hay que tener cuidado con la nomenclatura porque a nivel conceptual un nodo puede ser visto como un árbol, pero en estas implementaciones un nodo es otra cosa de la estructura denominada árbol.

Por lo tanto, todo lo que habíamos desarrollado anteriormente y considerábamos un "árbol" será considerado un "nodo" en estas implementaciones. ahora cuando se ejecuta una función sobre un árbol, ésta trabaja sobre la raiz:

Definición:

class Arbol:

    def __init__( self, esMenorFunction = lambda x,y: x < y ):

        self.raiz = None

        self.esMenor = esMenorFunction

class NodoBinario: 

    def __init__( self, elemento):

        self.elemento = elemento

        self.izquierda = None

        self.derecha = None

Agregar un elemento:

No hay conceptos nuevos aquí, simplemente que hay que tener en cuenta el caso de un árbol vacío. Si el árbol no es vacío se resuelve de manera recursiva sobre los nodos:

def agregarElemento(arbol, elemento):

    if (arbol.raiz == None):

        arbol.raiz = NodoBinario(elemento, None)

    else:

        subAgregarElementoEnNodo(arbol.raiz, elemento, arbol.esMenor)

def subAgregarElementoEnNodo(nodo, elemento, funcionEsMenor):  

    if (funcionEsMenor(elemento, nodo.elemento)):

        agregarIzquierda(nodo, elemento, funcionEsMenor)      

    else:

        agregarDerecha(nodo, elemento, funcionEsMenor)

def agregarIzquierda(nodo, elemento, funcionEsMenor):

    if nodo.izquierda == None:

        nodo.izquierda = NodoBinario(elemento, nodo)

    else:

        subAgregarElementoEnNodo(nodo.izquierda, elemento,funcionEsMenor)

def agregarDerecha(nodo, elemento, funcionEsMenor):

    if nodo.derecha == None:

        nodo.derecha = NodoBinario(elemento, nodo)

    else:

        subAgregarElementoEnNodo(nodo.derecha, elemento,funcionEsMenor)

Recorridos:

Tampoco hay conceptos nuevos en el recorrido, la funcion que recorre recibe un árbol y delega en la función recursiva sobre los nodos

def ejecutarInOrden(arbol, funcion):

    subEjecutarInOrden(arbol.raiz, funcion)

def subEjecutarInOrden(nodo, funcion):

    if (nodo != None):

        subEjecutarInOrden(nodo.izquierda, funcion)

        funcion(nodo.elemento)

        subEjecutarInOrden(nodo.derecha, funcion)

Elminar un elemento

La eliminación de un elemento presenta ciertas dificultades debido a que hay que enganchar los hijos del nodo eliminado con el padre, pero respetando la condición de que un nodo no puede tener más de dos hijos:

Analicemos los casos particulares:

• Eliminar un nodo hoja (sin hijos)
• Eliminar un nodo con solo un hijo
• Eliminar un nodo con ambos hijos

Eliminar una hoja

Este es el caso más sencillo, ya que no hay que enganchar ningún nodo.

Eliminar un nodo con un hijo

En este caso se procede a remover el nodo, y la única rama hija del nodo pasa a ocupar el lugar del nodo eliminado en el padre. No importa de si se trata de una rama derecha o izquierda, el árbol mantiene el orden al realizar esta operación sin preocuparnos de realizar operaciones adicionales.

Eliminar un nodo con dos hijos

Este es el caso más complejo debido a que en el padre tengo un lugar solo para dos ramas. La estrategia para removerlo es eliminar el nodo inmediatamente mayor al que se quería eliminar previamente. Este nodo se encuentra navegando siempre por la izquierda del hijo derecho. Luego, se reemplaza el elemento del nodo que se quería eliminar por el elemento del nodo recientemente eliminado. Esto genera un árbol que mantiene el orden sin realizar una operación adicional, ya que al reemplazar el elemento por su siguiente, se sigue respetando que a izquierda están los menores y a derecha los mayores. Este procedimiento es recursivo y tiene como casos base los dos procedimientos explicados anteriormente (eventualmente llegará a un nodo con un hijo solo o una hoja)

Ejemplo en python

Por supuesto, para poder programar los algoritmos definidos anteriormente hay que tener en cuenta si el nodo que se elimina es la raiz o no, ya que se debe actualizar la variable del objeto árbol. Adicionalmente, en este ejemplo, se agregó a cada nodo una referencia al nodo padre, para simplificar estos algoritmos.

A continuación se agrega el código para la eliminación. Esta vez los test case están entre los archivos adjuntos a la página, ya que había demasiados casos para probar.

Código Fuente

Todo el código fuente de árboles binarios está en éste link

Igualmente adjuntamos el proyecto python con todo el material.