La vida es breve; el arte, largo; la ocasión, fugaz; la experiencia, engañosa; el juicio, difícil. ( Hipócrates - Médico griego, considerado el padre de la medicina.)
Publicado el Martes 10 de enero de 2006 a las 02:51:26 por ktommy
Lecturas
Árboles
1 Conceptos básicos
Los árboles son una de las estructuras de datos no lineales más utilizada. Sirve para representar estructuras de información jerárquicas y direcciones o etiquetas de una manera organizada.
Dentro de la ciencia de la computación, los árboles tienen muchas aplicaciones como por ejemplo:
· organizar tablas de símbolos en compiladores
· representar tablas de decisión
· asignar bloques de memoria de tamaño variable
· ordenar
· buscar
· solucionar juegos
· probar teoremas
Como objetos matemáticos los árboles también han sido estudiados ampliamente.
Los árboles permiten representar situaciones de la vida diaria como son:
· organización de una empresa
· árbol genealógico de una persona
· organización de torneos deportivos
Definición: Un árbol es un conjunto finito T de uno o más nodos tal que:
a) Existe un nodo especial llamado la raíz de árbol
b) Los nodos restantes están particionados en m > 0 conjuntos disjuntos T1,...,Tm y cada uno de estos conjuntos es a su vez un árbol. Los árboles T1,...,Tm son llamados subárboles de la raíz
Cualquier nodo es la raíz de un subárbol que consiste de él y los nodos debajo de él. Esto se deriva de la definición recursiva de árbol presentada.
Un árbol puede representarse gráficamente de muchas formas. Algunas de ellas son por medio de:
· conjuntos anidados:
· paréntesis anidados.
(1(2(4(9,10,11),5),3(6(12),7,8)))
· indentación
· grafos
La forma más común de representar a los árboles es por medio de un grafo con la raíz hacia arriba:
Cada vértice o nodo del árbol puede tener un nombre y puede tener una información asociada; un arco es una conexión entre dos vértices.
Un camino en un árbol es una lista de vértices diferentes en los que vértices sucesivos están conectados por arcos en el árbol. Una propiedad que define a los árboles es que existe exactamente un camino entre la raíz y cada uno de los otros nodos en el árbol.
La longitud de un camino es el número de nodos del camino menos uno. Por tanto, hay un camino de longitud cero de cualquier nodo a si mismo.
Se dice que un nodo Y está abajo de un nodo X, si X está en el camino de Y a la raíz. Además, cada nodo, excepto la raíz, tiene exactamente un nodo arriba de él, que es llamado su padre; los nodos que están exactamente abajo de él son llamados sus hijos.
El número de hijos que cuelgan de un nodo es llamado el grado del nodo. El grado de un árbol es el grado máximo de los nodos del árbol. Un nodo de grado cero es llamado hoja, es decir, no tiene hijos.
Ejemplo:
Considere el siguiente árbol:
El camino del nodo A al nodo P es (A, B, D, J, P), cuya longitud de camino es 4. E es el padre de K y L.
Los hijos de G son M, N y O.
Los nodos de grado 0 son: I, P, K, L, F, M, N, O, P y H es decir son las hojas del árbol.
El único nodo de grado 1 es J.
Los nodos de grado 2 son A, B, D y E.
Los nodos de grado 3 son C y G.
No existen nodos de mayor grado, por tanto, el grado del árbol es 3.
Los nodos de un árbol pueden dividirse en niveles; el nivel de un nodo es el número de nodos en el camino de él a la raíz. La altura de un árbol es el nivel máximo de todos los nodos en el árbol, es decir, la distancia máxima de la raíz a cualquier nodo.
A veces la forma en la cual los hijos de cada nodo están ordenados es importante. Un árbol ordenado es aquel en el cual el orden de los hijos de cada nodo está especificado.
Un conjunto de árboles es llamado un bosque. Existe una pequeña diferencia entre un árbol y un bosque; si se elimina la raíz de un árbol se obtiene un bosque, y, recíprocamente, si se añade un nodo a un bosque se obtiene un árbol.
¿Qué es un árbol de grado 0?
¿Cómo se representa un árbol de grado 1?
En muchas ocasiones los árboles se estudian por su grado, así iniciaremos estudiando los árboles binarios.
2 Árboles binarios
Los árboles binarios son el caso particular más simple. Son usados para representar ciertos tipos de expresiones algebraicas, algoritmos, búsquedas y ordenamientos.
Definición: Un conjunto T de elementos (nodos) es un árbol binario si:
1. T es vacío, o
2. T está particionado en 3 conjuntos disjuntos
a) un solo elemento R, llamado la raíz
b) 2 conjuntos que son árboles binarios, llamados los subárboles izquierdo y derecho de R
de esta forma
T es un árbol binario si
1. T no tiene nodos, o
2. T es de la forma:
donde n es un nodo y TI y TD son árboles binarios.
2.1 Representación ligada de árboles binarios
La representación más usada es la ligada o dinámica, donde cada nodo o celda tiene la siguiente forma:
Un nodo de un árbol puede representarse como:
clase nodoArbol
{
//datos miembro
Objeto info
nodoArbol hijoIzq
nodoArbol hijoDer
//funciones miembro
...
}
Y un árbol como:
clase arbolBinario
{
//datos miembro
nodoArbol raíz
//funciones miembro
. . .
}
2.2 Recorrido en árboles binarios
Una vez construido un árbol binario surge la necesidad de recorrerlo, es decir una manera sistemática de visitar cada nodo del árbol. La forma en la cual una lista lineal se recorre es trivial (del primero al último, o viceversa). Sin embargo, para recorrer un árbol, esta forma natural no puede aplicarse.
Para recorrer un árbol, existen varias formas de lograrlo, las 3 más comunes son preorden, inorden y postorden. Estos métodos difieren en el orden en el cual los nodos son visitados. Siguiendo la costumbre de empezar a visitar antes lo que se encuentra a la izquierda que lo de la derecha, se tienen 3 posibilidades de visitar a la raíz (antes, en medio o después).
Definición: Para recorrer un árbol binario no vacío T en preorden o previo:
1. visitar la raíz
2. recorrer recursivamente el subárbol izquierdo
3. recorrer recursivamente el subárbol derecho
Definición: Para recorrer un árbol binario no vacío T en inorden o simétrico:
1. recorrer recursivamente el subárbol izquierdo
2. visitar la raíz
3. recorrer recursivamente el subárbol derecho
Definición: Para recorrer un árbol binario no vacio T en postorden o posterior:
1. recorrer recursivamente el subárbol izquierdo
2. recorrer recursivamente el subárbol derecho
3. visitar la raíz
A partir de las definiciones anteriores, los métodos usando una representación dinámica son los siguientes:
void previo (nodoArbol T)
comienza
si T nil entonces
comienza
visita (T.info)
previo (T.hijoIzq)
previo (T.hijoDer)
termina
termina
void simétrico (nodoArbol T)
comienza
si T nil entonces
comienza
simétrico (T.hijoIzq)
visita (T.info)
simétrico (T.hijoDer)
termina
termina
void posterior (nodoArbol T)
comienza
si T nil entonces
comienza
posterior (T.hijoIzq)
posterior (T.hijoDer)
visita (T.info)
termina
termina
el resultado que se obtiene al recorrer el árbol en
Aunque la recursividad resulta natural en los métodos anteriores, es posible implementarlos por medio de una pila. A continuación se presenta un método para recorrer un árbol en preorden:
void preorden ()
comienza
p ß nueva Pila ()
si raiz nil entonces
comienza
p.push(raiz)
mientras ¬p.vacía ()
comienza
t ß p.valTope ()
p.pop()
visita(t)
si t.hijoDer nil entonces
p.push (t.hijoDer)
si T.hijoIzq nil entonces
p.push (t.hijoIzq)
termina
termina
termina
Otra forma de común de recorrer un árbol es por niveles, donde el algoritmo utiliza una cola. Para el árbol anterior el orden en que se visitan los nodos por niveles es:
Definición: Dado un conjunto de nodos (con un campo asignado como llave de búsqueda) T es un árbol binario de búsqueda si:
[titulo]1. T es vacío, o[/titulo]
2. T es de la forma y
a) la llave de búsqueda de n es mayor que todas las llaves de búsqueda de TI
b) la llave de búsqueda de n es menor que todas las llaves de búsqueda de TD
c) TI y TD son árboles binarios de búsqueda
Buscar:
Una ventaja de los árboles binarios de búsqueda es que el algoritmo de búsqueda surge de una manera natural. Si x es la llave de la raíz de un árbol binario de búsqueda y se está buscando a x, se ha terminado la búsqueda; esto es cierto suponiendo que las llaves de búsqueda son únicas. Si se busca una llave menor que x, entonces debe encontrarse en el subárbol izquierdo. Similarmente, si se busca una llave mayor que x, debe buscarse en el subárbol derecho.
Así, puede procederse recursivamente hasta encontrar la llave buscada. El siguiente algoritmo de búsqueda supone que no existen llaves duplicadas y regresa una referencia al nodo donde se encuentra la llave de búsqueda o el valor de nil si la llave no se encuentra en el árbol.
Esto es semejante a realizar una búsqueda binaria.
nodoArbol busca (nodoArbol A, Objeto x)
comienza
si A = nil o A.info.igual (x) entonces
regresa A
otro
si x.menor (A.info) entonces
regresa busca (A.ligader, x)
otro
regresa busca (A.ligaizq, x)
termina
Si se busca la llave 7 en el árbol se compara 7 con 10 y se desciende por la izquierda; se compara 7 con 8 y se desciende por la izquierda; al comparar 7 con 5 se desciende por la derecha y se encuentra la llave.
Insertar:
La inserción en un árbol binario de búsqueda es similar a la búsqueda. Suponga que se desea insertar una nueva llave con valor x, lo primero que debe hacerse es una búsqueda, si x se encuentra en el árbol no se requiere insertarla de nuevo (si se desea que las llaves del árbol sean únicas); en otro caso la búsqueda termina no exitosamente en una hoja o en un nodo con un solo subárbol; y así un nuevo nodo que contenga la llave x debe ser insertado debajo de esa hoja, como hijo derecho o hijo izquierdo, dependiendo del valor de x.
Siguiendo el esquema anterior, se podría modificar el algoritmo de búsqueda anterior, para que regrese también la hoja donde termina la búsqueda, es decir la raíz de donde se debe insertar el nuevo nodo. A continuación se presenta un algoritmo de búsqueda no recursivo.
nodoArbol localiza (Objeto x, nodoArbol padre)
comienza
nodo ß raiz
padre ß nil
mientras nodo nil & nodo.info x
comienza
padre ß nodo
si x < nodo.info entonces
nodo ß nodo.ligaIzq
otro
nodo ß nodo.ligaDer
termina
regresa nodo
termina
El algoritmo para insertar una llave en un árbol binario de búsqueda que se presenta utiliza el procedimiento anterior:
void inserta (Objeto x)
// No se permiten elementos repetidos
comienza
nodo ß localiza (x, padre)
si nodo nil
error (“La llave se encuentra”)
otro
comienza
nuevoNodo ß nuevo nodoArbol (x, nil, nil)
si padre.info > x entonces
padre.ligaizq ß nuevoNodo
otro
padre.ligader ß nuevoNodo
termina
termina
Borrar:
Por lo general, borrar siempre resulta más complicado. Lo primero que debe hacerse para borrar un nodo de un árbol binario de búsqueda es buscarlo. Si la búsqueda no fue exitosa, no hay nada que hacer; sin embargo, si existe un nodo x con la llave de búsqueda que se desea borrar, con padre P, entonces ese nodo puede:
a) ser una hoja
b) tener un único hijo
c) tener dos hijos
A continuación se presenta cada uno de éstos casos para su estudio.
a) El nodo a eliminar es una hoja
Este caso es el más sencillo, en el cual lo único que hay que hacer, es que la liga que lo referencia debería ser nil.
Si se hubiera eliminado el nodo con llave de búsqueda 4 del árbol original entonces el árbol debería quedar como:
Para eliminar una hoja
nodo ß localiza (x, padre)
si nodo es una hoja //nodo.ligaDer = nil & nodo.ligaIzq = nil
comienza
si x < padre.info
padre.ligaIzq ß nil
otro
padre.ligaDer ß nil
termina
b) El nodo que se desea eliminar tiene un único hijo
En éste caso para eliminar un nodo su padre deberá referenciar a su hijo.
Si se desea eliminar el nodo con llave de búsqueda 4, se debe cambiar el subárbol izquierdo de 5 por el subárbol que contiene a 2 como raíz.
Esto mismo ocurre cuando se trata de eliminar un nodo con un único subárbol izquierdo, suponga ahora que deseamos eliminar el nodo cuya información es 6 del árbol mostrado en la figura anterior. En este caso bastaría con que el subárbol izquierdo de 8 referenciará al subárbol derecho del 6 (nodo 7).
//el nodo tiene un solo hijo izquierdo
si nodo.ligaIzq nil & nodo.ligaDer = nil
si x < padre.info
padre.ligaIzq ß nodo.ligaIzq
otro
padre .ligaDer ß nodo.ligaIzq
// el nodo tiene un solo hijo derecho
otro si nodo.ligaIzq = nil & nodo.ligaDer nil
si x < padre.info
padre.ligaIzq ß nodo.ligaDer
otro
padre.ligaDer ß nodo.ligaDer
c) El nodo que se desea eliminar tiene dos hijos
En este caso se debe sustituir el valor de la información del nodo que se desea borrar por el nodo que contiene la menor llave que se encuentra en el subárbol derecho o bien la llave mayor del subárbol izquierdo, esto es necesario para no perder la propiedad de árbol binario de búsqueda. En cualquier elección que se tome, (el menor de los mayores o el mayor de los menores), el nodo que contiene esa información a lo más tendrá un hijo, por lo que su eliminación es fácil de realizar.
Si se desea eliminar la raíz (que tiene 2 hijos) del árbol anterior, se puede substituir la llave 8 por la 7, y después eliminar el nodo que lo contiene
o bien substituirla por el menor de los mayores, es decir, la llave 9
A continuación se presenta el algoritmo general para borrar un nodo de un árbol binario de búsqueda:
void borra (Objeto x)
comienza
nodo ß localiza ( x, padre)
si nodo = nil entonces
error (no existe)
otro
comienza
si nodo.hijoDer = nil & nodo.hijoIzq = nil entonces
substituye(nodo, padre, Nodo.hijoDer)
otro
si nodo.hijoDer = nil entonces
substituye( nodo, padre, nodo.hijoIzq)
otro si nodo.hijoIzq = nil entonces
substituye(nodo, padre, Nodo.ligader)
otro
comienza
max ß MaxMin(nodo, padreMax)
nodo.info ß max.info
substituye (max, padreMax, max.hijoIzq)
termina
termina
termina
La función para encontrar el mayor de los menores es el siguiente:
Es fácil demostrar por inducción que la llave mayor de un árbol binario con la propiedad de montículo se encuentra almacenada en la raíz. En general, cuando la llave en la raíz es eliminada, el nodo que la contiene no puede eliminarse ya que quedarían dos hijos sin padre, por lo tanto necesitamos un método que reestablezca la propiedad de montículo.
Suponga que cualquier hoja es eliminada y la llave es transferida a la raíz. Claramente la propiedad de heap puede ser violada. Por ejemplo, considere el árbol anterior (representado en la siguiente figura del lado izquierdo), donde se desea eliminar la raíz, sustituyéndola por alguna hoja (representado en la siguiente figura del lado derecho)
El problema aquí es que el elemento de la raíz no satisface la propiedad de montículo. Esta estructura es llamada un semimontículo y ahora se puede considerar la estrategia de transformar el semimontículo en un montículo.
La única violación de la propiedad de montículo antes de la restauración es que la llave K en el árbol sea muy pequeña. Si es así, se puede cambiar a K con la llave de su hijo más grande, y entonces la nueva llave de la raíz será más grande que las llaves de sus hijos. Ahora la única posible violación de la propiedad de montículo es de nuevo que K sea muy pequeña y deba moverse un nivel hacia abajo. Esto puede manejarse a través de llamadas recursivas y eventualmente se obtendrá la propiedad de montículo hasta que quizá K no tenga hijos.
Considere lo anterior de manera gráfica:
El árbol anterior cuya raíz es 10 y tiene como hijos al 50 y al 40, para restablecer la propiedad de montículo y como 50 es el mayor se intercambia su valor con el 10:
Con este cambio ahora el semimontículo se encuentra con raíz en el nodo numerado con el 2, porque 10 es menor que 30 y 20, lo cual nos lleva a intercambiar el valor de 30 hacia la raíz:
Como puede observarse en la representación de almacenamiento contiguo es fácil definir funciones que regresen al hijo izquierdo y al hijo derecho. Cada función toma como argumento un índice del arreglo.
Objeto borra ()
comienza
aux ß info[0]
info[0] ß info[último]
último --
ajustaAbajo (0)
termina
void ajustaAbajo (int origen)
comienza
si ((2*origen) < último) entonces
comienza
si (info[origen] < info[2*origen]) or
info[origen] > info[(2*origen)+1]
comienza
si (info[(2*origen)+1] < info[2*origen])
nodo ß 2*origen
otro
nodo ß (2*origen) +1
Intercambia (origen, nodo)
ajustaAbajo (nodo)
termina
termina
void intercambia (int nodo1, int nodo2)
comienza
aux ß info[nodo1]
info[nodo1] ß info[nodo2]
info[nodo2] ß aux
termina
Insertar:
El algoritmo de inserción trabaja en forma contraria a la de borrar. En este caso, una llave K desea insertarse en un montículo. Esta puede insertarse en cualquier localidad disponible del árbol, de esta forma, la única violación que puede ocurrir es que K sea más grande que su padre y que necesite moverse un nivel hacia arriba en el árbol.
En la representación de almacenamiento secuencial, simplemente se incrementa el tamaño del montículo en uno y se incluye la nueva llave al final de las n llaves que forman el árbol y verificamos que se cumpla la propiedad de montículo. En el caso que no se cumpla será necesario intercambiar su valor con el de su padre hasta que su padrea sea mayor que él.
void inserta (Objeto k)
comienza
último ++
info[último]ß k
ajustaArriba(último)
termina
void ajustaArriba (int origen)
comienza
padre ß origen div 2
si padre > 0
comienza
si info [padre] < info[origen]
comienza
intercambia (padre, origen)
ajustaArriba (padre)
termina
termina
termina
Suponga ahora, que se tiene un árbol binario completo cuyas llaves no cumplen la propiedad de montículo ¿cómo convertirlo en un montículo?
Una forma de resolver el problema consiste en convertir cada subárbol en un montículo, así se tiene un árbol con raíz y dos subárboles que son montículos, el árbol completo será un montículo si se intercambia la llave del nodo raíz con la llave mayor de sus dos hijos:
