Un árbol binario es un árbol en el que de cada nodo cuelgan a los más dos árboles binarios.
Un árbol es una estructura de datos recursiva que se puede caracterizar en forma inductiva:
El árbol vacío es un árbol.
Un nodo del cual cuelgan uno más árboles es un árbol.
Un
árbol binario es un árbol en el que de cada nodo
cuelgan a los más dos árboles binarios.
Un árbol de búsqueda binaria (ABB) es un árbol binario que almacena en cada nodo una llave. El árbol de búsqueda binaria cumple las siguientes propiedades:
El árbol vacío es un ABB.
El árbol de la figura es un ABB cuando:
los árboles izquierdo y derecho son ABBs, y
la llave k es mayor que todas las llaves almacenadas en el ABB izquierdo.
la llave k es menor que todas las llaves almacenadas en el ABB derecho.
Representamos el arreglo asociativo mediante un objeto que tiene una referencia de la raíz de un ABB:
Nodo *raiz= NULL;
Cuando el arreglo está vacío, la raíz es nula y representa entonces el árbol vacío. Cuando el arreglo tiene al menos una asociación, la raíz no es nula y referencia una estructura Nodo que se define como:
typedef struct ABB
{
int llave;
char val[10];
struct ABB *izq;
struct ABB *der;
} Nodo;
En donde izq referencia la raíz del ABB izquierdo, o nulo si el ABB vacío, y der referencia respectivamente el ABB derecho. Un nodo almacena una asociación (llave, val), al igual que en una lista enlazada un eslabón almacena un asociación del arreglo asociativo.
La siguiente figura muestra dos posibles representaciones de un arreglo asociativo con asociaciones {3->"hola", 5->"que", 10->"tal"}:
Para implementar la operación get se utiliza un patrón de programación denominado búsqueda en ABBs. Esta búsqueda hace uso de un método recursivo que llamaremos buscar:
char *get(int llave)
{
return buscar(llave, raiz);
}
char *buscar(int llave, Nodo *nodo)
{
if (nodo==NULL) return NULL;
else
if (llave==nodo->llave) return nodo->val;
else
if (llave<nodo->llave) return buscar(llave, nodo->izq);
else
return buscar(llave, nodo->der);
}
La siguiente figura muestra gráficamente el funcionamiento de este método:
Cuando se invoca la operación put, se presentan dos casos:
La llave existía previamente, y por lo tanto ya existe en el árbol un nodo para esa llave en donde colocar el nuevo valor asociado. Por lo tanto en este caso no es necesario crear un nuevo nodo.
La llave no existía previamente, y por lo tanto se hace necesario crear un nuevo nodo e insertarlo en el árbol de modo que éste continúe siendo un ABB. En este caso, lo intuitivo es colocar el nodo como una hoja del árbol.
A continuación se presenta la implementación iterativa (es decir no recursiva) de put. Ésta resulta más simple conceptualmente que la implementación recursiva. Pero veremos que a la larga, la versión recursiva es un poco más breve que la iterativa.
void put(int llave, char val[])
{
Nodo *nodo, *n;
/* Dejamos altiro en memoria lo que vamos a almacenar */
nodo= (Nodo *) malloc (sizeof(Nodo));
nodo->llave=llave;
strcpy(nodo->val,val);
nodo->izq=NULL;
nodo->der=NULL;
if (raiz==NULL)
{
raiz= nodo;
return;
}
n= raiz;
while (true)
{
if (n->llave==llave)
{
strcpy(n->val,val);
return;
}
if (n->llave > llave)
{
if (n->izq!=NULL) n=n->izq;
else
{
n->izq= nodo;
return;
}
}
else
{
if (n->der!=NULL) n=n->der;
else
{
n->der= nodo;
return;
}
}
}
}
Esta solución no es elegante porque hay que diferenciar el caso en que el árbol está vacío (raiz==null), que el eslabón se agregue al lado izquierdo o que que se agregue al lado derecho. Sin embargo, esta solución es ligéramente más eficiente en un factor constante que la solución recursiva porque la iteración es más rápida que las llamadas recursivas.
Este método recibe como argumento la llave que se desea modificar, el nuevo valor asociado y la raíz del ABB en el que se debe realizar la modificación.
La clave para simplificar la implementación está en hacer que el método recursivo retorne una referencia del árbol modificado. En forma pictórica los distintos casos de modificación se explican en la siguiente figura:
El
código para implementar esta operación en C es:
void put(int llave, char val[])
{
raiz= modificar(llave, val, raiz);
}
Nodo *modificar(int llave, String val, Nodo *nodo)
{
if (nodo==NULL)
{
nodo = (Nodo *) malloc (sizeof(Nodo));
nodo->llave=llave;
strcpy(nodo->val,val);
nodo->izq=NULL;
nodo->der=NULL;
return nodo;
};
if (llave==nodo->llave) strcpy(nodo->val,val);
else if (llave < nodo->llave)
nodo->izq= modificar(llave, val, nodo->izq);
else
nodo->der= modificar(llave, val, nodo->der);
return nodo;
}
Como podemos apreciar, la versión es un poco más breve que la versión iterativa. Sin embargo, ambas son igualmente eficientes.
Para implementar el método remove se necesita usar el patrón de eliminación de nodos en ABBs. La siguiente figura explica en forma pictórica la lógica de este patrón:
Para
implementar esta operación se agrega el método
recursivo eliminar. Este método recibe un ABB como parámetro
y lo transforma de modo que ya no contenga la llave especificada. El
método retorna el ABB modificado:
void remove(int llave)
{
raiz= eliminar(llave, raiz);
}
Nodo *eliminar(int llave, Nodo *nodo)
{
if (nodo==NULL) return NULL;
if (nodo->llave==llave) return unir(nodo->izq, nodo->der);
if (llave<nodo->llave)
nodo->izq= eliminar(llave, nodo->izq);
else
nodo->der= eliminar(llave, nodo->der);
return nodo;
}
El caso difícil se presenta cuando hay que eliminar un nodo, pero ese nodo tiene subárboles izquierdo y derecho al mismo tiempo. En este caso por lo tanto fabricamos un nuevo método que une dos ABBs (unir). El trabajo realizado por este método queda representado en la siguiente figura:
El código de unir es:
Nodo *unir(Nodo *izq, Nodo *der)
{
Nodo *centro;
if (izq==NULL) return der;
if (der==NULL) return izq;
centro= unir(izq->der, der->izq);
izq->der= centro;
der->izq= izq;
return der;
}
Ejercicio 1: Implementación de la función int size(Nodo *nodo)
Implemente la función size que calcula el número de asociaciones de un arreglo asociativo implementado mediante ABBs.
Ejercicio 2: Implementación de la función int findKey(Nodo *nodo, char valor[])
Se desea desea agregar el método findKey de Map. Este método recibe como parámetro un valor y debe entregar alguna llave a la cual se asocia ese objeto. Formalmente, findKey debe cumplir con la siguiente propiedad:
Sea o un objeto cualquiera,
si findKey(o)==llave entonces get(llave)==o
Observe que pueden existir varias llaves que se asocian con el mismo objeto o. En tal caso, findKey(o) entrega cualquiera de esas llaves. Si no existe ninguna llave, findKey entrega -1.
Observación: Ud. debe buscar el objeto en todo el árbol. En este caso, el orden en que se encuentran las llaves en el ABB no sirve de nada.
Ejercicio 3: Inserción en la raiz de ABBs
En la implementación hecha para put, el eslabón que contiene la llave queda en su posición original (cuando la llave existía) o en una hoja del árbol (cuando la llave no existía). Implemente una versión de put en donde la llave que se reasocia con un nuevo objeto siempre quede en la raíz del ABB.
Indicaciones:
Suponga que la función recursiva que inserta la llave en la raíz del ABB se llama insertar. El caso simple es cuando la llave ya se encuentra en la raíz o el ABB está vacío.
Analícelo.
Cuando no se cumple ninguna de estas condiciones, sin pérdida de generalidad podemos suponer que la llave que se reasocia con un nuevo valor es menor que la llave almacenada en la raíz del ABB.
La siguiente figura muestra cómo debe calcular el nuevo árbol en el caso en que la llave que se desea agregar es menor que la llave que se encuentra almacenada en la raíz del ABB (ll<ll'):
El resultado de la función insertar será entonces el árbol A. Haga las figuras para los casos en que ll==ll' y ll>ll'. Finalmente programe las funciones put e insertar.