Estructuras de datos dinámicas/Árboles

Árboles

Árbol: estructura no lineal y dinámica de datos. Dinámica: puede cambiar durante la ejecución de un programa. No lineal: a cada elemento del árbol pueden seguirle varios elementos. Están formados por un conjunto de nodos y un conjunto de aristas que conectan pares de nodos.

Definición no recursiva

Conjunto de nodos y conjunto de aristas que conectan pares de nodos con las siguientes características:

Se distingue un nodo raíz (no tiene padre).

A cada nodo c (excepto la raíz) le llega una arista desde exactamente un nodo p diferente a c, al cual se le llama padre de c.

Hay un único camino desde la raíz hasta cada nodo. La misma longitud del camino es su número de aristas.

Definición recursiva

Un árbol es o bien vacío o consiste en una raíz y cero o más subárboles no vacíos $T_{1}$, $T_{2}$,…, $T_{n}$, cada una de cuyas raíces está conectada por medio de una arista con la raíz.

Definiciones

Los nodos que no tienen hijos se denominan hojas.

Un árbol con N nodos debe tener (N-1) aristas.

La profundidad de la raíz es 0 y la de cualquier nodo es la de su padre más 1.

La altura de un nodo es 1 más que la mayor altura de un hijo suyo. La altura de un árbol es la altura de la raíz.

Los nodos que tienen el mismo padre son hermanos.

Si hay un camino del nodo u al nodo v, u es ascendiente de v y v es descendiente de u. Si u $\neq$ v son propios.

El tamaño de un nodo es el número de descendientes (incluido él mismo). El tamaño de un árbol es el tamaño de su raíz.

Operaciones básicas

Insertar

Buscar

Eliminar

Ir a la raíz

Recorrer

Implementación primer hijo - siguiente hermano

Consiste en mantener los hijos de cada nodo en una lista enlazada. Cada nodo tiene dos referencias: una a su hijo más a la izquierda y otra a su hermano de la derecha.

Árboles binarios

Un árbol binario es o bien vacío o consta de una raíz, un hijo árbol binario izquierdo y otro derecho. Los árboles binarios de búsqueda permiten inserciones y acceso a los elementos en tiempo logarítmico. Los árboles binarios llamados colas con prioridad soportan acceso y eliminación del mínimo de una colección de elementos.

Árboles binarios de búsqueda

Para todo nodo A del árbol:

Todos los valores de los nodos del subárbol izquierdo de A deben ser menores al valor del nodo A.

Todos los valores de los nodos del subárbol derecho de A deben ser mayores o iguales al valor del nodo A. Un recorrido en inorden del árbol proporciona una lista en orden ascendente de los valores almacenados en los nodos. Para describir las operaciones, se considera que estas se enmarcan dentro de la clase NodoBinario. El lenguaje utilizado es JAVA.

Operación “buscar”

  buscar(Object o)
 {
   if (o.equals(valor)) 
     return true;
   else if (o.compareTo(valor)<0) 
     return buscar(getIzq(),o); 
   else return buscar(getDer(),o); 
 }

Operación “insertar”

 public NodoBinario insertar(Comparable o){ 
   if (o.compareTo(valor)<0) 
     setIzq(insertar(getIzq(),o)); 
   else setDer(insertar(getDer(),o)); 
   return this;
 }

Dentro de la clase NodoBinarioVacio:

 public NodoBinario insertar(Comparable o)
 {
   return new NodoBinario(o);
 }

Operación “recorrer”

Los recorridos pueden ser en preorden, postorden o inorden (orden simétrico). Todos son O(N).

 public void preOrder(SList aList)
 {
   aList.addElement(value);
   left.preOrder(aList);
   right.preOrder(aList);
 }

 public void inOrder(SList aList)
 {
   left.inOrder(aList);
   aList.addElement(value);
   right.inOrder(aList);
 }

 public void posOrder(SList aList)
 {
   left.posOrder(aList);
   right.posOrder(aList);
   aList.addElement(value);
 }

Los recorridos no necesitan obligatoriamente recursividad, se puede emplear una pila para realizarlos iterativamente.

Operación “borrado”

El nodo a borrar debe ser reemplazado por el nodo más a la derecha en el subárbol izquierdo o el nodo más a la izquierda en el subárbol derecho (el nodo más a la derecha del subárbol izquierdo será mayor o igual que cualquier otro nodo de ese subárbol y menor que todos los del subárbol derecho, y el nodo más a la izquierda del subárbol derecho será menor que todos los demás nodos de ese subárbol y mayor que todos los del subárbol izquierdo). Para el caso en el que el nodo elegido tengo un subárbol, hay por lo menos tres soluciones posibles:

La primera consiste en conservar la estructura del subárbol, y colgar del elemento ubicado en el extremo (el elemento menor o mayor) correspondiente al subárbol donde se encuentra el elemento a promover hacia la raíz (en este ejemplo, el subárbol izquierdo, por lo cual se buscará el elemento más a la izquierda), lo cual es consistente, porque todos los elementos en el subárbol promovido serán mayores que los del subárbol del cual estaban colgados a la derecha. El inconveniente que presenta esta solución es que debe utilizarse una función encontrarMínimo() o encontrarMáximo().

La segunda solución consiste en colgar del padre del nodo promovido hacia la raíz, el subárbol remanente. Esto es consistente, porque todo elemento del subárbol derecho de un nodo será mayor que el valor de ese nodo, y viceversa. Estas soluciones aprovechan la ventaja de contar con que el nodo promovido tiene, a lo sumo, un subárbol.

Un hueco dejado por un nodo promovido también puede pensarse como una eliminación. un arbol es un arbol jajaja

Árboles binarios perfectamente equilibrados

La eficiencia de las operaciones depende exclusivamente de la altura del árbol. Para un árbol de N nodos perfectamente equilibrado el coste de acceso es de orden logarítmico: O(log N). Sin embargo, se dice que si el árbol crece o decrece descontroladamente, el rendimiento puede disminuir considerablemente, siendo para el caso más desfavorable (insertar un conjunto de claves ordenadas en forma ascendente o descendente) el coste de acceso: O(N). En un árbol binario perfectamente equilibrado, el número de nodos en el subárbol izquierdo y el número de nodos en el subárbol derecho, difieren como mucho en una unidad, y los subárboles son también equilibrados

Árboles equilibrados

Un procedimiento de inserción que siempre restaure la estructura del árbol a un equilibrio perfecto es poco eficiente. Se usa una formulación menos estricta de “equilibrio”: Un árbol está equilibrado si para cada uno de sus nodos ocurre que las alturas de sus dos subárboles difieren como mucho en 1(Árboles AVL).

Factor de equilibrio (FE) de un nodo

El FE es la altura del subárbol izquierdo menos la altura del subárbol derecho. Los valores que puede tomar son -1, 0, 1. Si llegara a tomar los valores -2 o 2 debe reestructurarse el árbol. Todos los árboles perfectamente equilibrados son AVL. La longitud de camino media es prácticamente idéntica a la de un árbol perfectamente equilibrado. En un AVL se puede realizar con complejidad del O(log N) las siguientes operaciones:

Encontrar un nodo con una clave dada.

Insertar un nodo con una clave dada.

Borrar un nodo con una clave dada. Un árbol AVL de altura H tiene por lo menos (Fibonacci(H+3) -1) nodos. Los pasos necesarios para insertar un nodo en un árbol AVL son:

Agregar el nodo como en un árbol binario de búsqueda.

En el regreso por el camino de búsqueda se comprueba el FE de los nodos.

Si un nodo presenta un FE incorrecto (2 o -2) se reestructura el árbol y se continúa el ascenso hasta llegar a la raíz. Casos en situación de reestructurar:

1. Una inserción en el subárbol izquierdo del hijo izquierdo de X.
2. Una inserción en el subárbol derecho del hijo izquierdo de X.
3. Una inserción en el subárbol izquierdo del hijo derecho de X.
4. Una inserción en el subárbol derecho del hijo derecho de X.

Inserciones en los “márgenes”

