Download El TAD Árbol El TAD Árbol

El TAD Árbol
Tema 3
Objetivos
! Presentar el árbol como estructura de datos jerárquica
! Estudiar diferentes variantes de árboles, tanto en su especificación como en su implementación
Contenidos
3.1 Concepto, definiciones y terminología básica
3.2 Árbol n-ario
3.2.1 Especificación algebraica
3.2.2 Implementación
3.3 Árbol binario
3.3.1 Especificación algebraica
3.3.2 Implementación
3.4 Recorridos sobre árboles
3.5 Árboles binarios de búsqueda (ABB)
3.5.1 Especificación algebraica
3.5.2 Implementación
Algoritmos y Estructuras de Datos II
Tema 3
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
1
Universidad de Huelva
2
El TAD Árbol
3.6 Árboles binarios equilibrados
3.7 Árboles B, B+ y B*
3.8 Colas de prioridad y montículos
Duración
! 7 clases (10,5 h)
Bibliografía
! Estructuras de datos: especificación, diseño e implementación
Autor: Xavier Franch Gutiérrez
Editorial : Ediciones UPC, 1999
Págs. 219-303
! Estructuras de datos. Algoritmos, abstracción y objetos
Autor: Luis Joyanes Aguilar, Ignacio Zahonero Martínez
Editorial: McGraw-Hill
Págs. 311-416
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
El TAD Árbol
Tema 3
3.1 Concepto, definiciones y terminología básica
! Los árboles son estructuras que organizan sus elementos, denominados nodos, formando
jerarquías. De entre estos nodos existe uno especial denominado raíz
! Existe una relación (de paternidad entre los nodos) que hace que la estructura sea jerárquica
frente a la estructura lineal
!
El uso de los árboles está muy extendido en programación. Algunos ejemplos pueden ser:
! estructurar los directorios y archivos en los sistemas operativos
! representar la estructura de las fórmulas matemáticas
! organizar la información en los SGBD
! representar la estructura sintáctica de un programa fuente en los compiladores
! representar sistemas de clasificación
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
3
El TAD Árbol
Tema 3
! La definición recursiva de árbol es: Un árbol n-ario (con n ≥ 1) es un conjunto no vacío de
elementos o nodos del mismo tipo tal que:
! un único nodo es un árbol, llamado raíz del árbol
! el resto de los elementos se distribuyen en m (0 ≤ m ≤ n) subconjuntos disjuntos,
denominados subárboles, cada uno de los cuales es a su vez un árbol n-ario
! Un árbol con raíz x y subárboles A1, …, Am se representa de la siguiente forma:
x
A1
Algoritmos y Estructuras de Datos II
...
Am
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
4
El TAD Árbol
Tema 3
! Podemos clasificar los árboles atendiendo a diferentes criterios:
" Cuando existe una relación de orden total en el conjunto de los subárboles de
un árbol n-ario, el árbol se llama ordenado (será el que utilizaremos)
" Si no existe limitación para el número de hijos que pueda tener un nodo, el árbol
se denomina general. Por el contrario, si existe un número fijo n que limita el
número de hijos de un nodo, el árbol se denomina n-ario
" Cuando los nodos de una árbol contienen información (caso más habitual), el
árbol se denomina etiquetado
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
5
El TAD Árbol
Tema 3
Terminología Básica
• Nodo: Cada posición dentro del árbol junto
con la información asociada
A
B
C
E
H
I
F
J
• Si existe una arista (rama) dirigida del nodo n
al nodo m, entonces n es el padre de m y m
es un hijo de n
D
G
K
M
Algoritmos y Estructuras de Datos II
• Los hijos del mismo padre se denominan
hermanos
L
• Todos los nodos de un árbol menos uno,
denominado nodo raíz, tienen un único padre
• Una hoja de un árbol es un nodo que no
tiene hijos. El resto de los nodos se denominan
interiores o internos
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
6
El TAD Árbol
Tema 3
Terminología Básica
• Se denomina camino del nodo n1 al nodo nk
a la secuencia de nodos de un árbol n1, n2, …,
nk, de forma que ni es el padre de ni+1 (1 ≤ i ≤
k)
A
B
C
E
H
D
F
I
• La longitud de un camino es el número de
nodos del camino menos 1. Por convenio,
decimos que existe un camino de longitud 0 de
un nodo a sí mismo
G
J
K
L
M
• Si existe un camino desde un nodo n1 hasta
un nodo n2, se dice que n1 es antecesor de n2,
y n2 es descendiente de n1
• El padre de un subárbol o nodo es su primer
antecesor propio. Los hijos de un subárbol o
nodo son sus primeros descendientes
propios
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
7
El TAD Árbol
Tema 3
Terminología Básica
• La altura de un nodo en un árbol es la
longitud del camino desde dicho nodo a la hoja
más lejana que sea alcanzable desde él
A
B
C
E
H
I
F
J
K
M
D
• La altura de un árbol es la altura del nodo
raíz
G
• La profundidad o nivel de un nodo en un
árbol es la longitud del único camino existente
desde el nodo raíz hasta dicho nodo
L
• Por definición, el número de niveles de un
árbol se define como uno más el nivel de la
hoja más profunda. En el nivel 0 sólo está el
nodo raíz
• El grado de un árbol es el número máximo
de hijos que pueden tener sus subárboles
• El número máximo de nodos en el nivel
i-ésimo de un árbol de grado n es ni
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
8
El TAD Árbol
Tema 3
3.2 Especificación Algebraica
! La operación básica de la signatura de los árboles es la de “enraizar” un número
indeterminado de árboles para formar un nuevo árbol
! La sintaxis de las especificaciones algebraicas no permite declarar operaciones con un
número indeterminado de parámetros
! Debemos definir nuevos conceptos que nos ayuden a construir la especificación algebraica
" Un bosque ordenado de grado n (n ≥ 1) es una secuencia A1, …, Am (0 ≤ m ≤ n) de
árboles n-arios ordenados. Si m = 0, el bosque se llama vacío
" Un árbol n-ario ordenado se genera a partir de un elemento r y un bosque de grado n,
considerando al elemento r la raíz del nuevo árbol y el bosque como sus subárboles
" Definimos el tipo bosque como una lista en la que los elementos son árboles
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
9
El TAD Árbol
Tema 3
espec arbolesOrdenados
usa booleanos, naturales, listas
parámetro formal
género elemento
fpf
renombrar lista<árbol> por bosque
géneros árbol
operaciones
_ Θ _ : elemento bosque # árbol
raíz: árbol # elemento
hijos: árbol # bosque
parcial subárbol: árbol natural # árbol
numHijos: árbol # natural
hoja?: árbol # booleano
altura: árbol # natural
privada altBosque: bosque # natural
Algoritmos y Estructuras de Datos II
Universidad de Huelva
Gen (árbol) = { _ Θ _ }
Mod (árbol) = {subárbol}
Obs (árbol) = {raíz, hijos, numHijos, hoja?, altural}
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
10
El TAD Árbol
Tema 3
dominios de definición b: bosque; i: natural; e: elemento
subárbol (e Θ b, i) está definido sólo si (1 ≤ i) ∧ (i ≤ long (b))
ecuaciones b: bosque; i: natural; e: elemento; a: árbol
raíz (e Θ b) =
hijos (e Θ b) =
subárbol (e Θ b, i) =
numHijos (e Θ b) =
hoja? (e Θ b) =
altura (a) =
altBosque ([ ]) =
altBosque (+izq (a, b)) =
fespec
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
11
El TAD Árbol
Tema 3
3.3 Implementación del árbol n-ario
! La implementación se hará de forma dinámica mediante punteros, usando una
representación denominada “primogénito – siguiente hermano”
" Consiste en crear, para cada nodo, una lista dinámica con sus hijos
! el tipo árbol es un puntero a un objeto con tres propiedades: la información correspondiente
al elemento raíz, un puntero al objeto correspondiente al primer hijo, y otro puntero al objeto
correspondiente al siguiente hermano
a
3
·
3
14
15
14
9
2
6
33
Algoritmos y Estructuras de Datos II
9
·
15
·
2
·
I.T. en Informática de Gestión/Sistemas
6
·
·
Universidad de Huelva
33
·
·
12
El TAD Árbol
Tema 3
módulo TadArbol
importa TadElemento, TadNodoArbol, TadLista
exporta
tipo
bosque = lista<árbol>
árbol = clase
público
constructor plantar (e: elemento; b: bosque)
función observaRaíz: elemento
acción hijos (var b: bosque)
acción subárbol (i: natural; var sa: árbol)
función numHijos: natural
función esHoja: booleano
función altura: natural
acción copia (a: árbol)
acción libera
privado
raiz: PtrNodoArbol;
fclase;
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
13
El TAD Árbol
Tema 3
! Se define una clase NodoArbol, que representa a cada uno de los nodos que
forman un árbol
tipo
PtrNodoArbol = puntero a NodoArbol;
nodoArbol = clase
público
constructor creaNodoArbol(e: Elemento; ph,sh:PtrNodoArbol);
acción setElemento(e: Elemento);
acción setPrimHijo(pph: PtrNodoArbol);
acción setSigHermano(psh: PtrNodoArbol);
función getElemento: Elemento;
acción getPrimHijo: PtrNodoArbol;
función getSigHermano: PtrNodoArbol;
privado
elem: Elemento;
PrimHijo, SigHermano: PtrNodoArbol;
fclase;
ftipo;
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
14
El TAD Árbol
Tema 3
acción árbol.plantar (e:elemento; b:bosque)
faccion;
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
El TAD Árbol
Tema 3
función árbol.subárbol(i: natural; var sa: árbol);
función árbol.altura:natural
ffunción;
faccion;
Algoritmos y Estructuras de Datos II
15
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
16
El TAD Árbol
Tema 3
3.4 Concepto, especificación e implementación de árbol binario
! Un árbol binario ordenado es un árbol en el que cada nodo puede tener, a lo
sumo, dos hijos
$ es un conjunto de nodos del mismo tipo que, o bien es el conjunto vacío, o
está formado por un nodo raíz enlazado a dos árboles binarios disjuntos
denominados subárbol izquierdo y subárbol derecho
t
m
h
Algoritmos y Estructuras de Datos II
k
f
I.T. en Informática de Gestión/Sistemas
d
Universidad de Huelva
17
Universidad de Huelva
18
El TAD Árbol
Tema 3
Especificación Algebraica
espec arbolesBinarios
usa booleanos, enteros
parámetro formal
género elemento
fpf
género arbin
operaciones
∆: # arbin
_ < _ , _ >: elemento arbin arbin # arbin
parcial raíz: arbin # elemento
parcial subIzq, subDer: arbin # arbin
vacío?: arbin # booleano
parcial altura: arbin # entero
dominios de definición iz, de: arbin; e: elemento
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
El TAD Árbol
Tema 3
ecuaciones
iz, de: arbin; e: elemento
raíz (e<iz, de>) =
subIzq (e<iz, de>) =
subDer (e<iz, de>) =
vacío? (∆) =
vacío? (e<iz, de>) =
altura (e<iz, de>) =
fespec
Clasificación de las operaciones:
Algoritmos y Estructuras de Datos II
Gen (arbin) = {
}
Mod (arbin) = {
}
Obs (arbin) = {
}
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
19
El TAD Árbol
Tema 3
Implementación del árbol binario
! La clase NodoB, que representa a cada uno de los nodos que forman un árbol
binario, es:
tipo
PtrNodo = puntero a NodoB;
nodoB = clase
público
constructor creaNodo(e: Elemento; izq,der:PtrNodo);
acción setElemento(e: Elemento);
acción setIzq(pizq: PtrNodo);
acción setDer(pder: PtrNodo);
función getElemento: Elemento;
acción getIzq: PtrNodo;
función getDer: PtrNodo;
privado
elem: Elemento;
izq, der: PtrNodo;
fclase;
ftipo;
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
20
El TAD Árbol
Tema 3
Implementación del árbol binario
módulo TadArbolBinario
importa TadElemento, TadNodoB
exporta
tipo
arbin= clase
público
raíz
dato
constructor creaVacío
acción plantar (e: elemento; ai, ad: arbin)
función raíz: elemento
acción subIzq ( var ai: arbin)
acción subDer ( var ad: arbin)
función esVacío: booleano
función altura (a: arbin): entero
acción copia ( viejo: arbin)
acción libera
izq
der
privado
raíz: PtrNodo;
fclase;
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
21
El TAD Árbol
Tema 3
Tipos de árboles binarios
! Un árbol binario de altura h se llama completo si tiene todas sus hojas a nivel h y
todos sus nodos interiores tienen dos hijos no vacíos
! Un árbol binario de altura h se llama semicompleto si los nodos de nivel h y h-1
son los únicos de grado cero o uno, de forma que las hojas del último nivel
ocupan las posiciones más a la izquierda de dicho nivel
50
20
80
10
8
Algoritmos y Estructuras de Datos II
40
35
74
99
60
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
22
El TAD Árbol
Tema 3
3.4 Recorridos sobre árboles
Los dos tipos básicos de recorrido para los árboles n-arios ordenados son:
PREORDEN
- si A no tiene hijos, se visita la raíz de A
- si los tiene, primero se visita la raíz de A y, a continuación, se recorren en
preorden los subárboles
POSTORDEN
- si A no tiene hijos, se visita la raíz de A
- si los tiene, primero se recorren en postorden los subárboles y a continuación se
visita la raíz de A
3
14
15
recorrido en preorden:
recorrido en postorden:
9
2
Algoritmos y Estructuras de Datos II
6
33
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
23
El TAD Árbol
Tema 3
Implementación para árboles n-arios
acción preOrden (a: árbol; var l: lista);
acción postOrden (a: árbol; var l: lista)
facción;
facción;
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
24
El TAD Árbol
Tema 3
Implementación para árboles binarios
Para los árboles binarios existe otro tipo de recorrido:
INORDEN
- si A es el árbol vacío, termina el recorrido
- si no lo es, primero se recorre en inorden el subárbol izquierdo, a
continuación se visita la raíz de A y, por último, se recorre en inorden el
subárbol derecho.
acción preOrden (a: arbin; var l: lista)
acción postOrden (a: arbin; var l: lista)
facción
facción
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
25
El TAD Árbol
Tema 3
Implementación para árboles binarios
A
acción InOrden (a: arbin; var l: lista)
B
C
D
H
facción
F
E
I
G
K
J
Recorrido preorden:
Recorrido inorden:
Recorrido postorden:
Algoritmos y Estructuras de Datos II
I.T. en Informática de Gestión/Sistemas
Universidad de Huelva
26