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.
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
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") + "]"
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:
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:
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]
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)
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 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.
class Arbol:
def __init__( self, esMenorFunction = lambda x,y: x < y ):
self.raiz = None
self.esMenor = esMenorFunction
class NodoBinario:
def __init__( self, elemento, padre ):
self.elemento = elemento
self.izquierda = None
self.derecha = None
self.padre = padre
def eliminar(arbol, element):
eliminarNodo(arbol, buscarNodo(arbol.raiz, element, arbol.esMenor))
def eliminarNodo(arbol, nodo):
if (not tieneHijos(nodo)):
eliminarSinHijos(arbol, nodo)
elif (tieneAmbosHijos(nodo)):
eliminarConAmbosHijos(arbol, nodo)
elif (tieneHijoDerecho(nodo)):
eliminarCon1Hijo(arbol, nodo, nodo.derecha)
else:
eliminarCon1Hijo(arbol, nodo, nodo.izquierda)
def tieneHijoDerecho(nodo): return nodo.derecha != None
def tieneHijoIzquierdo(nodo): return nodo.izquierda != None
def tieneHijos(nodo): return tieneHijoDerecho(nodo) or tieneHijoIzquierdo(nodo)
def tieneAmbosHijos(nodo): return tieneHijoDerecho(nodo) and tieneHijoIzquierdo(nodo)
def esHijoIzquierdo(nodo): return nodo.padre.izquierda == nodo
def esRaiz(nodo): return nodo.padre == None
def eliminarSinHijos(arbol, nodo):
if (esRaiz(nodo)):
arbol.raiz = None
elif esHijoIzquierdo(nodo):
nodo.padre.izquierda = None
else:
nodo.padre.derecha = None
def eliminarCon1Hijo(arbol, nodo, hijo):
if (esRaiz(nodo)):
arbol.raiz = hijo
arbol.raiz.padre = None
elif esHijoIzquierdo(nodo):
nodo.padre.izquierda = hijo
hijo.padre = nodo.padre
else:
nodo.padre.derecha = hijo
hijo.padre = nodo.padre
def eliminarConAmbosHijos(arbol, nodo):
menorHijoRamaDerecha = buscarNodoMenorValor(nodo.derecha)
eliminarNodo(arbol, menorHijoRamaDerecha)
nodo.elemento = menorHijoRamaDerecha.elemento
def buscarNodoMenorValor(nodo):
return nodo if nodo.izquierda == None else buscarNodoMenorValor(nodo.izquierda)
Todo el código fuente de árboles binarios está en éste link
Igualmente adjuntamos el proyecto python con todo el material.