3.1 CONCEPTO GENERAL DE ARBOLES
El Árbol es una estructura de datos muy importante en la informática en la ciencia de la computación. Los arboles son estructura no lineales al contrario que los arrays y las lista enlazadas que constituye estructuras lineales. Es una estructura de datos no lineal que posee raíz, ramas y hojas, técnicamente constituye un grafo finito y sin ciclos. Un árbol define ciertos niveles jerárquicos precedidos por la raíz (1er. nivel), en donde las hojas constituyen el nivel más bajo.
El Árbol es una estructura de datos muy importante en la informática en la ciencia de la computación. Los arboles son estructura no lineales al contrario que los arrays y las lista enlazadas que constituye estructuras lineales. Es una estructura de datos no lineal que posee raíz, ramas y hojas, técnicamente constituye un grafo finito y sin ciclos. Un árbol define ciertos niveles jerárquicos precedidos por la raíz (1er. nivel), en donde las hojas constituyen el nivel más bajo.
Componentes
Raíz: Nodo que constituye la única entrada a la estructura (por ello es necesario tener un puntero sobre él).
Ramas o Arcos: Conexión entre dos nodos del árbol que representa una relación de jerarquía.
Hojas: Nodo sin hijos.
Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. Los árboles son estructuras que organizan sus elementos, denominados nodos, formando jerarquías. De entre estos nodos existe uno especial denominado raíz.
(Autor: Ignacio Zahonera Martínez)
En el capítulo se estudiara el concepto de árbol general y los tipos de árboles más usuales, binario y binario de búsqueda. Asimismo se estudiara algunas aplicaciones típicas del diseño y construcción de árboles.
3.2 REPRESENTACIÓN DE ARBOLES BINARIOS
Un Árbol Binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario. Cada nodo puede tener, cero, uno, o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.
3.2.1 Árbol binario completo
Un árbol binario completo de profundidad n es un árbol en el que para cada nivel, del O al nivel n-1 tiene un conjunto lleno de nodos y todos los nodos hoja a nivel n ocupan las posiciones más a la izquierda del árbol.
Un árbol binario completo que contiene 2" nodos a nivel n es un árbol lleno. Un árbol lleno es un árbol binario que tiene el máximo número de entradas para su altura. Esto sucede cuando el Último nivel está lleno. La Figura muestra un árbol binario completo; el árbol de la Figura se corresponde con uno lleno.
3.2.2 Estructura de un árbol binario
La estructura de un árbol binario se construye con nodos. Cada nodo debe contener el campo dato (datosa almacenar) y dos campos punteros, uno ahí subárbol izquierdo y otro al subárbol derecho, que se conocen Como puntero izquierdo (izquierdo, izdo.) y puntero derecho (derecho, dcho.) respectivamente.Un valor NULL indica un árbol vacío.
El algoritmo correspondiente a la estructura de un árbol es el siguiente:
Nodo
SubarbolIzquierdo
Datos
SubarbolDerecho
Fin Nodo
< Puntero a Nodo>
<Tipodato>
< Puntero a Nodo>
La Figura muestra un árbol binario y su estructura en nodos:
Ejemplo:
Representar la estructura en nodos de los dos árboles binarios de raíz A:
La representación enlazada de estos dos árboles binarios es:
3.3 OPERACIONES SOBRE ARBOLES
Una vez que se tiene creado un árbol binario, se pueden realizar diversas operaciones sobre él. El hacer uso de una operación u otra dependerá de la aplicación que se le quiera dar al árbol. Algunas de las operaciones típicas que se realizan en árboles binarios son:
Determinar su altura.
Determinar su número de elementos.
Hacer una copia.
Visualizar el árbol binario en pantalla o en impresora.
Determinar si dos árboles binarios son idénticos.
Borrar (eliminar el árbol).
Si es un árbol de expresión', evaluar la expresión.
Si es un árbol de expresión, obtener la forma de paréntesis de la expresión.
Todas estas operaciones se pueden realizar recorriendo el árbol binario de un modo sistemático. El recorrido de un árbol es la operación de visita al árbol, o lo que es lo mismo, la visita a cada nodo del Árbol una vez y sólo una. La visita de un árbol es necesaria en muchas ocasiones, por ejemplo, si se desea imprimir la información contenida en cada nodo. Existen diferentes formas de visitar o recorrer un árbol que se estudiarán más tarde.
3.3.1 Recorrido de un árbol
Para visualizar o consultar los datos almacenados en un árbol se necesita recorrer el árbol o visitar los nodos del mismo. Al contrario que las listas enlazadas, los árboles binarios no tienen realmente un primer valor, un segundo valor, tercer valor, etc. Se puede afirmar que el raíz viene el primero, pero ¿Quién viene a continuación? Existen diferentes métodos de recorrido de árbol ya que la mayoría de las aplicaciones binarias son bastante sensibles al orden en el que se visitan los nodos, de forma que será preciso elegir cuidadosamente el tipo de recorrido.
Un recorrido de un árbol binario requiere que cada nodo del árbol sea procesado (visitado) una vez y sólo una en una secuencia predeterminada. Existen dos enfoques generales para la secuencia de recorrido, profundidad y anchura.
En el recorrido en profundidad, el proceso exige un camino desde el raíz a través de un hijo, al descendiente más lejano del primer hijo antes de proseguir a un segundo hijo. En otras palabras, en el recorrido en profundidad, todos los descendientes de un hijo se procesan antes del siguiente hijo.
En el recorrido en anchura, el proceso se realiza horizontalmente desde el raíz a todos sus hijos, a continuación a los hijos de sus hijos y así sucesivamente hasta que todos los nodos han sido procesados. En otras palabras, en el recorrido en anchura, cada nivel se procesa totalmente antes de que comience el siguiente nivel.
El recorrido de un árbol supone visitar cada nodo sólo una vez.
Dado un árbol binario que consta de una raíz, un subárbol izquierdo y un subárbol derecho se pueden definir tres tipos de secuencia de recorrido en profundidad. Estos:
La designación tradicional de los recorridos utiliza un nombre para el nodo raíz (N), para el subárbolizquierdo (I) y para el subárbol derecho (D), según sea la estrategia a seguir, los recorridos se conocen como enorden(inorder),preorden(preorder)y postorden(postorder).
Preorden(nodo-izquierdo-derecho) (NID)
Enorden(izquierdo-nodo-derecho) (IND)
Postorden(izquierdo-derecho-nodo) (IDN)
3.3.2 Recorrido PREORDEN
El recorrido preorden(NID) conlleva los siguientes pasos, en los que el raíz va antes que los subárboles:
1. Recorrer el raíz (N).
2. Recorrer el subárbol izquierdo (I) en preorden.
3. Recorrer el subárbol derecho (D) en preorden.
Dado las características recursivas de los árboles, el algoritmo de recorrido tiene naturaleza recursiva. Primero, se procesa la raíz, a continuación el subárbol izquierdo y a continuación el subárbol derecho. Para procesar el subárbol izquierdo, se hace una llamada recursiva al procedimiento preorden
Y luego se hace lo mismo con el subárbol derecho. El algoritmo recursivo correspondiente para un árbolT es:
Si T no es vacío entonces
Inicio
Ver los datos en el r a i z/ de T
Preorden (subárbol izquierdo de la raíz de T)
Preorden (subárbol derecho del raíz de T)
fin
Regla
En el recorrido preorden, el raíz se procesa antes que los subárboles izquierdo y derecho.
Si utilizamos el recorrido preorden del árbol de la Figura 16.22 se visita primero la raíz (nodo A).A continuación se visita el subárbol izquierdo de A, que consta de los nodos B, D y E. Dado que elSubárbol es a su vez un árbol, se visitan los nodos utilizando el orden NID. Por consiguiente, se visita primero el nodo B, después D (izquierdo) y, por último, E (derecho)
A continuación se visita el subárbol derecho de A, que es un árbol que contiene los nodos c, F yG. De nuevo siguiendo el orden NID, se visita primero el nodo C, a continuación F (izquierdo) y, porÚltimo, G (derecho). En consecuencia el orden del recorrido preorden para el árbol de la Figura 16.22 es
A-B-D-E-C-F-G.
Un refinamiento del algoritmo es:
algoritmopreOrden (val rai7 <puntero nodos>)
Recorrer un arbol binario en secuencia nodo-izdo-dcho
Pre raiz es el nodo de entrada del árbol o subárbol
Post cada nodo se procesa en orden
1 si (raiz no es nulo)
1 procesar (raiz)
2 preOrden (raiz ->cubarbolTzdo)
3 preOrden (raiz ->subarbolDcho
2 return
La función preorden muestra el código fuente en C del algoritmo ya citado anteriormente. El tipo jde los datos es entero.
typedefintTipoElemento;
struct nodo
{TipoElemento datos;
struct nodo *hijo-izdo, *hijo-dcho;
} ;
typedefstructnodoNodo;
voidpreorden (Nodo *p)
{ if (P)
{ printf ("%d " , p ->ddtos) ;
PreOrden(p -> hijo-izdo);
PreOrden(p -> hijo-dcho);
}
}
Gráficas de las llamadas recursivas de preorden
El recorrido recursivo de un árbol se puede mostrar gráficamente por dos métodos distintos:
1.- paseopreordendel árbol;
2.- recorrido algorítmico.
Un medio gráfico para visualizar el recorrido de un árbol es imaginar que se está dando un «paseo» alrededor del árbol comenzando por la raíz y siguiendo el sentido contrario a las agujas del reloj, un nodo a continuación de otro sin pasar dos veces por el mismo nodo. El camino señalado por una líneacontinua que comienza en el nodo 1 (Fig. 16.2 1) muestra el recorrido preorden completo. En el caso dela Figura el recorrido es A H D E C F G.
El otro medio gráfico de mostrar el recorrido algorítmico recursivo es similar a las diferentes etapas del algoritmo. Así la primera llamada procesa la raíz del árbol A. A continuación se llama recursivamente a procesar subárbol izquierdo, procesa el nodo B. La tercera llamada procesa el nodo D, que es un subárbol formado por un único nodo. En ese punto, se llama en preorden, con un puntero nulo, que produce un retorno inmediato al subárbol U para procesar a su subárbol derecho. Debido a que el subárbol derecho de D es también nulo, se vuelve al nodo B de modo que va a procesar (visitar) su subárbol derecho, E. Después de procesar el nodo E, se hacen dos llamadas más, una con el punteroizquierdo null de E y otra con su puntero derecho null. Como el subárbol R ha sido totalmente procesado, se vuelve a la raíz del árbol y se procesa su subárbol derecho, C. Después de procesar C, llama para procesar su subárbol izquierdo F'. Se hacen dos llamadas con null, vuelve al nivel donde está el nodo cpara procesar su rama derecha G. Aún se realizan dos llamadas más, una al subárbol izquierdo nully otraal subárbol derecho. Entonces se retorna en el árbol, se concluye el recorrido del árbol.
3.3.3 Recorrido ENORDEN
El recorrido en orden (inorder) procesa primero el subárbol izquierdo, después el raíz y a continuación el subárbol derecho. El significado de in es que la raíz se procesa entre los subárboles. Si el árbol no está vacío, el método implica los siguientes pasos:
1. Recorrer el subárbol izquierdo (1) en inorden.
2. Visitar el nodo raíz (N).
3. Recorrer el subárbol derecho (I) en inorden.
El algoritmo correspondiente es:
Enorden(A)
si el arbol no estavacio entonces
Recorrer el subarbol izquierdo
Visitar el nodo raiz
Recorrer el subarbol derecho
inicio
fin
Un refinamiento del algoritmo es:
Algoritmoenorden (val raiz<puntero anodo>)
Recorrer un árbol binario en la secuencia izquierdo-nodo-derecho
pre raíz en el nodo de entrada de un árbol o subárbol
post cada nodo se ha de procesar en orden
1 si (raíz no es nulo)
1 enorden (raiz ->subarbol Izquierdo)
2 procesar (raiz)
3 enorden(raiz->subarbolDerecho)
2 retorno
finenorden
En el árbol de la Figura, los nodos se han numerado en el orden en que son visitados durante el recorrido enorden. El primer subárbol recorrido es el subárbol izquierdo del nodo raíz (árbol cuyo nodo contiene la letra 5. Este subárbol consta de los nodos 5, D y E y es a su vez otro árbol con el nodo B como raíz, por lo que siguiendo el orden IND, se visita primero D, a continuación B (nodo raíz) y, por último, E (derecha). Después de la visita a este subárbol izquierdo se visita el nodo raíz A y, por último, se visita el subárbol derecho que consta de los nodos C, F y G. A continuación, siguiendo el orden IND para el subárbol derecho, se visita primero F, después c (nodo raíz) y, por Último, G. Por consiguiente, el orden del recorrido inorden de la Figura 16.23 es D-B-E-A-F-C-G.
La siguiente función visita y escribe el contenido de los nodos de un árbol binario de acuerdo al recorrido EnOrden. La función tiene como parámetro un puntero al nodo raíz del árbol.
voidenorden (Nodo *p)
{ if (P)
{ enorden(p -> hijo-izqdo);
printf ("%d ",p -> datos) ;
enorden (p -> hijo-dcho);
/* recorrer subárbol izquierdo * /
/ * visitar la raíz * /
/* recorrer subárbol derecho * /
}
}
3.3.4 Recorrido POSTORDEN
El recorrido postorden(IDN) procesa el nodo raíz (post) después de que los subárboles izquierdo y derecho se han procesado. Se comienza situándose en la hoja más a la izquierda y se procesa. A continuación se procesa su subárbol derecho. Por último se procesa el nodo raíz. Las etapas de lalgoritmo son:
1. Recorrer el subárbol izquierdo (I) en postorden.
2. Recorrer el subárbol derecho (D) en postorden.
3. Visitar el nodo raíz (N).
El algoritmo recursivo para un árbol A es:
si A no estávacío entonces
inicio
Postorden (subarbol izquierdo delraíz de A)
Postorden( subarbolderecho del raíz de A)
Visitar la raíz de A
fin
El refinamiento del algoritmo es:
algoritmopostorden (val raiz<puntero a nodo>)
Recorrer un árbol binario en secuencia izquierda-derecha-nodo
preraíz es el nodo de entrada de un árbol a un subárbol
postcada nodo ha sido procesado en orden
1 Si (raíznoesnulo)
1 postOrden (raíz ->SubarbolIzdo)
2postOrden (raíz ->SubarbolDcho)
3procesar (raiz)
2 retorno
finpostorden
Si se utiliza el recorrido postorden del árbol de la Figura 16.24, se visita primero el subárbolIzquierdo A. Este subárbol consta de los nodos B , D y E y siguiendo el orden IDN, se visitará primero D(Izquierdo), luego E (derecho) y, por Último, B (nodo). A continuación, se visita el subárbol derecho Aque consta de los nodos C, F y G. Siguiendo el orden IDN para este árbol, se visita primero F (izquierdo),Después G (derecho) y, por Último, c (nodo). Finalmente se visita la raíz A (nodo). Así el orden del recorrido postorden del árbol de la Figura 16.24 es D-E-B-F-G-C-A.
La función postorden que implementa en C el código fuente del algoritmo correspondiente
voidpostorden (Nodo *p)
{if (P)
{ postorden (p -> hijo-izqdo);
postorden (p -> hijo-dcho);
printf ("%d ",p -> datos) ;
}
}
3.3.5 Árbol Binario de Búsqueda
Los árboles vistos hasta ahora no tienen un orden definido; sin embargo, los árboles binarios ordenados tienen sentido. Estos árboles se denominan árboles binarios de búsqueda, debido a que se pueden buscaren ellos un término utilizando un algoritmo de búsqueda binaria similar al empleado en arrays.
Un árbol binario de búsqueda es aquel que dado un nodo, todos los datos del subárbol izquierdo son menores que los datos de ese nodo, mientras que todos los datos del subárbol derecho son mayores que sus propios datos.
Creación de un árbol binario de búsqueda
Supongamos que se desea almacenar los números 8 3 1 20 10 5 4 en un árbol binario de búsqueda. Siguiendo la regla, dado un nodo en el árbol todos los datos a su izquierda deben ser menores que todos los datos del nodo actual, mientras que todos los datos a la derecha deben ser mayores que los datos. Inicialmente el árbol está vacío y se desea insertar el 8. La única elección es almacenar el 8 en el raíz A continuación viene el 3. Ya que 3 es menor que 8, el 3 debe ir en el subárbol izquierdo.
A continuación se ha de insertar 1 que es menor que 8 y que 3, por consiguiente irá a la izquierday debajo de 3.
El siguiente número es 20, mayor que 8, lo que implica debe ir a la derecha de 8.
Cada nuevo elemento se inserta como una hoja del árbol. Los restantes elementos se pueden situar fácilmente
Una propiedad de los árboles binarios de búsqueda es que no son únicos para los mismos datos.
Construir un árbol binario para almacenar los datos 12, 8, 7, 16 y 14.
Construir un árbol binario de búsqueda que corresponda a un recorrido enorden cuyos elementos son: 1, 3, 4, 5, 6, 7, 8, 9 y 10.
3.3.6 Implementación de un nodo de un árbol binario de búsqueda
Un árbol binario de búsqueda se puede utilizar cuando se necesita que la información se encuentrerápidamente. Estudiemos un ejemplo de árbol binario en el que cada nodo contiene información relativaa una persona. Cada nodo almacena un nombre de una persona y el número de matrícula en suuniversidad (dato entero).
Declaración de tipos
Nombre
Matrícula
Tipo de dato cadena ( string )
Tipo entero
structnodo {
intnummat;
char nombre [ 3 O ] ;
structnodo *izda, *dcha;
};
typedefstructnodoNodo;
3.3.7 Operaciones en árboles binarios de búsqueda
De lo expuesto se deduce que los árboles binarios tienen naturaleza recursiva y en consecuencia las operaciones sobre los árboles son recursivas, si bien siempre tenemos la opción de realizarlas de forma iterativa. Estas operaciones son:
Búsqueda de un nodo.
Inserción de un nodo.
Recorrido de un árbol.
Borrado de un nodo.
Búsqueda:
La búsqueda de un nodo comienza en el nodo raíz y sigue estos pasos:
1. La clave buscada se compara con la clave del nodo raíz.
2. Si las claves son iguales, la búsqueda se detiene.
3. Si la clave buscada es mayor que la clave raíz, la búsqueda se reanuda en el subárbol derecha. Si la clave buscada es menor que la clave raíz, la búsqueda se reanuda con el subárbol izquierdo.
Buscar una información específica
Si se desea encontrar un nodo en el árbol que contenga la información sobre una persona específica. La función buscar tiene dos parámetros, un puntero al árbol y un número de matrícula para la persona requerida. Como resultado, la función devuelve un puntero al nodo en el que se almacena la información sobre esa persona; en el caso de que la información sobre la persona no se encuentra se devuelve el valor O. El algoritmo de búsqueda es el siguiente:
1. Comprobar si el árbol está vacío.
En caso afirmativo se devuelve O.
Si la raíz contiene la persona, la tarea es fácil: el resultado es, simplemente, un puntero a la raíz.
2. Si el árbol no está vacío, el subárbol específico depende de que el número de matrícula requerido es más pequeño o mayor que el número de matrícula del nodo raíz.
3. La función de búsqueda se consigue llamando recursivamente a la función buscar con un puntero al subárbol izquierdo o derecho como parámetro.
El código C de la función buscares:
Nodo* buscar (Nodo* p, int buscado)
{if ( ! p )
else if (buscado == p ->nummdt)
else if (buscado< p ->nummdt)
else /
return O;
return p;
return buscar (p ->izda, buscado);
return buscar (p ->dcha, buscado);
}
3.3.8 Inserción de un nodo
Una característica fundamental que debe poseer el algoritmo de inserción es que el árbol resultante de una inserción en un árbol de búsqueda ha de ser también de búsqueda. En esencia, el algoritmo deInserción se apoya en la localización de un elemento, de modo que si se encuentra el elemento (clave) buscado, no es necesario hacer nada; en caso contrario, se inserta el nuevo elemento justo en el lugar donde ha acabado la búsqueda (es decir, en el lugar donde habría estado en el caso de existir).
Por ejemplo, considérese el caso de añadir el nodo 8 al árbol de la Figura 16.26. Se comienza el recorrido en el nodo raíz 25; la posición 8 debe estar en el subárbol izquierdo de 25 (8 < 25). En el nodo10, la posición de 8 debe estar en el subárbol izquierdo de 10, que está actualmente vacío. El nodo 8 se introduce como un hijo izquierdo del nodo 10.
Ejemplo
Insertar un elemento con clave 80 en el árbol Binario de Búsqueda siguiente:
A continuación insertar un elemento con clave 36 en el árbol binario de búsqueda resultante.
Solución
3.3.9 Función Insertar ( )
La función insertar que pone nuevos nodos es sencilla. Se deben declarar tres argumentos: un puntero al raíz del árbol, el nuevo nombre y número de matrícula de la persona. La función creará un nuev onodo para la nueva persona y lo inserta en el lugar correcto en el árbol de modo que el árbol permanezca como binario de búsqueda.
La operación de inserción de un nodo es una extensión de la operación de búsqueda. Los pasos aseguir son:
1. Asignar memoria para una nueva estructura nodo.
2. Buscar en el árbol para encontrar la posición de inserción del nuevo nodo, que se colocará comonodo hoja.
3. Enlazar el nuevo nodo al árbol.
El código C de la función:
void insertar (Nodo** raiz, intnuevomat, char *nuevo-nombre)
{
if ( ! (*raiz))
else if (nuevomat i (*raiz) ->nummat)
else
*raiz = CrearNodo(nuevo-mat, nuevo-nombre) ;
insertar (&((*raiz) ->izda), nuevomat, nuevo-nombre);
insertar ( & ( (*raiz) ->dcha), nuevomat, nuevo-nombre);
}
Si el árbol está vacío, es fácil insertar la entrada en el lugar correcto. El nuevo nodo es la raíz del árbol y el puntero raiz se pone apuntando a ese nodo. El parámetro raiz debe ser un parámetro referencia ya que debe ser leído y actualizado, por esa razón se declara puntero a puntero (Nodo * *) . Si el árbol no está vacío, se debe elegir entre insertar el nuevo nodo en el subárbol izquierdo o derecho, dependiendo de que el número de matrícula de 12 nueva persona sea más pequeño o mayor que el número de matrícula en la raíz del árbol.
3.3.9 Eliminación
El árbol resultante es: la operación de eliminación de un nodo es también una extensión de la operación de búsqueda, si bien más compleja que la inserción debido a que el nodo a suprimir puede ser cualquiera y la operación de supresión debe mantener la estructura de árbol binario de búsqueda después de la eliminación de datos.
Los pasos a seguir son:
1. Buscar en el árbol para encontrar la posición de nodo a eliminar.
2. Reajustar los punteros de sus antecesores si el nodo a suprimir tiene menos de 2 hijos, o subir a
la posición que éste ocupa el nodo más próximo en clave (inmediatamente superior o
Inmediatamente inferior) con objeto de mantener la estructura de árbol binario.
Ejemplo:
Suprimir el elemento de clave 36 del siguiente árbol binario de búsqueda:
El árbol resultante es:
Borrar el elemento de clave 60 del siguiente árbol:
Se reemplaza 60 bien con el elemento mayor (5.5) en su subárbol izquierdo o el elemento máspequeño (70) en su subárbol derecho. Si se opta por reemplazar con el elemento mayor del subárbolizquierdo. Se mueve el 5.5 al raíz del subárbol y se reajusta el árbol.
3.4 IMPLEMENTACIÓN USANDO LISTA
Una manera impórtame y útil de representar árboles consiste en formar una lista de los hijos de cada nodo. Las listas se pueden representar con cualquiera de los métodos sugeridos en el capítulo 2, pero como el número de hijos que cada nodo puede tener es variable, la representación por medio de listas enlazadas es a menudo más apropiada. La figura 3.12 sugiere cómo se podrá representar el árbol de la figura 3.10(a).
Hay un arreglo de celdas de encabezamiento indizadas por nodos, los cuales se supone que están numerados del I al 10. Cada encabezamiento apunta a una lista enlazada de «elementos» que son nodos del árbol. Los elementos de la lisia encabezada por encabezamiento[i] son los hijos del nodo i; por ejemplo, 9 y 10 son los hijos de 3.
Fig. 3.12. Representación de un árbol por listas enlazadas
Primero se desarrollarán las estructuras de datos necesarias en función de un tipo de dalos abstracto LISTA (de nodos), y luego se dará una realización particular para las listas y se verá cómo las abstracciones compaginan entre si. Después se mostraran algunas simplificaciones posibles. Se empieza con las siguientes declaraciones de tipo:
Se supone que la raíz de cada árbol está almacenada explícitamente en el campo raiz, y que se usa O para representar el nodo nulo. La figura 3.13 muestra el código para la operación HIJO-MAS-IZQ. Como ejercicio, sería útil escribir el código para las restantes operaciones.
Una implantación particular para las listas, en la cual tanto LISTA como posición sean enteros, empleados como cursores a un arreglo espacio_celdas de registros:
Se asumirá que las listas de hijos no tienen celdas de encabezamiento. A.encabezamiento[n] apunta directamente a la primera celda de la lista, como se sugiere en la figura 3.13. La figura 3.14 muestra este cambio en la función HIJO_MAS_IZQ
Representación hijo mis a la izquierda — hermano derecho
La estructura de datos descrita antes no es adecuada para crear árboles grandes a partir de árboles más chicos por medio de los operadores CREAi- La razón es que, a pesar de que iodos los árboles comparten espacio-celdas para crear las listas ligadas de hijos, cada uno tiene su arreglo propio de encabezamientos correspondientes a sus nodos. Por ejemplo, si se deseara obtener CREA2(v, A1, A2), se tendría que copiar A1 y A2 en un tercer árbol y agregar un nuevo nodo con etiqueta v y dos hijos: las raíces de A1 y A2.
Para construir árboles a partir de otros menores se puede reemplazar el arreglo de encabezamientos por un arreglo espacio_nodos que contenga registros con dos campos etiqueta y encabezamiento. Este arreglo contendrá los encabezamientos de la totalidad de nodos de todos los árboles:
Otras estructuras de listas enlazadas para árboles: la figura 3.16 muestra un árbol A-B-C-D, y la estructura de datos correspondiente, en la cual los nodos con etiquetas A, B, C, y D se han colocado de manera arbitraría en las posiciones 10, 5, 11 y 2 de espacio-nodos. También se ha hecho una elección arbitraria de las celdas de espacio-celdas utilizadas para las listas de hijos.
Fig. 3.17. Otras estructuras de listas enlazadas para árboles
La estructura de la figura 3.17 es adecuada para combinar árboles por medio de operaciones CREAi. Sin embargo, esta estructura se puede simplificar de modo significativo. Primero, se observa que las cadenas de apuntadores sigde espacio_celdasson en realidad apuntadores a hermanos derechos. Usando estos apuntadores, se pueden obtener los hijos más a la izquierda como sigue. Supóngase que espacio_celdas[i].nodo = n. Entonces, espacio_nodos[n].encabezamiento indica la celda ocupada por el hijo más a la izquierda de n en espacio_celdas, en el sentido de que el campo nodo de esa celda es el nombre de tal nodo en espacio_nodos.Se pueden simplificar las cosas si se identifica un nodo no por su índice en espacio_nodos. sino por el índice de la celda de espacio_celdasque lo representa como hijo. Entonces los apuntadores sigde espacio_celdas apuntarán en realidad a hermanos derechos, y la información contenida en el arreglo espacio_nodos se podrá guardar introduciendo un campo hijo_más_izqen espacio_celdas. El tipo de datos ÁRBOL se convertirá en un entero empleado como cursor a espacio_celdas para indicar la raíz del árbol. Se declara espacio_celdaspara tener la siguiente estructura:
El árbol de la figura 3.17 se puede representar como una nueva estructura de datos en la figura 3.19. Para los nodos se han utilizado los mismos los índices arbitrarios de la figura 3.17
En la representación hijo más a la izquierda-hermano derecho, todas las operaciones son fáciles de realizar, excepto PADRE. Esta requiere de una búsqueda en todo espacio_celdas. Si es necesario realizar la operación PADRE eficientemente, se puede agregar a espacio_celdas un cuarto campo que indique al padre de un nodo directamente.
Como ejemplo de una operación con árboles escrita para utilizar una estructura hijo más a la izquierda-hermano derecho, como la de la figura 3.16, se da la función CREA2 en la figura 3.20. Se supone que las celdas no utilizadas están enlazadas en una lista de espacio disponible, encabezada por disp, y que este enlace utiliza los campos hermano derecho. La figura 3.21 muestra los apuntadores antiguos (con líneas de trazo continuo) y los nuevos (con líneas punteadas).
Fig. 3.21. Cambios de apuntadores producidos por CREA2
Como alternativa, se puede usar menos espacio, pero más tiempo, si se coloca en el campo hermano derecho del hijo más a la derecha un apuntador al padre, en lugar del apuntador nulo que, de lo contrario, estaría ahí. Para evitar confusiones, se necesitaría en cada celda un bit que indicase si el campo hermano derecho tiene un apuntador al hermano derecho o al padre. Así, dado un nodo, se encontraría su padre siguiendo apuntadores hermano derecho hasta encontrar uno que fuera apuntador al padre. Como todos los hermanos tienen el mismo padre, se encontraría el camino al padre del nodo del que se partió. El tiempo necesario para encontrar el padre de un nodo en esta representación depende del número de hermanos que tenga el nodo.
3.5 ARBOLES AVL
Un árbol AVL (llamado así por las iniciales de sus inventores: Adelson-Velskii y Landis) es un árbol binario de búsqueda en el que para cada nodo, las alturas de sus subárboles izquierdo y derecho no difieren en más de 1. No se trata de árboles perfectamente equilibrados, pero sí son lo suficientemente equilibrados como para que su comportamiento sea lo bastante bueno como para usarlos.
El algoritmo para mantener un árbol AVL equilibrado se basa en reequilibrados locales, de modo que no es necesario explorar todo el árbol después de cada inserción o borrado.
— Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.
— Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.
AVL es la mejor estructura para memoria principal, pero es ineficiente si se utiliza para almacenamiento secundario. Esto se debe a la cantidad de accesos necesarios para efectuar las rotaciones. Otro problema es quese requieren tantos accesos como niveles se recorran en el árbol para efectuar la búsqueda.
3.5.1 Características (Factor Balanceo)
Un AVL es un ABB
La diferencia entre las alturas de los subárboles derecho e izquierdo no debe excederse en más de 1.
Cada nodo tiene asignado un peso de acuerdo a las alturas de sus subárboles
Un nodo tiene un peso de 1 si su subárbol derecho es más alto, -1 si su subárbol izquierdo es más alto y 0 si las alturas son las mismas.
La inserción y eliminación en AVLs es la misma que en los ABBs
Es fácil ver desbalanceado si y solo si el nodo recién insertado es un descendiente izquierdo de un nodo q tiene de manera previa balance de 1, o si es un hijo derecho descendiente de un nodo que tiene de Manera previa balance -1 .
3.5.2 Conversiones arboles avl
Cada nodo, además de la información que se pretende almacenar, debe tener los dos punteros a los árboles derecho e izquierdo, igual que los ABB, y además un miembro nuevo: el factor de equilibrio. El factor de equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo:
FE = altura subárbol derecho - altura subárbol izquierdo;
Por definición, para un árbol AVL, este valor debe ser -1, 0 ó 1.
Un heap o montículo es un árbol binario completo, y además parcialmente ordenado. Ya hemos visto el concepto de árbol completo. Un árbol parcialmente ordenado es aquél que tiene todas y cada una de sus ramas, consideradas como listas, totalmente ordenadas, ya sea de forma creciente o decreciente. En relación al heap, se exige una ordenación decreciente, lo que puede dar lugar a una definición más natural de heap: un heap es un árbol binario completo, tal que el valor de su raíz es mayor o igual que las raices de sus hijos, siendo también heaps ambos hijos. A este concepto le añadiremos ciertas operaciones, lo cual desemboca en el TAD Heap. La siguiente figura ilustra un ejemplo de heap, así como casos de árboles que no lo son: por no ser parcialmente ordenados, o por no ser completos.
Al igual que para el árbol binario de búsqueda, las operaciones básicas son las mismas que para el árbol binario simple, y al igual que en aquél, el generador Arbol_binario está oculto al usuario.Necesitamos además un predicado que nos diga cuando un árbol es un heap:
Es_Heap: ArbolB->Lógico
Ecuaciones
a : ArbolB
Es_Heap(a) == Es_Completo(a) and Es_Parc_Orden(a)
Ya hemos especificado formalmente cuando un árbol es completo. Nuestra definición deparcialmente ordenado se completa con la siguiente especificación:
Es_Parc_Orden :ArbolB Lógico
ecuaciones
r : Elemento i, d : ArbolB
Es_Parc_Orden(Crear) == V
Es_Parc_Orden(Arbol_binario(r, i, d)) == (Es_Vacio(i) or r >= Raiz(i)) and
(Es_Vacio(d) or r >= Raiz(d)) and
Es_Parc_Orden(i) and
Es_Parc_Orden(d)
Vamos a ver ahora unas cuantas operaciones interesantes. La primera de ellas inserta unelemento en un árbol completo, y hace que el resultado siga siendo un árbol completo:
Ins_Completo: Elemento × ArbolB ->ArbolB
ecuaciones
e, r : Elemento i, d : ArbolB
Ins_Completo(e, Crear) == Arbol_binario(e, Crear, Crear)
Ins_Completo(e, Arbol_binario(r, i, d)) ==
SI ((Altura(i) > Altura(d)) and (notEs_Lleno(i))) or
((Altura(i) = Altura(d)) and Es_Lleno(d)) ENTONCES
Arbol_binario(r, Ins_Completo(e, i), d)
SI NO
Arbol_binario(r, i, Ins_Completo(e, d))
de manera que se verifica:
teoremaa : ArbolB
Es_Completo(A_Completo(a)) == V
Una vez que hemos convertido cualquier árbol en completo, ya sólo nos queda convertirlo en heap, que es lo que hace la operación Completo_A_Heap, que parte del árbol completo, y aplica recursivamente Arbol_heap a cada raíz, y a sus dos hijos ya convertidos es heap:
Completo_A_Heap: ArbolB ->ArbolB
Arbol_heap: Elemento × ArbolB × ArbolB ->ArbolB
precondicionesa:ArbolB
Completo_A_Heap(a) :Es_Completo(a)
ecuacionesr : Elemento i, d : ArbolB
Completo_A_Heap(Crear) == Crear
Completo_A_Heap(Arbol_binario(r, i, d)) ==
Arbol_heap(r, Completo_A_Heap(i), Completo_A_Heap(d))
Arbol_heap(r, i, d) ==
SI Es_Vacio(i)
Arbol_binario(r, Crear, Crear)
SI NO SI Es_Vacio(d) ENTONCES
SI r >Raiz(i) ENTONCES
Arbol_binario(r, i, Crear)
SI NO
Arbol_binario(Raiz(i), Arbol_binario(r, Crear, Crear), Crear)
SI NO SI (r $ Raiz(i)) and (r $ Raiz(d)) ENTONCES
Arbol_binario(r, i, d)
SI NO SI (Raiz(i) $ r) and (Raiz(i) $ Raiz(d)) ENTONCES
Arbol_binario(Raiz(i), Arbol_heap(r, Hijo_izq(i), Hijo_dch(i)), d)
SI NO
Arbol_binario(Raiz(d), i, Arbol_heap(r, Hijo_izq(d), Hijo_dch(d)))
teoremasa, i, d : ArbolB r : Elemento
Completo(a) 6 Es_Heap(Completo_A_Heap(a))
Es_Completo(Arbol_binario(r, i, d)) and
Es_Heap(i) and Es_Heap(d) 6 Es_Heap(Arbol_heap(r, i, d))
No obstante, podemos simplificar estas tareas hasta cierto punto, con una sola operación que inserte un elemento en un heap, de manera similar a como lo hace el Insertar de los árboles binarios de búsqueda.
3.5.3 Rotaciones arboles avl
Rotaciones simples de nodos
Los reequilibrados se realizan mediante rotaciones, en el siguiente punto veremos cada caso, ahora vamos a ver las cuatro posibles rotaciones que podemos aplicar.
3.5.4 Simple rotación a la izquierda
Rotacion simple a la izquierda
§ El nodo apuntado por Q se convierte en nodo Padre
§ El nodo apuntado por P se convierte en hijo por la derecha.
Y los demás nodos siguen igual
3.5.5 Simple rotación a la derecha
Esta rotación se usará cuando el subárbol izquierdo de un nodo sea 2 unidades más alto que el derecho, es decir, cuando su FE sea de -2. Y además, la raíz del subárbol izquierdo tenga una FE de -1, es decir, que esté cargado a la izquierda.
El nodo apuntado por Q se convierte en nodo Padre
El nodo apuntado por P se convierte en hijo por la izquierda.
Y los demás nodos siguen igual
Código
void RSD(Arbol *a, pNodo nodo)//Rotación simple a derechas
{pNodo Padre = nodo->padre;
pNodo P = nodo;
pNodo Q = P->izquierdo;
pNodo B = Q->derecho;
if(Padre)
if(Padre->derecho == P) Padre->derecho = Q;
else Padre->izquierdo = Q;
else *a = Q;
/* Reconstruir árbol: */
P->izquierdo = B;
Q->derecho = P;
/* Reasignar padres: */
P->padre = Q;
if(B) B->padre = P;
Q->padre = Padre;
/* Ajustar valores de FE: */
P->FE = 0;
Q->FE = 0;
}
3.5.6 Doble rotación a la izquierda
Se separan los árboles y se usan 3 punteros:
El nodo apuntado por R se convierte en nodo Padre de ese árbol
El nodo apuntado por Q se convierte en hijo por la derecha.
Y los demás nodos siguen igual
Ahora el nodo apuntado por Q pasa a ser padre y el nodo apuntado por P pasa a ser hijo por la izquierda.
3.5.7 Doble rotación a la derecha
Esta rotación se usará cuando el subárbol izquierdo de un nodo sea 2 unidades más alto que el derecho, es decir, cuando su FE sea de -2. Y además, la raíz del subárbol izquierdo tenga una FE de 1, es decir, que esté cargado a la derecha.
Pasos
Se separan los arboles y se usan 3 punteros:
El nodo apuntado por R se convierte en nodo Padre de ese arbol
El nodo apuntado por Q se convierte en hijo por la izquierda.
Y los demás nodos siguen igual
Ahora el nodo apuntado por Q pasa a ser padre y el nodo apuntado por P pasa a ser hijo por la derecha.
Código
void RDD(Arbol *raíz, Arbol nodo)/* Rotación doble a derechas */
{pNodo Padre = nodo->padre;
pNodo P = nodo;
pNodo Q = P->izquierdo;
pNodo R = Q->derecho;
pNodo B = R->izquierdo;
pNodo C = R->derecho;
if(Padre)
if(Padre->derecho == nodo) Padre->derecho = R;
else Padre->izquierdo = R;
else *raíz = R;
/* Reconstruir árbol: */
Q->derecho = B;
P->izquierdo = C;
R->izquierdo = Q;
R->derecho = P;
/* Reasignar padres: */
R->padre = Padre;
P->padre = Q->padre = R;
if(B) B->padre = Q;
if(C) C->padre = P;
/* Ajustar valores de FE: */
switch(R->FE) {
case -1: Q->FE = 0; P->FE = 1; break;
case 0: Q->FE = 0; P->FE = 0; break;
case 1: Q->FE = -1; P->FE = 0; break;
}
R->FE = 0;
}
3.6 CONCEPTO DE ARBOLES B+
El Árbol B es un TDA de búsqueda equilibrado, diseñado para ser usado con grandes conjuntos de datos en almacenamiento secundario.Generalmente se considera a los Arboles B como el mejor método para implementar al TDA dinámico en una unidad de disco.A diferencia de los Arboles Binarios, el Árbol B accede al disco mediante bloques de datos, es decir, agrupa los datos en paquetes para su lectura o escritura de así serlo.Esta propuesta reduce bastante el número de accesos al dispositivo secundario, optimizando así el rendimiento de nuestro sistema informático.
Características del Árbol B
Se dice que un árbol es B-Tree de orden n si: Cada página tiene a lo más 2n llaves.
Un árbol B de orden n es aquél en que:
— Los elementos de un nodo están ordenados linealmente.
— Los elementos están organizados de tal forma que se cumple la regla de la búsqueda: a la izquierda menores, a la derecha mayores.
3.6.1 Búsqueda de Arboles B+
En este caso, la búsqueda no debe detenerse cuando se encuentre la clave en la página raíz o en una página interior, si no que debe proseguir en la página apuntada por la rama derecha de dicha clave.
3.6.2 Inserción de Arboles B+
Su diferencia con el proceso de inserción en árboles B consiste en que cuando se inserta una nueva clave en una página llena, ésta se divide también en otras dos, pero ahora la primera contendrá con m/2 claves y la segunda 1+m/2, y lo que subirá a la página antecesora será una copia de la clave central.
Ø Buscar el nodo hoja en donde se debería agregar el elemento.
Ø Si hay espacio disponible en el nodo, agregar el elemento y terminar.
Ø Si el nodo hoja NO tiene capacidad de almacenar el elemento, se deberá crear un nuevo nodo al mismo nivel de la hoja y distribuir a los 2n+1 elementos de la siguiente forma:
§ El nuevo nodo recibe a los ‘n’ elementos más grandes.
§ El nodo existente se queda con los ‘n’ elementos más pequeños.
§ El elemento medio se insertará en el nodo padre siguiendo la misma lógica de inserción. En caso de no haber nodo padre, se creará un nuevo nodo que pasará a ser la nueva raíz.
3.6.3 Borrador en un Árbol B +
La operación de borrado debe considerar:
Si al eliminar la clave (siempre en una hoja) el número de claves es mayor o igual a m/2 el proceso ha terminado. Las claves de las páginas raíz o internas no se modifican aunque sean una copia de la eliminada, pues siguen constituyendo un separador válido entre las claves de las páginas descendientes.
Si al eliminar la clave el número de ellas en la página es menor que m/2 será necesaria una fusión y redistribución de las mismas tanto en las páginas hojas como en el índice
Buscar el elemento a borrar.
Si el elemento a borrar está en un nodo hoja, se borra y termina el proceso.
Si el elemento a borrar no se encuentra en una hoja, al igual que en un ABB, se buscará al sustituto más apropiado.
El sustituto será:
El último elemento de la hoja más derecha del subárbol izquierdo del nodo actual (el mayor de los menores).
El primer elemento de la hoja más izquierda del subárbol derecho del nodo actual (el menor de los mayores).