1 y 4: inserciones en los “márgenes”: rotación simple: intercambia los papeles de los padres y de los hijos, manteniendo la ordenación.

 // Rotación izquierda - izquierda
 private static NodoAVL rotarConHijoIzq(NodoAVL A)
 {
   NodoAVL B = (NodoAVL) A.getIzq(); //Asigna nombre
   A.setIzq(B.getDer());
   B.setDer(A);
   return B;
 }

Inserciones por “dentro”

2 y 3: inserciones por “dentro”: rotación doble. Notar que una rotación simple no resuelve el problema, ya que la rama que provocó el desequilibrio se descuelga del nodo promovido y se cuelga al nodo que desciende un nivel, de manera que se mantiene con la misma profundidad, que es la que provocó el desequilibrio. Por lo tanto, antes de rotar, debe desplazarse el desequilibrio a la rama correspondiente, es decir, transformamos el caso de una inserción por dentro, a un caso de inserción en el margen, utilizando una rotación.

 // Rotación izquierda - derecha
 private static NodoAVL rotarDobleConHijoIzq(NodoAVL A)
 {
   NodoAVL B = (NodoAVL) A.getIzq(); //Asigna nombre
   A.setIzq(rotarConHijoDer((NodoAVL) B));
   return rotarConHijoIzq(A);
 }

Como se ve, el problema se convirtió en un problema igual al del primer caso. Los pasos necesarios para suprimir un nodo en un árbol AVL son:

Suprimir el nodo como en un árbol binario de búsqueda.

En el regreso por el camino de supresión se comprueba el FE de los nodos.

Si un nodo presenta un FE incorrecto (2 o -2) se reestructura el árbol y se continúa el ascenso hasta llegar a la raíz. La reestructuración se efectúa cuando al regresar por el camino de búsqueda después de una inserción o una supresión se comprueba que la condición del FE se ha violado. Una supresión puede provocar varias reestructuraciones. En la práctica se utilizan otros esquemas de equilibrio como los árboles rojinegros: como en los AVL las operaciones son logarítmicas en el peor caso. La ventaja es que las inserciones y eliminaciones pueden realizarse con un único recorrido descendente.

Árboles rojinegros

Árbol binario de búsqueda, donde cada nodo está coloreado con los colores rojo o negro, y se verifican las siguientes propiedades:

1. La raíz es negra.

2. Si un nodo es rojo, sus hijos deben ser negros.

3. Todos los caminos desde un nodo a un nodo vacío deben contener el mismo número de nodos negros.

Las condiciones (2) y (3) aseguran que el árbol nunca esté demasiado desbalanceado. (2) asegura que no puedan haber demasiados nodos rojos, y (3) dice que, despreciando el número de nodos rojos, que es limitado, el árbol es perfectamente balanceado. La condición (1) es trivial: si la raíz es roja, simplemente se colorea negra, ya que esto no violará ninguna regla. En los ARN la operación eliminar se complica. Cuando se necesitan árboles equilibrados y se requieren muchas eliminaciones se emplean los AA-Árboles que añaden una condición adicional a las impuestas por los ARN:

4. Los hijos izquierdos no pueden ser rojos.

Altura de un ARN

En un ARN con n nodos, la altura h será: $h\leq 2log_{2}(n+1)$

Demostración

La condición (3) nos permite asegurar que, despreciando el número de nodos rojos, el árbol es perfectamente balanceado, y, en virtud de esa característica, su altura $h\leq 2log_{2}(n+1)$. La condición (2) evita que haya nodos rojos consecutivos, como máximo, la mitad de los nodos de un camino -que constituirán una altura- serán rojos.

Operaciones

Se pueden realizar operaciones de búsqueda con complejidad O(log N), por lo expuesto anteriormente. Al realizar una inserción, la complejidad de búsqueda será O(log N), pero aparece un problema: el resultado será un árbol de búsqueda binario, pero no necesariamente un ARN. Si coloreamos el nuevo nodo rojo, el balance de negros quedará intacto, pero se puede incurrir en una violación rojo-rojo. Si lo coloreamos negro, no se incurrirá en una violación rojo-rojo, pero en este caso, siempre alteraremos el balance de negros. Al eliminar, si el nodo a eliminar es negro, ambas violaciones pueden aparecer.

Reparación del balance del árbol

Una vez detectada una violación, se deben tomar medidas que reparen el balance del árbol. Estas medidas utilizan dos herramientas: rotaciones y cambios de color.

Inserción ascendente

Sea X la nueva hoja añadida, P su padre, S el hermano de P (si existe) y G el abuelo.

1. Los nuevos nodos se insertan en el árbol como hojas de color rojo.

2. Si el padre es negro, hemos acabado.

3. Si el padre es rojo violamos la regla 2, entonces debemos modificar el árbol de forma que se cumpla la regla (2) sin introducir violaciones de la propiedad (3).

4. Si el padre P es la raíz, se colorea negro. La altura negra aumenta en 1, pero el balance se preserva. Hemos acabado.

Reparación del balance

Asumiendo que P no es la raíz

5. Si S es rojo, se puede aplicar un cambio de color: Se elimina así la violación, y el balance de negros se mantiene. ¿Qué pasa si el padre de G es también rojo? Solución: propagar este procedimiento hacia arriba hasta conseguir que no haya dos nodos rojos consecutivos o alcanzar la raíz. Esta propagación es análoga a la que se hace en los árboles AVL.

6. Si S es negro, tenemos dos casos, con sus simétricos asociados: violación en el margen, y violación por dentro.

7. Si es una violación es por dentro, la convertimos a una violación en el margen haciendo una rotación: Como X y P son rojos, no añaden nada en el balance de negros a los caminos que pasan por g, de manera que el balance se preserva.

8. Teniendo el caso de violación por dentro, se efectúa una rotación simple. La rama izquierda de desbalancea, le falta un nodo negro para todos sus caminos, y aún tenemos la violación rojo-rojo. Solucionamos ambos problemas haciendo un cambio de color.

Inserción descendente

Objetivo: garantizar que en el momento de la inserción S no sea rojo, de manera que sólo haya que añadir una hoja roja y, si fuere necesario, realizar una rotación (simple o doble). En el camino descendente, si un nodo X tiene dos hijos rojos, el color de X cambia a rojo y el de sus dos hijos a negro. El número de nodos negros en los caminos por debajo de X permanece inalterable. Si X es la raíz, la convertiríamos en roja, hay que volver a negro (esto no puede violar ninguna de las reglas). Si el padre de X es rojo, hay que aplicar rotación simple o doble. ¿Qué pasa si el hermano del padre de X es también rojo? Esta situación NO puede darse, gracias al proceso efectuado en el camino descendiente.

Árboles B

Mientras que la altura de un árbol binario completo es, aproximadamente, $log_{2}N$, la altura de un árbol M-ario completo es, más o menos, $log_{M}N$. Un B-árbol de orden M es un árbol M-ario que verifica:

Cada página, excepto la página raíz y las páginas hojas, tienen entre M/2 y M descendientes, y entre (M/2 -1) y (M-1) elementos.

La página raíz, o es una hoja o tiene entre 2 y M descendientes.

Las páginas hojas están todas al mismo nivel.

Relación entre los árboles B y los árboles rojinegros

Si juntamos un nodo negro con sus hijos rojos, si los hubiere, en un mismo nodo, se obtiene un árbol no binario con altura igual a la altura negra, con un máximo de 3 elementos y 4 hijos, y un mínimo de un elemento; en definitiva, es un árbol B de orden 4.

Búsqueda

Debe tenerse en memoria principal la página sobre la cual vamos a buscar. Considérese el elemento a buscar x. Si la búsqueda es infructuosa dentro de la página se estará en una de las siguientes situaciones:

$k_{i}<x<k_{i+1}$ para 1 ≤i < n. La búsqueda continúa en la página $r_{i}$.

$k_{n}<x$. La búsqueda continúa en la página $r_{n}$.

$x<k_{1}$. La búsqueda continúa en la página$r_{0}$. Si en algún caso la referencia es nula, es decir, si no hay página descendiente, entonces no hay ningún elemento x en todo el árbol y se acaba la búsqueda.

