Download Tema 11

Metodología y Tecnología de la
Programación
Curso 2008/09
Tema 11
Árboles
Temario
Tema 11. Árboles
11.1
11.2
11.3
11.4
11.5
11.6
11.7
Terminología Fundamental
TDA Árbol
TDA Árbol Binario
TDA Árbol basado en su Definición Recursiva
TDA Árbol Binario basado en su Definición Recursiva
Árboles Parcialmente Ordenados: Colas de Prioridad
Árboles Binarios de Búsqueda: Conjuntos
Metodología y Tecnología de la Programación
Tema 11. Árboles
2
11.1 Terminología Fundamental
Árbol:
Colección de elementos.
Existe una estructura jerárquica:
⇒ relación de paternidad entre los elementos.
elementos: nodos ⇒ nodo raíz.
Matemáticamente:
grafo no orientado, conexo y acíclico.
existe un vértice destacado llamado raíz.
Metodología y Tecnología de la Programación
Tema 11. Árboles
3
11.1 Terminología Fundamental
Árbol A n-ario:
O bien es el conjunto vacío ⇒ árbol vacío.
O bien no es vacío:
elemento raíz.
A1,…,Am subárboles.
Definiciones:
Árbol ordenado: el orden de los subárboles importa.
La raíz de A es padre de la raíz de A1,…,Am.
Las raíces de A1,…,Am son hijos de la raíz de A.
Metodología y Tecnología de la Programación
Tema 11. Árboles
4
11.1 Terminología Fundamental
Árbol binario A:
O bien es el conjunto vacío ⇒ árbol vacío.
O bien no es vacío:
elemento raíz.
A1, A2 subárboles izquierdo y derecho.
Definiciones:
No es lo mismo un árbol 2-ario que un árbol binario:
⇒ en el árbol binario se distingue entre súbárboles izquierdo y derecho.
Los términos padre e hijo descritos para árboles n-arios son también utilizados
para árboles binarios.
Metodología y Tecnología de la Programación
Tema 11. Árboles
5
11.1 Terminología Fundamental
Otros términos comunes:
Camino del nodo n1 a nk:
Secuencia de nodos n1,…, nk
tal que ni es padre de ni+1
Longitud de un camino:
Número de nodos del camino menos 1.
Existe un camino de longitud 0 de todo nodo a sí mismo.
Ascendiente/Descendiente:
Un a es ascendiente de b (y b descendiente de a), si existe un camino de a a b.
Todo nodo es ascendiente (y descendiente) de sí mismo.
Los ascendientes (y descendientes) de un nodo, excluido el propio nodo, se
denominan ascendientes (y descendientes) propios.
Hoja:
Nodo sin descendientes propios.
Metodología y Tecnología de la Programación
Tema 11. Árboles
6
11.1 Terminología Fundamental
Altura:
La altura de un nodo es la longitud del camino más largo de
ese nodo a una hoja.
La altura de un árbol es la altura de la raíz.
Profundidad:
La profundidad de un nodo es la longitud del camino único
desde ese nodo a la raíz.
Metodología y Tecnología de la Programación
Tema 11. Árboles
7
11.2 TDA Árbol: Descripción
Formas de construir árboles:
Añadir un nodo a un árbol:
como hijo más a la izquierda.
como hermano derecho.
Utilizar directamente en la definición recursiva de árboles.
Entradas:
A1,…,Am
nodo raiz.
Metodología y Tecnología de la Programación
Tema 11. Árboles
8
11.2 TDA Árbol: Operaciones
Operaciones de construcción:
CREA
Operaciones de posicionamiento:
RAIZ
PADRE
HIJOIZQUIERDO, HERMANODERECHO
Operaciones de consulta:
VACIO
RECUPERA
NULO
Operaciones de modificación:
INSERTARAIZ, INSERTAHIJO, INSERTAHERMANO
SUPRIMEHIJO, SUPRIMEHERMANO
MODIFICA
Metodología y Tecnología de la Programación
Tema 11. Árboles
9
11.2 TDA Árbol: Especificación
Arbol = TDA con operaciones crea, raiz, padre, hijoIzquierdo,
hermanoDerecho, vacio, recupera, nulo, insertaRaiz, insertaHijo,
insertaHermano, suprimeHijo, suprimeHermano, modifica.
DESCRIPCIÓN:
Los valores del TDA Arbol son árboles n-arios donde cada nodo contiene un dato del
tipo Elemento. Los nodos son del tipo Nodo. Los árboles son mutables:
insertaRaiz, insertaHijo, insertaHermano, suprimeHijo,
suprimeHermano y modifica añaden, eliminan y modifican respectivamente
elementos de un árbol.
OPERACIONES:
crea() devuelve (A:Arbol)
efecto: Devuelve el árbol vacío A.
raiz(A:Arbol) devuelve (Nodo)
efecto: Devuelve la raíz de A. Si A es vacío, devuelve nulo.
Metodología y Tecnología de la Programación
Tema 11. Árboles
10
11.2 TDA Árbol: Especificación
padre(A:Arbol; N:Nodo) devuelve (Nodo)
requerimientos: N ≠ nulo.
efecto: Devuelve el padre de N. Si N es la raíz, devuelve nulo.
hijoIzquierdo(A:Arbol; N:Nodo) devuelve (Nodo)
requerimientos: N ≠ nulo.
efecto: Devuelve el hijo más a la izquierda de N. Si N no tiene hijos, devuelve nulo.
hermanoDerecho(A:Arbol; N:Nodo) devuelve (Nodo)
requerimientos: N ≠ nulo.
efecto: Devuelve el hermano derecho de N. Si N no tiene hermano derecho,
devuelve nulo.
vacio(A:Arbol) devuelve (booleano)
efecto: Devuelve cierto si A es vacío, y falso en caso contrario.
recupera(A:Arbol; N:Nodo) devuelve (Elemento)
requerimientos: N ≠ nulo.
efecto: Devuelve el elemento contenido en el nodo N.
Metodología y Tecnología de la Programación
Tema 11. Árboles
11
11.2 TDA Árbol: Especificación
nulo(A:Arbol; N:Nodo) devuelve (booleano)
efecto: Devuelve cierto si N es nulo, y falso en caso contrario.
insertaRaiz(A:Arbol; E:Elemento)
requerimientos: A = vacío.
efecto: Añade un nodo, con contenido E, como raíz de A.
insertaHijo(A:Arbol; N:Nodo; E:Elemento)
requerimientos: N ≠ nulo.
modifica: A.
efecto: Añade un nodo, con contenido E, como hijo más a la izquierda de N.
insertaHermano(A:Arbol; N:Nodo; E:Elemento)
requerimientos: N ≠ nulo. N ≠ raíz.
modifica: A.
efecto: Añade un nodo, con contenido E, como hermano derecho de N.
Metodología y Tecnología de la Programación
Tema 11. Árboles
12
11.2 TDA Árbol: Especificación
suprimeHijo(A:Arbol; N:Nodo)
requerimientos: N ≠ nulo. hijoIzquierdo(N) ≠ nulo.
modifica: A.
efecto: Suprime el hijo más a la izquierda de N y todos sus descendientes.
suprimeHermano(A:Arbol; N:Nodo)
requerimientos: N ≠ nulo. hermanoDerecho(N) ≠ nulo.
modifica: A.
efecto: Suprime el hermano derecho de N y todos sus descendientes.
modifica(A:Arbol; N:Nodo; E:Elemento)
requerimientos: N ≠ nulo.
modifica: A.
efecto: Modifica el contenido de N, cambiándolo por el nuevo contenido E.
Metodología y Tecnología de la Programación
Tema 11. Árboles
13
11.2 TDA Árbol: Métodos en Java
Clase Arbol
class Arbol
Clases Internas
class Arbol.Nodo
Constructores
Arbol()
Métodos
Arbol.Nodo raiz()
Arbol.Nodo padre(Arbol.Nodo n)
Arbol.Nodo hijoIzquierdo(Arbol.Nodo n)
Arbol.Nodo hermanoDerecho(Arbol.Nodo n)
boolean vacio()
Elemento recupera(Arbol.Nodo n)
boolean nulo(Arbol.Nodo n)
void insertaRaiz(Elemento e)
void insertaHijo(Arbol.Nodo n, Elemento e)
void insertaHermano(Arbol.Nodo n, Elemento e)
void suprimeHijo(Arbol.Nodo n)
void suprimeHermano(Arbol.Nodo n)
void modifica(Arbol.Nodo n, Elemento e)
Metodología y Tecnología de la Programación
Tema 11. Árboles
14
11.2 TDA Árbol: Esquemas de recorrido
Esquemas de recorrido en árboles fundamentales:
Preorden(A):
Si A es vacío ⇒ lista vacía.
Si A no es vacío ⇒ raíz + preorden(A1) +…+ preorden(Am).
Inorden(A):
Si A es vacío ⇒ lista vacía.
Si A no es vacío ⇒ inorden(A1) + raiz + inorden(A2) +…+ inorden(Am).
Postorden(A):
Si A es vacío ⇒ lista vacía.
Si A no es vacío ⇒ postorden(A1) +…+ postorden(Am) + raíz.
Metodología y Tecnología de la Programación
Tema 11. Árboles
15
11.2 TDA Árbol: Utilización
static public void preOrden(Arbol a) {
preOrden(a,a.raiz());
}
static private void preOrden(Arbol a, Arbol.Nodo n) {
if (a.nulo(n)) return;
System.out.println(a.recupera(n).valor());
Arbol.Nodo m = a.hijoIzquierdo(n);
while (!a.nulo(m)) {
preOrden(a,m);
m = a.hermanoDerecho(m);
}
}
Metodología y Tecnología de la Programación
Tema 11. Árboles
16
11.2 TDA Árbol: Utilización
static public void inOrden(Arbol a) {
inOrden(a,a.raiz());
}
static private void inOrden(Arbol a, Arbol.Nodo n) {
if (a.nulo(n)) return;
Arbol.Nodo m = a.hijoIzquierdo(n);
inOrden(a,m);
System.out.println(a.recupera(n).valor());
while (!a.nulo(m)) {
m = a.hermanoDerecho(m);
inOrden(a,m);
}
}
Metodología y Tecnología de la Programación
Tema 11. Árboles
17
11.2 TDA Árbol: Utilización
static public void postOrden(Arbol a) {
postOrden(a,a.raiz());
}
static private void postOrden(Arbol a, Arbol.Nodo n) {
if (a.nulo(n)) return;
Arbol.Nodo m = a.hijoIzquierdo(n);
while (!a.nulo(m)) {
postOrden(a,m);
m = a.hermanoDerecho(m);
}
System.out.println(a.recupera(n).valor());
}
Metodología y Tecnología de la Programación
Tema 11. Árboles
18
11.2 TDA Árbol: Implementación con representación Enlazada
representación hijo izquierdo - hermano derecho.
mediante apuntadores.
Metodología y Tecnología de la Programación
Tema 11. Árboles
19
11.2 TDA Árbol: Implementación con representación Enlazada
TDA Árbol: Estructura de datos con representación Enlazada.
public class Arbol {
public class Nodo {
private Elemento elemento;
private Nodo padre, hijoIzquierdo, hermanoDerecho;
}
private Nodo raiz;
…
}
Eficiencia:
Todas las operaciones pueden realizarse con tiempos de ejecución O(1).
Excepto las de eliminación de nodos que requieren la eliminación de un
conjunto de nodos.
Estas últimas operaciones pueden realizarse fácilmente de forma recursiva.
Metodología y Tecnología de la Programación
Tema 11. Árboles
20
11.2 TDA Árbol: Implementación con representación Enlazada
public class Arbol {
public class Nodo {
private Elemento elemento;
private Nodo padre, hijoIzquierdo, hermanoDerecho;
}
private Nodo raiz;
public Arbol()
{ raiz = null; }
public Nodo raiz()
{ return raiz; }
public Nodo padre(Nodo n)
{ return n.padre; }
public Nodo hijoIzquierdo(Nodo n) { return n.hijoIzquierdo; }
public Nodo hermanoDerecho(Nodo n) { return n.hermanoDerecho; }
public boolean vacio()
{ return (raiz==null); }
public Elemento recupera(Nodo n)
{ return n.elemento; }
public boolean nulo(Nodo n)
{ return (n==null); }
Metodología y Tecnología de la Programación
Tema 11. Árboles
21
11.2 TDA Árbol: Implementación con representación Enlazada
public void insertaRaiz(Elemento e) {
raiz = new Nodo();
raiz.elemento = e;
raiz.padre = null;
raiz.hijoIzquierdo = null;
raiz.hermanoDerecho = null;
}
public void insertaHijo(Nodo n, Elemento e) {
Nodo aux = new Nodo();
aux.elemento = e;
aux.padre = n;
aux.hijoIzquierdo = null;
aux.hermanoDerecho = n.hijoIzquierdo;
n.hijoIzquierdo = aux;
}
Metodología y Tecnología de la Programación
Tema 11. Árboles
22
11.2 TDA Árbol: Implementación con representación Enlazada
public void insertaHermano(Nodo n, Elemento e) {
Nodo aux = new Nodo();
aux.elemento = e;
aux.padre = n.padre;
aux.hijoIzquierdo = null;
aux.hermanoDerecho = n.hermanoDerecho;
n.hermanoDerecho = aux;
}
public void suprimeHijo(Nodo n) {
n.hijoIzquierdo = n.hijoIzquierdo.hermanoDerecho;
}
public void suprimeHermano(Nodo n) {
n.hermanoDerecho = n.hermanoDerecho.hermanoDerecho;
}
public void modifica(Nodo n, Elemento e) {
n.elemento = e;
}
} // fin class Arbol
Metodología y Tecnología de la Programación
Tema 11. Árboles
23
11.3 TDA Árbol Binario: Descripción
Conjunto de operaciones muy similar al que hemos descrito para el
TDA Árbol.
Las operaciones de posicionamiento, inserción y eliminación van
dirigidas hacia el hijo izquierdo y hacia el hijo derecho.
En el árbol binario, los subárboles se constituyen desde su
creación como subárboles izquierdos o derechos:
En un árbol, un subárbol puede ser creado como subárbol de más
la izquierda y después dejar de serlo.
En un árbol binario las operaciones de eliminación de nodos o
subárboles no provocan cambios en los restantes nodos o
subárboles.
Metodología y Tecnología de la Programación
Tema 11. Árboles
24
11.3 TDA Árbol Binario: Operaciones
Operaciones de construcción:
CREA
Operaciones de posicionamiento:
RAIZ
PADRE
HIJOIZQUIERDO, HIJODERECHO
Operaciones de consulta:
VACIO
RECUPERA
NULO
Operaciones de modificación:
INSERTARAIZ, INSERTAHIJOIZQUIERDO, INSERTAHIJODERECHO
SUPRIMEHIJOIZQUIERDO, SUPRIHIJOMEDERECHO
MODIFICA
Metodología y Tecnología de la Programación
Tema 11. Árboles
25
11.3 TDA Árbol Binario: Especificación
ArbolBinario = TDA con operaciones crea,raiz, padre, hijoIzquierdo,
hijoDerecho, vacio, recupera, nulo, insertaRaiz,
insertaHijoIzquierdo, insertaHijoDerecho, suprimeHijoIzquierdo,
suprimeHijoDerecho, modifica.
DESCRIPCIÓN:
Los valores del TDA ArbolBinario son árboles binarios donde cada nodo contiene un
dato del tipo Elemento. Los nodos son del tipo Nodo. Los árboles son mutables:
insertaRaiz, insertaHijoIzquierdo, insertaHijoDerecho,
suprimeHijoIzquierdo, suprimeHijoDerecho y modifica añaden, eliminan y
modifican respectivamente elementos de un árbol.
OPERACIONES:
crea() devuelve (A:ArbolBinario)
efecto: Devuelve el árbol binario vacío A.
raiz(A:ArbolBinario) devuelve (Nodo)
efecto: Devuelve la raíz de A. Si A es vacío, devuelve nulo.
Metodología y Tecnología de la Programación
Tema 11. Árboles
26
11.3 TDA Árbol Binario: Especificación
padre(A:ArbolBinario; N:Nodo) devuelve (Nodo)
requerimientos: N ≠ nulo.
efecto: Devuelve el padre de N. Si N es la raíz de A, devuelve nulo.
hijoIzquierdo(A:ArbolBinario; N:Nodo) devuelve (Nodo)
requerimientos: N ≠ nulo.
efecto: Devuelve el hijo izquierdo de N. Si N no tiene hijo izquierdo, devuelve nulo.
hijoDerecho(A:ArbolBinario; N:Nodo) devuelve (Nodo)
requerimientos: N ≠ nulo.
efecto: Devuelve el hijo derecho de N. Si N no tiene hijo derecho, devuelve nulo.
vacio(A:ArbolBinario) devuelve (booleano)
efecto: Devuelve cierto si A es vacío, y falso en caso contrario.
recupera(A:ArbolBinario; N:Nodo) devuelve (Elemento)
requerimientos: N ≠ nulo.
efecto: Devuelve el contenido de N.
Metodología y Tecnología de la Programación
Tema 11. Árboles
27
11.3 TDA Árbol Binario: Especificación
nulo(A:ArbolBinario; N:Nodo) devuelve (booleano)
efecto: Devuelve cierto si N es nulo, y falso en caso contrario.
insertaRaiz(A:ArbolBinario; E:Elemento)
requerimientos: A = vacío.
modifica: A.
efecto: Añade un nodo, con contenido E, como raíz de A como raíz de A.
insertaHijoIzquierdo(A:ArbolBinario; N:Nodo; E:Elemento)
requerimientos: N ≠ nulo y hijoIzquierdo(N) = nulo.
modifica: A.
efecto: Añade un nodo, con contenido E, como hijo izquierdo de N.
insertaHijoDerecho(A:ArbolBinario; N:Nodo; E:Elemento)
requerimientos: N ≠ nulo. hijoDerecho(N) = nulo.
modifica: A.
efecto: Añade un nodo, con contenido E, como hijo derecho de N.
Metodología y Tecnología de la Programación
Tema 11. Árboles
28
11.3 TDA Árbol Binario: Especificación
suprimeHijoIzquierdo(A:ArbolBinario; N:Nodo)
requerimientos: N ≠ nulo. hijoIzquierdo(N) ≠ nulo.
modifica: A.
efecto: Suprime el hijo izquierdo de N y todos sus descendientes.
suprimeHijoDerecho(A:ArbolBinario; N:Nodo)
requerimientos: N ≠ nulo. hijoDerecho(N) ≠ nulo.
modifica: A.
efecto: Suprime el hijo derecho de N y todos sus descendientes.
modifica(A:ArbolBinario; N:Nodo; E:Elemento)
requerimientos: N ≠ nulo.
modifica: A.
efecto: Modifica el contenido de N cambiándolo por el nuevo contenido E.
Metodología y Tecnología de la Programación
Tema 11. Árboles
29
11.3 TDA Árbol Binario: Métodos en Java
Clase ArbolBinario
class ArbolBinario
Clases Internas
class ArbolBinario.Nodo
Constructores
ArbolBinario()
Métodos
ArbolBinario.Nodo raiz()
ArbolBinario.Nodo padre(ArbolBinario.Nodo n)
ArbolBinario.Nodo hijoIzquierdo(ArbolBinario.Nodo n)
ArbolBinario.Nodo hijoDerecho(ArbolBinario.Nodo n)
boolean vacio()
Elemento recupera(ArbolBinario.Nodo n)
boolean nulo(ArbolBinario.Nodo n)
void insertaRaiz(Elemento e)
void insertaHijoIzquierdo(ArbolBinario.Nodo n, Elemento e)
void insertaHijoDerecho(ArbolBinario.Nodo n, Elemento e)
void suprimeHijoIzquierdo(ArbolBinario.Nodo n)
void suprimeHijoDerecho(ArbolBinario.Nodo n)
void modifica(ArbolBinario.Nodo n, Elemento e)
Metodología y Tecnología de la Programación
Tema 11. Árboles
30
11.3 TDA Árbol Binario: Esquemas de Recorrido
Esquemas de recorrido en árboles binarios:
Preorden(A):
Si A es vacío ⇒ lista vacía.
Si A no es vacío ⇒ raíz + preorden(A1) + preorden(A2).
Inorden(A):
Si A es vacío ⇒ lista vacía.
Si A no es vacío ⇒ inorden(A1) + raiz + inorden(A2).
Postorden(A):
Si A es vacío ⇒ lista vacía.
Si A no es vacío ⇒ postorden(A1) + postorden(A2) + raíz.
Metodología y Tecnología de la Programación
Tema 11. Árboles
31
11.3 TDA Árbol Binario: Utilización
static public void preOrden(ArbolBinario a) { preOrden(a,a.raiz()); }
static private void preOrden(ArbolBinario a, ArbolBinario.Nodo n) {
if (a.nulo(n)) return;
System.out.println(a.recupera(n).valor());
preOrden(a,a.hijoIzquierdo(n));
preOrden(a,a.hijoDerecho(n)); }
static public void inOrden(ArbolBinario a) { inOrden(a,a.raiz()); }
static private void inOrden(ArbolBinario a, ArbolBinario.Nodo n) {
if (a.nulo(n)) return;
inOrden(a,a.hijoIzquierdo(n));
System.out.println(a.recupera(n).valor());
inOrden(a,a.hijoDerecho(n)); }
static public void postOrden(ArbolBinario a) {
postOrden(a,a.raiz()); }
static private void postOrden(ArbolBinario a, ArbolBinario.Nodo n) {
if (a.nulo(n)) return;
postOrden(a,a.hijoIzquierdo(n));
postOrden(a,a.hijoDerecho(n));
System.out.println(a.recupera(n).valor()); }
Metodología y Tecnología de la Programación
Tema 11. Árboles
32
11.3 TDA Árbol Binario:
Implementación con representación Enlazada
representación hijo izquierdo - hijo derecho.
mediante apuntadores.
Metodología y Tecnología de la Programación
Tema 11. Árboles
33
11.3 TDA Árbol Binario:
Implementación con representación Enlazada
TDA Árbol: Estructura de datos con representación Enlazada.
public class ArbolBinario {
public class Nodo {
private Elemento elemento;
private Nodo padre, hijoIzquierdo, hijoDerecho;
}
private Nodo raiz;
…
}
Eficiencia:
Todas las operaciones pueden realizarse con tiempos de ejecución O(1).
Metodología y Tecnología de la Programación
Tema 11. Árboles
34
11.3 TDA Árbol Binario:
Implementación con representación Enlazada
public class ArbolBinario {
public class Nodo {
private Elemento elemento;
private Nodo padre, hijoIzquierdo, hijoDerecho;
}
private Nodo raiz;
public ArbolBinario()
{ raiz = null; }
public Nodo raiz()
{ return raiz; }
public Nodo padre(Nodo n)
{ return n.padre; }
public Nodo hijoIzquierdo(Nodo n) { return n.hijoIzquierdo; }
public Nodo hijoDerecho(Nodo n)
{ return n.hijoDerecho; }
public boolean vacio()
{ return (raiz==null); }
public Elemento recupera(Nodo n) { return n.elemento; }
public boolean nulo(Nodo n)
{ return (n==null); }
Metodología y Tecnología de la Programación
Tema 11. Árboles
35
11.3 TDA Árbol Binario:
Implementación con representación Enlazada
public void insertaRaiz(Elemento e) {
raiz = new Nodo();
raiz.elemento = e;
raiz.padre = null;
raiz.hijoIzquierdo = null;
raiz.hijoDerecho = null;
}
public void insertaHijoIzquierdo(Nodo n, Elemento e) {
n.hijoIzquierdo = new Nodo();
n.hijoIzquierdo.elemento = e;
n.hijoIzquierdo.padre = n;
n.hijoIzquierdo.hijoIzquierdo = null;
n.hijoIzquierdo.hijoDerecho = null;
}
Metodología y Tecnología de la Programación
Tema 11. Árboles
36
11.3 TDA Árbol Binario:
Implementación con representación Enlazada
public void insertaHijoDerecho(Nodo n, Elemento e) {
n.hijoDerecho = new Nodo();
n.hijoDerecho.elemento = e;
n.hijoDerecho.padre = n;
n.hijoDerecho.hijoIzquierdo = null;
n.hijoDerecho.hijoDerecho = null;
}
public void suprimeHijoIzquierdo(Nodo n) {
n.hijoIzquierdo = null; }
public void suprimeHijoDerecho(Nodo n) {
n.hijoDerecho = null; }
public void modifica(Nodo n, Elemento e) {
n.elemento = e; }
} // fin class ArbolBinario
Metodología y Tecnología de la Programación
Tema 11. Árboles
37
11.4 TDA Árbol basado en su Definición Recursiva
TDA Árbol: Especificación Formal.
Tipo: Arbol (Elemento)
Sintaxis:
arbolvacio → Arbol
arbolcompleto(Lista,Elemento) → Arbol
vacio(Arbol) → booleano
raiz(Arbol) → Elemento
subarboles(Arbol) → Lista
Semántica: ∀ L ∈ Lista, ∀ E ∈ Elemento:
vacio(arbolvacio) ⇒ cierto
vacio(arbolcompleto(L,E)) ⇒ falso
raiz(arbolvacio) ⇒ error
raiz(arbolcompleto(L,E)) ⇒ E
subarboles(arbolvacio) ⇒ error
subarboles(arbolcompleto(L,E)) ⇒ L
Metodología y Tecnología de la Programación
Tema 11. Árboles
38
11.4 TDA Árbol basado en su Definición Recursiva
TDA Lista de Árboles: Especificación Formal.
Tipo: Lista (Arbol)
Sintaxis:
listavacia → Lista
inserta(Lista,Arbol) → Lista
vacia(Lista) → booleano
cabeza(Lista) → Arbol
resto(Lista) → Lista
Semántica: ∀ L ∈ Lista, ∀ A ∈ Arbol:
vacia(listavacia) ⇒ cierto
vacia(inserta(L,A)) ⇒ falso
cabeza(listavacia) ⇒ error
cabeza(inserta(L,A)) ⇒ A
resto(listavacia) ⇒ error
resto(inserta(L,A)) ⇒ L
Metodología y Tecnología de la Programación
Tema 11. Árboles
39
11.4 TDA Árbol basado en su Definición Recursiva
Clase Arbol
class Arbol
Clase Lista
class Lista
Constructores
Arbol()
Arbol(Lista l, Elemento e)
Constructores
Lista()
Lista(Lista l, Arbol a)
Métodos
boolean vacio()
Elemento raiz()
Lista subarboles()
Métodos
boolean vacia()
Arbol cabeza()
Lista resto()
Metodología y Tecnología de la Programación
Tema 11. Árboles
40
11.4 TDA Árbol basado en su Definición Recursiva
Utilización del Árbol Inmutable: Recorrido en Pre-Orden
static public void preOrden(Arbol a) {
if (a.vacio()) return;
System.out.println(a.raiz().valor());
lista_preOrden(a.subarboles());
}
static private void lista_preOrden(Lista l) {
if (l.vacia()) return;
preOrden(l.cabeza());
lista_preOrden(l.resto());
}
Metodología y Tecnología de la Programación
Tema 11. Árboles
41
11.4 TDA Árbol basado en su Definición Recursiva
Utilización del Árbol Inmutable: Recorrido en In-Orden
static public void inOrden(Arbol a) {
if (a.vacio()) return;
Lista l = a.subarboles();
if (!l.vacia()) inOrden(l.cabeza());
System.out.println(a.raiz().valor());
if (!l.vacia()) lista_inOrden(l.resto());
}
static private void lista_inOrden(Lista l) {
if (l.vacia()) return;
inOrden(l.cabeza());
lista_inOrden(l.resto());
}
Metodología y Tecnología de la Programación
Tema 11. Árboles
42
11.4 TDA Árbol basado en su Definición Recursiva
Utilización del Árbol Inmutable: Recorrido en Post-Orden
static public void postOrden(Arbol a) {
if (a.vacio()) return;
lista_postOrden(a.subarboles());
System.out.println(a.raiz().valor());
}
static private void lista_postOrden(Lista l) {
if (l.vacia()) return;
postOrden(l.cabeza());
lista_postOrden(l.resto());
}
Metodología y Tecnología de la Programación
Tema 11. Árboles
43
11.4 TDA Árbol basado en su Definición Recursiva
Implementación del Árbol Inmutable Recursivo
public class Arbol {
private Elemento elemento;
private Lista subarboles;
public Arbol() { elemento=null; subarboles=null; }
public Arbol(Lista l, Elemento e) { elemento=e; subarboles=l; }
public boolean vacio(){
return ((elemento==null)&&(subarboles==null)); }
public Elemento raiz() { return elemento; }
public Lista subarboles() { return subarboles; }
} // fin class Arbol
public class Lista {
private Arbol arbol;
private Lista sig;
public Lista() { arbol=null; sig=null; }
public Lista(Lista l, Arbol a) { arbol=a; sig=l; }
public boolean vacia() { return ((arbol==null)&&(sig==null)); }
public Arbol cabeza() { return arbol; }
public Lista resto() { return sig; }
} // fin class Lista
Metodología y Tecnología de la Programación
Tema 11. Árboles
44
11.5 TDA Árbol Binario basado en su Definición Recursiva
TDA Árbol Binario: Especificación Formal.
Tipo: ArbolBinario (Elemento)
Sintaxis:
arbolvacio → ArbolBinario
arbolcompleto(Arbolbinario,Arbolbinario,Elemento) → ArbolBinario
vacio(ArbolBinario) → booleano
raiz(ArbolBinario) → Elemento
subarbolIzquierdo(ArbolBinario) → ArbolBinario
subarbolDerecho(ArbolBinario) → ArbolBinario
Semántica: ∀ A1,A2 ∈ ArbolBinario, ∀ E ∈ Elemento:
vacio(arbolvacio) ⇒ cierto
vacio(arbolcompleto(A1,A2,E)) ⇒ falso
raiz(arbolvacio) ⇒ error
raiz(arbolcompleto(A1,A2,E)) ⇒ E
subarbolIzquierdo(arbolvacio) ⇒ error
subarbolIzquierdo(arbolcompleto(A1,A2,E)) ⇒ A1
subarbolDerecho(arbolvacio) ⇒ error
subarbolDerecho(arbolcompleto(A1,A2,E)) ⇒ A2
Metodología y Tecnología de la Programación
Tema 11. Árboles
45
11.5 TDA Árbol Binario basado en su Definición Recursiva
TDA Árbol Binario Inmutable: Métodos en Java.
Clase ArbolBinario
class ArbolBinario
Constructores
ArbolBinario()
ArbolBinario(ArbolBinario a1, ArbolBinario a2, Elemento e)
Métodos
boolean vacio()
Elemento raiz()
ArbolBinario subarbolIzquierdo()
ArbolBinario subarbolDerecho()
Metodología y Tecnología de la Programación
Tema 11. Árboles
46
11.5 TDA Árbol Binario basado en su Definición Recursiva
Utilización del Árbol Binario Inmutable
static public void preOrden(ArbolBinario a) {
if (a.vacio()) return;
System.out.println(a.raiz().valor());
preOrden(a.subarbolIzquierdo());
preOrden(a.subarbolDerecho());
}
static public void inOrden(ArbolBinario a) {
if (a.vacio()) return;
inOrden(a.subarbolIzquierdo());
System.out.println(a.raiz().valor());
inOrden(a.subarbolDerecho());
}
static public void postOrden(ArbolBinario a) {
if (a.vacio()) return;
postOrden(a.subarbolIzquierdo());
postOrden(a.subarbolDerecho());
System.out.println(a.raiz().valor());
}
Metodología y Tecnología de la Programación
Tema 11. Árboles
47
11.5 TDA Árbol Binario basado en su Definición Recursiva
Implementación del Árbol Inmutable
public class ArbolBinario {
private Elemento elemento;
private ArbolBinario izquierdo,derecho;
public ArbolBinario() {
elemento=null; izquierdo=null; derecho=null;
}
public ArbolBinario(ArbolBinario a1, ArbolBinario a2, Elemento e) {
elemento=e; izquierdo=a1; derecho=a2;
}
public boolean vacio() {
return((elemento==null)&&(izquierdo==null)&&(derecho==null));
}
public Elemento raiz() { return elemento; }
public ArbolBinario subarbolIzquierdo() { return izquierdo; }
public ArbolBinario subarbolDerecho() { return derecho; }
} // fin class ArbolBinario
Metodología y Tecnología de la Programación
Tema 11. Árboles
48
11.6 Árboles Parcialmente Ordenados: Colas de Prioridad
Operación
Árbol binario
inserta
O(n)
O(log n)
suprime
O(1)
O(log n)
Balanceado:
Estructura lineal
Todas las hojas tienen profundidad ⌊log n⌋ ó ⌊log n⌋ − 1.
Las hojas que faltan son las de más a la derecha posible.
Parcialmente ordenado:
La prioridad de un nodo no es menor que la de sus hijos.
⇒ En la raíz estará siempre el elemento con mayor prioridad.
Metodología y Tecnología de la Programación
Tema 11. Árboles
49
11.6 Árboles Parcialmente Ordenados: Colas de Prioridad
Representación por montículos
Vector:
A[1] contiene la raíz.
el hijo izquierdo de A[i] está, si existe, en A[2i].
el hijo derecho de A[i] está, si existe, en A[2i + 1].
el padre de A[i] está en A[i div 2], para i > 1.
Ventajas:
Se opera aritméticamente con los índices del vector para obtener, con
tiempos de ejecución constantes, las posiciones de los padres e hijos
izquierdo y derecho.
Desventajas:
Se requiere determinar a priori el número máximo de elementos en el
árbol.
Metodología y Tecnología de la Programación
Tema 11. Árboles
50
11.6 Árboles Parcialmente Ordenados: Colas de Prioridad
public class ColaPrioridad {
private Elemento elementos[];
private int prioridades[];
private int ultimo;
public ColaPrioridad() {
elementos = new Elemento[100];
prioridades = new int[100];
ultimo = 0;
}
public boolean vacia() { return (ultimo==0); }
public Elemento primero() { return elementos[1]; }
Metodología y Tecnología de la Programación
Tema 11. Árboles
51
11.6 Árboles Parcialmente Ordenados: Colas de Prioridad
Metodología y Tecnología de la Programación
Tema 11. Árboles
52
11.6 Árboles Parcialmente Ordenados: Colas de Prioridad
public void inserta(Elemento e, int prioridad) {
ultimo++;
int i = ultimo;
while(i>1) {
int padre = i/2;
if (prioridad<=prioridades[padre]) break;
elementos[i] = elementos[padre];
prioridades[i] = prioridades[padre];
i = padre;
}
elementos[i] = e;
prioridades[i] = prioridad;
}
Metodología y Tecnología de la Programación
Tema 11. Árboles
53
11.6 Árboles Parcialmente Ordenados: Colas de Prioridad
Metodología y Tecnología de la Programación
Tema 11. Árboles
54
11.6 Árboles Parcialmente Ordenados: Colas de Prioridad
public void suprime() {
Elemento e = elementos[ultimo];
int prioridad = prioridades[ultimo];
ultimo--;
int i = 1;
int hijo = 2*i;
while(hijo<=ultimo) {
if ((hijo<ultimo)&&(prioridades[hijo]<prioridades[hijo+1]))
hijo++;
if (prioridad>=prioridades[hijo]) break;
elementos[i] = elementos[hijo];
prioridades[i] = prioridades[hijo];
i = hijo;
hijo = 2*i;
}
elementos[i] = e;
prioridades[i] = prioridad;
}
} // fin class ColaPrioridad
Metodología y Tecnología de la Programación
Tema 11. Árboles
55
11.7 Árboles Binarios de Búsqueda: Conjuntos
Árbol binario de búsqueda
Los elementos del subárbol izquierdo de cualquier nodo son menores
que el elemento de dicho nodo.
Los elementos almacenados en el subárbol derecho de cualquier nodo
son mayores que el elemento almacenado en ese nodo.
Metodología y Tecnología de la Programación
Tema 11. Árboles
56
11.7 Árboles Binarios de Búsqueda: Conjuntos
Representación de Conjuntos:
inserta: inserta un elemento en un conjunto.
suprime: suprime un elemento de un conjunto.
pertenece: indica si un elemento dado pertenece o no a un conjunto).
⇒ Tiempo de ejecución promedio O(log n).
Otras operaciones: (Colas de Prioridad)
min: devuelve el elemento mínimo de un árbol.
suprime_min: elimina el elemento mínimo de un árbol.
max: devuelve el elemento máximo de un árbol.
suprime_max: elimina el elemento máximo de un árbol.
⇒ Tiempo de ejecución promedio O(log n).
⇒ Tiempo de ejecución peor caso O(n).
⇒ Tiempo de ejecución peor caso O(log n), si balanceado (árboles AVL,
árboles B, etc.)
Metodología y Tecnología de la Programación
Tema 11. Árboles
57
11.7 Árboles Binarios de Búsqueda: Conjuntos
public class Conjunto {
private Elemento elemento;
private Conjunto izquierdo, derecho;
public Conjunto() {
elemento = null;
izquierdo = null;
derecho = null;
}
public boolean vacio() {
return ((elemento==null)&&(izquierdo==null)&&(derecho==null));
}
public boolean pertenece(Elemento e) {
if (vacio()) return false;
else if (e.valor()>elemento.valor())
return derecho.pertenece(e);
else if (e.valor()<elemento.valor())
return izquierdo.pertenece(e);
return true;
}
Metodología y Tecnología de la Programación
Tema 11. Árboles
58
11.7 Árboles Binarios de Búsqueda: Conjuntos
public void inserta(Elemento e) {
if (vacio()) {
elemento = e;
izquierdo = new Conjunto();
derecho = new Conjunto();
}
else if (e.valor()>elemento.valor())
derecho.inserta(e);
else if (e.valor()<elemento.valor())
izquierdo.inserta(e);
}
Metodología y Tecnología de la Programación
Tema 11. Árboles
59
11.7 Árboles Binarios de Búsqueda: Conjuntos
Operación suprime:
1. Localiza la posición del nodo a suprimir:
⇒ Realizando una búsqueda similar a la realizada por la operación
miembro.
2. Elimina el nodo:
a) Si el nodo no tiene hijos ⇒ suprime el nodo.
b) Si tiene hijo derecho:
⇒ suprime el nodo.
⇒ sustituye el nodo por su hijo derecho.
c) Si tiene hijo izquierdo:
⇒ suprime el nodo.
⇒ sustituye el nodo por su hijo derecho.
d) Si tiene hijos derecho e izquierdo:
⇒ encuentra el menor elemento de los descendientes del hijo derecho (NOTA:
otra alternativa es encontrar el mayor elemento de los descendientes del hijo
izquierdo).
⇒ suprime el nodo de dicho elemento.
⇒ sustituye el nodo por dicho elemento.
Metodología y Tecnología de la Programación
Tema 11. Árboles
60
11.7 Árboles Binarios de Búsqueda: Conjuntos
public void suprime(Elemento e) {
if (e.valor()>elemento.valor()) derecho.suprime(e);
else if (e.valor()<elemento.valor())
izquierdo.suprime(e);
else if ((izquierdo.vacio())&&(derecho.vacio())) {
elemento = null;
derecho = null;
izquierdo = null; }
else if (izquierdo.vacio()) {
elemento = derecho.elemento;
izquierdo = derecho.izquierdo;
derecho = derecho.derecho; }
else if (derecho.vacio()) {
elemento = izquierdo.elemento;
derecho = izquierdo.derecho;
izquierdo = izquierdo.izquierdo; }
Metodología y Tecnología de la Programación
Tema 11. Árboles
61
11.7 Árboles Binarios de Búsqueda: Conjuntos
else {
Conjunto min = derecho;
while (!min.izquierdo.vacio()) min = min.izquierdo;
elemento = min.elemento;
min.elemento = min.derecho.elemento;
min.izquierdo = min.derecho.izquierdo;
min.derecho = min.derecho.derecho;
}
}
} // fin class Conjunto
Metodología y Tecnología de la Programación
Tema 11. Árboles
62