Download modulo 08 - Universidad Nacional de Colombia : Sede Medellin

3004597 – Estructura de Datos – Modulo 08
Universidad Nacional de Colombia – Sede Medellín
MODULO 08
OBJETIVOS
Por medio del desarrollo de este módulo el estudiante deberá:
Comprender la especificación del tipo de dato árbol y sus variantes (árbol binario, árbol binario de
búsqueda, AVL) Reconocer las particularidades de cada una de estas.
CONTENIDO
1
1.1
1.2
1.3
Árboles
Definición
Terminología
Especificación general del árbol
2 Clases de árboles (Especificación)
2.1 Árbol binario
2.1.1 Especificación
2.2 Árbol binario de búsqueda
2.2.1 Especificación
2.3 Árbol AVL
2.3.1 Especificación
A Referencias
B Taller
C Laboratorio
02-2003
1
3004597 – Estructura de Datos – Modulo 08
1
Universidad Nacional de Colombia – Sede Medellín
ÁRBOLES
Los árboles son estructuras de datos con relaciones jerárquicas, o de “uno a muchos” entre sus
componentes. Permiten representar de manera natural muchas de las relaciones entre elementos
existentes en el universo. Uno de los ejemplos más comunes de árbol es el árbol genealógico (de
hecho, gran parte de la terminología usada para describir árboles es tomada de la genealogía)
como se ve en la figura 1.1, de la cual puede inferirse que Luis es el padre de Juan, Pedro y Maria,
y a su vez Juan es el padre de Mario y José y María es la madre de Mateo.
Figura 1.1: Árbol genealógico
Luis
Camino simple
Juan
Mario
José
Elías
Pedro
Arista
Es el
Nodo
primer
nodo
del
árbol.
María
Se
caracte
riza por
ser el
único
Mateo
nodo
que no
tiene
predec
esores.
ta
Nivel 1
Nivel 2
Nivel 3
Nivel 4
1.1 DEFINICIÓN
En el contexto de las computadoras, se denomina árboles a aquellas estructuras de datos que
presentan relaciones jerárquicas entre sus elementos. Su principal característica es que la relación
entre los elementos es “de uno a muchos”, es decir no son lineales (de uno a uno). Por ejemplo,
en la figura 1.1 puede verse que un integrante cualquiera puede tener muchos (o ningún)
hijos.
1.2 TERMINOLOGÍA
Nodo: Los elementos de un árbol son elementos estándar, es decir, tipos de datos que contienen
un campo clave (identificador único). Un nodo está compuesto por un solo elemento. Al referirnos
a un nodo, implícitamente nos referimos a todos los elementos que lo componen. En los gráficos
de árboles, los nodos se representan como esferas y en ocasiones como cajas, dentro del nodo
se escribe la clave del elemento que contiene.
Arista: Son las líneas que conectan a los nodos. Representan relaciones jerárquicas entre los
nodos, por lo tanto, un nodo puede tener ninguna, una o varias aristas que salen de él.
02-2003
2
3004597 – Estructura de Datos – Modulo 08
Nodo raíz: Es el primer nodo del árbol.
predecesores (ancestros).
Universidad Nacional de Colombia – Sede Medellín
Se caracteriza por ser el único nodo que no tiene
Nodos hojas: Son aquellos nodos que no tienen sucesores (hijos).
Camino simple: Es una secuencia de nodos n1, n2, ... ,nk tales que todos los nodos son distintos
y hay una arista entre cada par de nodos (n1, n2), (n2, n3), ... (n(k-1), nk). Se dice que este es un
camino simple desde el nodo n1 hasta el nodo nk.
Longitud de camino: La longitud de un camino es el número de nodos que este contiene. Puede
calcularse como el número de aristas recorridas mas uno. (En algunos textos, es el número de
aristas). Por ejemplo, el camino entre Luis y Mario, tiene longitud tres (ver figura 1.1).
Padre de un nodo: El predecesor de un nodo se conoce como el padre del nodo. Por ejemplo,
como se ve en la figura 1.1, María es el padre de Mateo.
Hijo de un nodo: Los sucesores de un nodo se conocen como hijos del nodo. Como se ve en la
figura 1.1, Mario y José son los hijos de Juan.
Antecesor: Sea A algún nodo de un árbol. Si A es el nodo raíz, entonces A no tiene
antecesores. De otro modo, el padre de A y todos los antecesores del padre de A son los
antecesores de A. También puede decirse que los antecesores de A son aquellos nodos que se
encuentran en el único camino simple que va desde A hasta la raíz del árbol. Por ejemplo, en la
figura 1.1, los antecesores de José son Juan y Luis.
Descendientes: Si D es un nodo hoja, no tiene descendientes. De otro modo, cada hijo de D y
todos los descendientes de cada hijo de D son descendientes de D. Por ejemplo, en la figura 1.1,
los descendientes de Juan son Mario, José y Elías.
Subárbol: Dado algún nodo de un árbol, dicho nodo junto a todos sus descendientes, forman un
subconjunto del árbol llamado subárbol. La figura 1.2 muestra un subárbol de la figura 1.1.
Figura 1.2: Subárbol
Juan
Mario
José
Elías
Hermanos: Dos nodos son hermanos si tienen el mismo padre. Por ejemplo en la figura 1.2 los
nodos Mario y José son hermanos.
Nivel o profundidad: El nivel de un nodo se define como el número de nodos que se encuentran
entre él y la raíz (contando al nodo y la raíz). La raíz tiene un nivel de 1. Por ejemplo, el nodo
Mateo de la figura 1.1 se encuentra en el nivel 3.
02-2003
3
3004597 – Estructura de Datos – Modulo 08
Universidad Nacional de Colombia – Sede Medellín
Altura del árbol: Se define la altura de un árbol como el máximo nivel presente en el árbol. La
altura del árbol de la figura 1.1 es 4.
2
CLASES DE ÁRBOLES
Existen varios tipos de árboles usados frecuentemente en programación, cada uno de ellos tiene
propiedades especiales y usos específicos, pero en general todos se ajustan a la definición de
árbol vista en la sección anterior.
2.1 ARBOL BINARIO
El árbol binario tiene las siguientes características distintivas:
-
Cada nodo puede tener como máximo 2 subárboles, y por tanto no puede tener más de
dos hijos.
-
Cada subárbol se identifica como el subárbol izquierdo o el subárbol derecho de su padre.
-
Puede ser vacío.
Alternativamente, puede definirse el árbol binario de manera recursiva:
Un árbol binario puede ser vacío, o puede ser un nodo llamado nodo raíz que posee dos
subárboles binarios. Estos subárboles binarios son disjuntos entre sí y son disjuntos del nodo
raíz, y se llaman el subárbol izquierdo y el subárbol derecho del nodo raíz respectivamente.
Uno de los usos más importantes que se le ha dado a los árboles binarios es la representación de
expresiones en compiladores, la figura 2.1 ilustra el árbol binario que representa la expresión
aritmética (5+3)*(1-(a++))
Figura 2.1: Árbol binario
*
Subárbol
izquierdo
del nodo
raíz
+
5
2.1.1
02-2003
Especificación
Subárbol
derecho
del nodo
raíz
-
3
1
++
a
Subárbol
izquierdo
del nodo
++
4
3004597 – Estructura de Datos – Modulo 08
Universidad Nacional de Colombia – Sede Medellín
A continuación se presenta la especificación del árbol binario que incluye una colección de
operaciones que se pueden efectuar sobre él. Estas operaciones se describen desde un punto de
vista lógico y carecen de cualquier tipo de detalles concernientes a la implementación.
Especificación TD árbol binario (basada en Stubbs & Webre pg. 181)
-
Elementos: Los elementos de un árbol binario son nodos. Cada nodo contiene un elemento estándar
identificado de manera única por un campo clave.
-
Estructura: Tiene una estructura jerárquica. Un árbol binario puede ser vacío. En caso contrario es
un nodo, llamado nodo raíz unido a dos árboles binarios disjuntos uno de otro y del nodo raíz. Estos
árboles se llaman el subárbol izquierdo y derecho respectivamente. Cada nodo (excepto el nodo raíz)
tiene un único padre. Cada nodo puede tener uno o dos hijos, o bien no tener ninguno. Cada
hijo se denota como hijo izquierdo o derecho de su padre.
-
Operaciones: Cada una de las operaciones, excepto crear(), asume la existencia de un árbol binario.
Ocasionalmente, en la poscondición, es necesario referirse al árbol o al nodo actual antes de la
operación. Se usará la notación T-pre (tree previous) y c-pre (current previous) para estas
referencias.
recorrer(ord)
PRE: El árbol es no vacío
POST: Cada nodo en el árbol ha sido procesado exactamente una vez. El orden en que los nodos
fueron procesados depende del valor de ord, como se muestra a continuación:
Caso de ord:
preorden: Cada nodo es procesado antes de su subárbol izquierdo y antes de su subárbol derecho.
inorden: Cada nodo es procesado después de todos los nodos en su subárbol izquierdo y antes de
cualquier nodo en su subárbol derecho.
postorden: Cada nodo es procesado después de su subárbol izquierdo y de su subárbol derecho.
insertar(e, rel)
PRE: puede darse ya sea que rel=raiz y el árbol es vacío o que rel  raiz y el árbol es no vacío.
POST: dependiendo del valor de rel, e pudo haber sido añadido. Si e fue añadido, el nodo que
contiene a e es el actual.
Caso de rel:
raíz: e es el elemento en la raíz del árbol.
hijoizq: si c-pre no tenía hijo izquierdo entonces tiene un hijo izquierdo que contiene a e, de otro
modo la función da error.
hijoder: si c-pre no tenía hijo derecho entonces tiene un hijo derecho que contiene a e, de otro modo
la función da error.
borrarsub()
PRE: el árbol es no vacío.
POST: el subárbol de T-pre cuya raíz es c-pre ha sido removido del árbol. El nodo raíz es el actual
(o nulo si c-pre era la raíz del árbol) .
02-2003
5
3004597 – Estructura de Datos – Modulo 08
Universidad Nacional de Colombia – Sede Medellín
actualizar(e)
PRE: el árbol es no vacío.
POST: el elemento del nodo actual tiene el valor de e.
e = leer()
PRE: el árbol es no vacío.
POST: e tiene el valor del elemento del nodo actual.
st = características()
PRE: el árbol es no vacío.
POST: st contiene el tamaño (número de nodos del árbol), la altura y la longitud promedio de un
camino desde la raíz hasta un nodo hoja del árbol.
ir_a(rel)
PRE: el árbol es no vacío.
POST: el nodo actual está determinado por el valor de rel como se indica a continuación.
caso de rel:
raiz: El nodo raíz es el actual.
padre: si c-pre tenía un nodo padre, este es el actual. De otro modo da error.
hijoizq: si c-pre tenía un hijo izquierdo, este es el actual. De otro modo da error.
hijoder: si c-pre tenía un hijo derecho, este es el actual. De otro modo da error.
r = vacio()
PRE: ninguna.
POST: si T-pre es vacío, el valor de r es VERDADERO, de otro modo el valor de r es FALSO.
crear()
PRE: no existe árbol.
POST: existe un árbol vacío.
destruir()
PRE: el árbol es no vacío.
POST: el árbol es vacío
2.2 ÁRBOL BINARIO DE BÚSQUEDA
Un árbol binario de búsqueda es un tipo especial de árbol binario en el cual la posición de cada
nodo en el árbol está determinada por el valor de alguno de los campos del elemento guardado en
el nodo (generalmente el campo clave) a este campo del elemento del nodo se le llamará campo
de clasificación.
Consideremos la búsqueda de un nodo que contiene un elemento particular. Este nodo se llamará
nodo objetivo, la búsqueda se inicia en la raíz del árbol, si la raíz es el nodo objetivo habrá
02-2003
6
3004597 – Estructura de Datos – Modulo 08
Universidad Nacional de Colombia – Sede Medellín
concluido la búsqueda, pero si no lo es a continuación hay que decidir si la búsqueda continuará
por el subárbol izquierdo o por el subárbol derecho de la raíz. El árbol binario de búsqueda permite
saber cual de los subárboles debe seguirse para llegar al nodo objetivo. Una consecuencia de
esto es que como máximo tendrá que recorrerse un número de nodos igual a la altura del
árbol para encontrar el nodo objetivo.
El árbol binario de búsqueda, como lo insinúa su nombre, hace que el proceso de buscar un nodo
que contenga un elemento en particular sea altamente eficiente. Por supuesto, para asegurar el
correcto funcionamiento del árbol binario de búsqueda es necesario restringir las funciones de
inserción y actualización para garantizar su integridad.
Un árbol binario de búsqueda es un árbol binario tal que para cada nodo N, las siguientes
afirmaciones son verdaderas:
-
Si L es algún nodo en el subárbol izquierdo de N, entonces el campo de clasificación de L
es menor que el campo de clasificación de N.
-
Si R es algún nodo en el subárbol derecho de N, entonces el campo de clasificación de R
es mayor que el campo de clasificación de N.
Ejemplo 2.1: Búsqueda en un árbol binario de búsqueda
En la figura 2.1 se muestra un árbol binario de búsqueda. A continuación se describe paso a paso
el proceso de búsqueda del nodo cuyo elemento tiene un valor de 10.
Primero se busca en la raíz, cuyo valor es 5. Como 10 es mayor que 5 se procede a buscar en el
subárbol derecho de la raíz.
Ahora estamos en el nodo 8, como 10 es mayor que 8, se procede a buscar en el subárbol derecho
de 8.
Ahora hemos llegado al nodo 12, como 10 es menor que 12, se procede a buscar en el subárbol
izquierdo del nodo 12.
Se ha encontrado el nodo con elemento 10.
Nótese que en el peor de los casos (en el que el elemento buscado no está en el árbol) se
habría tenido que recorrer como máximo un número de elementos igual a la altura del árbol (que
en el caso de la figura 2.1 es 5), mientras que en una lista se tendrían que recorrer todos los
componentes de la lista (por ejemplo, si el árbol de la figura 2.1 estuviera implementado en una
lista, al buscar un elemento que no pertenece a la lista se tendrían que recorrer 9 elementos).
Este efecto crece dramáticamente cuando el número de elementos manejados es muy grande, los
tiempos de búsqueda en una lista comparados con los de un árbol binario de búsqueda serán
abismalmente mayores.
02-2003
7
3004597 – Estructura de Datos – Modulo 08
Universidad Nacional de Colombia – Sede Medellín
Figura 2.1: Árbol binario de búsqueda
Búsqueda
del
elemento
10
5
2
1
0
8
4
12
10
11
2.2.1
Especificación
Muchas de las operaciones del árbol binario son exactamente iguales en el árbol binario de
búsqueda. actualizar e insertar deben ser modificadas para conservar la estructura del árbol de
búsqueda, además se añaden dos funciones nuevas: encontrar_clave y borrar_clave que toman
ventaja de las características del árbol de búsqueda.
Especificación TD árbol binario de búsqueda (basada en Stubbs & Webre pg. 207)
-
Elementos: Los elementos de un árbol binario de búsqueda son nodos. Se asume que cada nodo
contiene un elemento estándar y es identificado de manera única por el campo clave del
elemento.
-
Estructura: La estructura del árbol binario de búsqueda es la misma del árbol binario excepto que
en el árbol de búsqueda, si N es algún nodo del árbol todos los nodos en su subárbol izquierdo tienen
campos de clasificación menores que los de N y todos los nodos en su subárbol derecho tienen
campos de clasificación mayores que los de N.
-
Operaciones: T-pre se refiere al árbol antes de que fuera ejecutada la operación. Todas las
operaciones del árbol binario aplican y son idénticas, excepto las que se listan a continuación.
insertar(e)
PRE: existe el árbol.
POST: si T-pre no contenía el elemento e, entonces e es un elemento del árbol, de otro
modo la función genera error.
02-2003
8
3004597 – Estructura de Datos – Modulo 08
Universidad Nacional de Colombia – Sede Medellín
borrar_clave(key)
PRE: existe el árbol y es no-vacío.
POST: si T-pre contenía un elemento con campo clave igual a key, entonces ese elemento
ya no está en el árbol. De otro modo la función reporta error.
Si el árbol es no vacío el nodo raíz es el actual.
actualizar(e)
PRE: el árbol es no vacío.
POST: el elemento del nodo actual es e. El árbol sigue siendo un árbol binario de búsqueda.
findkey(key)
PRE: el árbol es no vacío.
POST: si el árbol contiene un nodo cuyo campo clave tiene el mismo valor de key, entonces
ese nodo es el actual. De otro modo el nodo actual es el nodo (hoja) al cual se conectaría
como hijo un nodo con campo clave key de ser insertado.
Las nuevas operaciones del árbol binario de búsqueda son más poderosas y más restrictivas.
La operación findkey se beneficia de la estructura del árbol binario de búsqueda, que la hace muy
eficiente, como se vio anteriormente.
La operación actualizar es particularmente importante, ya que es su deber proteger la integridad
del árbol binario de búsqueda. Si el usuario quiere cambiar el elemento de un nodo, entonces el
campo clave del nuevo elemento debe ser mayor que todos los campos clave del subárbol
izquierdo y menor que todos los campos clave del subárbol derecho. Si este no es el caso, el
árbol debe ser reestructurado para acomodar el nuevo elemento. Una forma sencilla de hacer
esto es borrar el elemento a ser modificado y luego insertar un elemento con los nuevos valores.
Dado un elemento, la operación insertar determina la posición apropiada y añade al árbol un nodo
que contiene el elemento a insertar. Nótese que la posición de inserción no puede ser especificada
por el usuario, quien podría cometer un error y arruinar la integridad del árbol.
En módulos posteriores se verá en detalle el funcionamiento de todas estas funciones y como
aplicarlas para crear un gestor de registros.
2.3 ÁRBOL AVL
Un árbol AVL es un caso especial de un árbol binario con altura balanceada. Un árbol binario es
un árbol-p de altura balanceada si para cada nodo en el árbol, la diferencia de las alturas de sus
dos subárboles es máximo p. Un árbol AVL es un árbol-1 de altura balanceada, es decir, en un
árbol AVL la diferencia de las alturas de los dos subárboles de cualquier nodo no puede ser
mayor que 1.
02-2003
9
3004597 – Estructura de Datos – Modulo 08
Universidad Nacional de Colombia – Sede Medellín
Figura 2.2: Árbol AVL
4
2
1
8
3
6
5
9
7
10
Puede demostrarse que la altura de un árbol AVL jamás excede 1.45Log 2n. Estudios empíricos
demuestran que la altura es aproximadamente log2n donde n es el número de nodos del árbol, esto
asegura que el número máximo de elementos que tendrían que recorrerse en una búsqueda (este
número es la altura del árbol) nunca será mayor a 1.45Log 2n, mientras que en un árbol binario de
búsqueda normal podría llegar a ser un número muy cercano a n (n si el árbol está "degenerado",
es decir sesgado hacia la derecha o hacia la izquierda, ver figura 2.3).
Figura 2.3: árbol binario de búsqueda
no AVL degenerado
1
4
7
9
2.3.1
Especificación
Todas las operaciones del árbol binario de búsqueda excepto insertar y borrar también se aplican
al árbol AVL. Los árboles AVL considerados en esta sección están construidos sobre el árbol
binario de búsqueda.
En módulos posteriores se discutirá en detalle la función insertar.
02-2003
10
3004597 – Estructura de Datos – Modulo 08
Universidad Nacional de Colombia – Sede Medellín
Especificación TD árbol AVL (basada en Stubbs & Webre pg. 226)
Elementos: Los elementos de un árbol AVL son nodos. Se asume que cada nodo contiene un elemento
estándar y es identificado de manera única por el campo clave del elemento.
Estructura: Los nodos se estructuran para formar un árbol binario de búsqueda de manera que la
diferencia en la altura de dos subárboles de cualquier nodo será como máximo 1.
Operaciones: Todas las operaciones del árbol binario de búsqueda, excepto insertar y borrar aplican al
árbol AVL. En este módulo sólo se considerará la función insertar.
insertar(e)
PRE: Existe el árbol AVL y no contiene un elemento cuyo valor es e.
POST: El árbol contiene a e y sigue siendo AVL.
02-2003
11
3004597 – Estructura de Datos – Modulo 08
Universidad Nacional de Colombia – Sede Medellín
ANEXOS
A REFERENCIAS
[DS1984] Stubbs. Daniel F. & Webre, Neil W., “Data Structures: with Abstract Data Types and
Pascal”, Brooks/Cole Publishing Company, 1984.
B TALLER
1
Señale las diferencias entre una estructura de datos lineal (como las listas) y una
jerárquica (árboles.)
2
Considere el árbol de la figura B.1.
a. Cuál es su altura?
b. Cuales son sus nodos hoja?
c. Cuál es el único camino simple del nodo raíz a cada uno de los nodos hoja?
3
Muestre como puede usarse un árbol binario para representar las relaciones entre una
persona y todos los ancestros de esa persona. Dibuje el árbol con sus propios ancestros.
Que persona está en la raíz del árbol?
4
Dibuje un árbol AVL insertando cada uno de los siguientes nodos: 5, 7, 6, 9, 2, 3, 4
recuerde que debe mantener la estructura del árbol binario de búsqueda y equilibrar el
árbol.
Figura B.1: Ejercicio 2
A
D
E
F
K
Q
J
O
Z
C CREDITOS
Editor: PhD. Fernando Arango
Colaboradores: Ing. Edwin Hincapié, Ms.C. Francisco Moreno, Santiago Londoño, Alberto Jiménez,
Juan Carlos Hernández, Carlos Andrés Giraldo, Diego Figueroa.
02-2003
12