Inserción

Siempre se inserta en los nodos hojas. Primero se comprueba que la clave no se encuentre en el árbol. Si la cantidad de elementos es menor que 2n:

Se inserta en forma secuencial la clave. Si la cantidad de elementos es 2n:

Los 2n+1 elementos se dividen en dos páginas, excluyendo la clave del medio.

La clave del medio se inserta en el nodo padre.

Borrado

Si la clave a ser borrada no está en una hoja, su predecesor inmediato tiene que estar en una hoja (esto se debe a que todas las hojas tienen el mismo nivel, de manera que si existe un valor menor en un nodo más abajo, también tiene que haber uno mayor), y se puede promover, y así borrar el espacio que estaba en la hoja. Si la hoja queda con menos de n elementos, se comprueba si se puede promover un elemento de un hermano adyacente a su padre, y bajar el del padre a la hoja. Si el hermano tiene sólo n elementos, las dos hojas y la clave del medio se unen, y la clave del medio se elimina del nodo padre.

Árboles B+

Las diferencias con los árboles B son que:

Sólo los nodos hoja apuntan a los registros o cubetas del fichero.

Existe un orden lineal entre las hojas, que están encadenadas mediante punteros para permitir un eficiente acceso secuencial.

Búsqueda por clave

Buscar en la raíz el valor $k_{i}$ más pequeño mayor que la clave x. La búsqueda sigue por el puntero $p_{i}$ hasta que llegue a un nodo hoja, que será donde esté el puntero al bloque o cubeta (cuando un elemento se encuentre en una página raíz o interior la búsqueda continuará por la rama derecha de dicha clave, hasta llegar a una hoja).

Inserción

Se busca el nodo hoja correspondiente y se inserta la clave si no está allí. Si tiene lugar una partición, se inserta una clave en el nodo padre, que será duplicada si la partición ocurre en una hoja.

1. include<conio.h>
2. include<stdio.h>
3. include<iostream.h>
4. include<stdlib.h>
5. include<dos.h>

struct nodo {

int valor;
struct nodo*sig;

}*cab; void insertar(int num); void mostrar(void); void BorrarTodo(void); void Eliminar(int num); void insertord(int num);

void main (void) { int op, num; cab=NULL;

while(1)
{
clrscr();
printf("1.-Insertar un nodo.\n2.-Eliminar un nodo.\n3.-Mostrar\n4.-Insettar nodos en orden\n0.-Salir\n");
printf("\nElige una opcion: ");
scanf("%d",&op);
switch(op)
{
case 1:
printf("Valor del nodo que deseas insertar: ");
scanf("%d",&num);
insertar(num);
break;
case 2:
printf("Dame el valor del nodo a eliminar: ");
scanf("%d",&num);
Eliminar(num);
break;
case 3:
mostrar();
break;
case 4:
printf("Valor del nodo que deseas insertar: ");
scanf("%d",&num);
insertord(num);
break;
case 0:
BorrarTodo();
exit(0);//para usar exit debes declarar stdlib.h
break;
default:
printf("ERROR Opcion incorrecta");
getch();



}
getch();
}

} void insertar(int num) {

nodo *aux,*nuevo;
aux=cab;
nuevo=new nodo;
nuevo->valor=num;
nuevo->sig=NULL;
if(cab==NULL)
cab=nuevo;

else
{
while(aux->sig!=NULL)
aux=aux->sig;
aux->sig=nuevo;

}

}

void mostrar()
{
nodo *aux; //Aux es un apuntador
aux=cab; //En esta line aux toma la direccion de cab
while(aux!=NULL)
{
printf("%d, ",aux->valor);
aux=aux->sig;
}
}

void BorrarTodo(void)

{
nodo *aux;
aux=cab;
while(aux!=NULL)
{
cab=aux->sig;
delete aux;
aux=cab;
}
}

void Eliminar(int num) {

nodo *aux,*aux2, *prev;
int c=0;
aux=cab;

while(c!=1)
{
if(aux->valor==num)
{
c=1;
}
else{
prev=aux;
aux=aux->sig;
}
}

if(c==1)
{
if(prev->sig==NULL)
{
cab=cab->sig;
delete aux;
}
else
{
aux2 = aux->sig;
prev->sig = aux2;
delete aux;
}
}

}

void insertord(int num) {

nodo *aux,*nuevo,*aux2,*prev;
int c=0;
aux2=cab;
nuevo=new nodo;
// nuevo->valor=num;
while(aux2!=NULL)
{
if(aux2->valor>=num)
{

prev->sig=nuevo;
nuevo->valor=num;
nuevo->sig=aux2;
cab=prev;
aux2=NULL;
c=1;
}
prev=aux2;
aux2=aux2->sig;
}
if(aux2==NULL)
if(c==0)
{
insertar(num);
}
else
{
delete aux2;
}

}

Eliminación

Se busca el nodo hoja correspondiente y se elimina la clave. Si al eliminar una clave, n queda menor a (M/2 -1), entonces debe realizarse una redistribución de claves, tanto en el índice como en las páginas hojas.

1. include<conio.h>
2. include<stdio.h>
3. include<iostream.h>
4. include<stdlib.h>
5. include<dos.h>

struct nodo {

int valor;
struct nodo*sig;

}*cab; void insertar(int num); void mostrar(void); void BorrarTodo(void); void Eliminar(int num); void insertord(int num);

void main (void) { int op, num; cab=NULL;

while(1)
{
clrscr();
printf("1.-Insertar un nodo.\n2.-Eliminar un nodo.\n3.-Mostrar\n4.-Insettar nodos en orden\n0.-Salir\n");
printf("\nElige una opcion: ");
scanf("%d",&op);
switch(op)
{
case 1:
printf("Valor del nodo que deseas insertar: ");
scanf("%d",&num);
insertar(num);
break;
case 2:
printf("Dame el valor del nodo a eliminar: ");
scanf("%d",&num);
Eliminar(num);
break;
case 3:
mostrar();
break;
case 4:
printf("Valor del nodo que deseas insertar: ");
scanf("%d",&num);
insertord(num);
break;
case 0:
BorrarTodo();
exit(0);//para usar exit debes declarar stdlib.h
break;
default:
printf("ERROR Opcion incorrecta");
getch();



}
getch();
}

} void insertar(int num) {

nodo *aux,*nuevo;
aux=cab;
nuevo=new nodo;
nuevo->valor=num;
nuevo->sig=NULL;
if(cab==NULL)
cab=nuevo;

else
{
while(aux->sig!=NULL)
aux=aux->sig;
aux->sig=nuevo;

}

}

void mostrar()
{
nodo *aux; //Aux es un apuntador
aux=cab; //En esta line aux toma la direccion de cab
while(aux!=NULL)
{
printf("%d, ",aux->valor);
aux=aux->sig;
}
}

void BorrarTodo(void)

{
nodo *aux;
aux=cab;
while(aux!=NULL)
{
cab=aux->sig;
delete aux;
aux=cab;
}
}

void Eliminar(int num) {

nodo *aux,*aux2, *prev;
int c=0;
aux=cab;

while(c!=1)
{
if(aux->valor==num)
{
c=1;
}
else{
prev=aux;
aux=aux->sig;
}
}

if(c==1)
{
if(prev->sig==NULL)
{
cab=cab->sig;
delete aux;
}
else
{
aux2 = aux->sig;
prev->sig = aux2;
delete aux;
}
}

}

void insertord(int num) {

nodo *aux,*nuevo,*aux2,*prev;
int c=0;
aux2=cab;
nuevo=new nodo;
// nuevo->valor=num;
while(aux2!=NULL)
{
if(aux2->valor>=num)
{

prev->sig=nuevo;
nuevo->valor=num;
nuevo->sig=aux2;
cab=prev;
aux2=NULL;
c=1;
}
prev=aux2;
aux2=aux2->sig;
}
if(aux2==NULL)
if(c==0)
{
insertar(num);
}
else
{
delete aux2;
}

}