Download - Tema+4+ +Arboles
Tema 4 Árboles, Árbol Binario y Árbol Binario de Búsqueda
Objetivos o Aprender los conceptos básicos de árboles, árboles binarios y
árboles binarios de búsqueda. o Aprender los conceptos de recorridos de árboles y las operaciones
básicas sobre árboles binarios de búsqueda o Conocer los árboles equilibrados.
2
Bibliografía o Data structures, algorithms, and applications in Java, Sahni
(capítulos 12 y 15) o Estructuras de datos en Java, Weiss (capítulos 17 y 18) o Data Structures and Algorithms in Java (4th edition), Goodrich y
Tamassia (capítulo 10)
3
Contenidos 1. Conceptos de árboles 2. Árboles generales: representación 3. Árboles binarios: definición y propiedades 4. Recorridos de árboles binarios 5. Árboles binarios de búsqueda:
representación y operaciones básicas 6. La clase ABBMap 7. La clase ABBColaPrioridad 8. Árboles equilibrados
1. Conceptos de árboles Relación entre modelos e implementaciones
4
Tablas de dispersión
Árboles
Montículos Árboles binarios de búsqueda
Map/Diccionario Cola de prioridad
1. Conceptos de árboles Modelos lineales vs. jerárquicos o Las estructuras de datos lineales permiten describir
conjuntos de datos que mantienen entre ellos relaciones de sucesión (o de predecesión).
Ejemplo: lista de clientes de una empresa, trabajos en la cola de impresión, etc.
o Los Árboles permiten representar estructuras jerárquicas entre conjuntos de datos.
Ejemplo: estructura de directorios, árbol genealógico, expresiones aritméticas, etc.
5
1. Conceptos de árboles Estructuras jerárquicas o En ocasiones los datos de una colección mantienen
relaciones de tipo jerárquico, que no es posible expresar con una representación lineal.
Ejemplo 1: colección de directorios para las prácticas de EDA
6
$HOME
eda
librerias aplicaciones
estructurasDeDatos algoritmos letras hospital
1. Conceptos de árboles Estructuras jerárquicas o Ejemplo 2: el árbol que se muestra a continuación
representa la expresión aritmética (((a*b)+(c+d))*(e-f)):
7
* + -
* +
a b c d
e f
o Los Árboles son estructuras básicas para problemas de búsqueda y optimización (ajedrez, damas, sudoku, etc.)
1. Conceptos de árboles Conceptos básicos oUn árbol es una estructura jerárquica que se puede definir
por medio de un conjunto de nodos (uno de los cuales es distinguido como la raíz del árbol) y un conjunto de aristas tal que:
Cualquier nodo H, a excepción del raíz, está conectado por medio de una arista a un único nodo P. Se dice que P es el nodo padre y H el hijo
Un nodo sin hijos se denomina hoja
Un nodo que no es hoja se denomina nodo interno
El grado de un nodo es el número de hijos que tiene 8
1. Conceptos de árboles Ejemplo
9
Nodo raíz: A Nodos hoja: D, M, N, F, J, K, L Nodos internos: A, B, E, I, C, G, H
A
B C
D E F G H
I J K L
M N
nodo raíz padre hijo
1. Conceptos de árboles Longitud, profundidad y altura o En un árbol hay un único camino desde la raíz a cada nodo
o El número de aristas que componen un camino se denomina longitud del camino
oProfundidad de un nodo: longitud del camino que va desde la raíz a ese nodo
La profundidad de la raíz es 0
Se dice que todos los nodos que están a la misma profundidad están en el mismo nivel
oAltura de un nodo: longitud del camino que va desde ese nodo hasta la hoja más profunda bajo él
o Altura de un árbol = Altura de la raíz
10
1. Conceptos de árboles Ejercicio 1
11
a) ¿Cuántas aristas tiene un árbol con N nodos?
b) ¿Longitud de A a D? c) ¿Longitud de C a K? d) ¿Longitud de B a N? e) ¿Longitud de B a B? f) ¿Profundidad de A, B, C y F? g) ¿Altura de B, C, I, F y del
árbol?
A
B C
D E F G H
I J K L
M N
1. Conceptos de árboles Definición recursiva de árbol oUn árbol es:
o Un conjunto vacío (sin nodos ni aristas) , o
o Un nodo raíz y cero o más subárboles no vacíos donde cada una de sus raíces está conectada mediante una arista con el nodo raíz
12
7
3 10 4
11 2 1
Nodo raíz
Subárbol con raíz 3
Subárbol con raíz 4
Subárbol con raíz 10
2. Árboles generales Representación oRepresentación de árboles generales (número de hijos de
los nodos sin acotar:
o Listas (ordenadas) de hijos
o Hijo más a la izquierda – hermano derecho
o Con vectores y referencias al padre (mf-sets)
o Otras…
13
2. Árboles generales Representación o Ejemplo: listas ordenadas
de hijos:
14
raíz
2. Árboles generales Representación o Ejemplo: hijo más a la
izquierda-hermano derecho:
15
raíz
raíz
dato hijo izq.
her. der.
raíz
3. Árboles binarios Definición y propiedades oUn árbol binario es un árbol en el que ningún nodo puede
tener más de dos hijos (hijo izquierdo e hijo derecho)
16
oPropiedades: El número máximo de nodos del
nivel i es 2i
En un árbol de altura H, el número máximo de nodos es: ∑i=0..H2i = 2H+1 – 1
El número máximo de hojas es: (2H+1 - 1) - (∑i=0..H-12i) = 2H
El número máximo de nodos internos es: (2H+1-1) - (2H) = 2H - 1
Nivel A
B C
E D F
G
0
1
2
3
3. Árboles binarios Definición y propiedades oUn árbol binario es lleno si tiene todos sus niveles
completos
oPropiedades: sea H su altura y N su tamaño (número de nodos)
H = log2N
N = 2H+1 – 1
17
A
B C
E D F G N = 7 H = 2
3. Árboles binarios Definición y propiedades oUn árbol binario completo tiene todos sus niveles
completos, a excepción quizás del último en el cuál todas las hojas están tan a la izquierda como sea posible
oPropiedades: sea H su altura y N su tamaño (número de nodos)
H ≤ log2N → es un árbol equilibrado
2H ≤ N ≤ 2H+1 – 1
18
A
B C
D
N = 4 H = 2
Nota: un árbol es equilibrado si los subárboles izquierdo y derecho de cualquier nodo tienen alturas que difieren como mucho en 1
4. Operaciones de recorrido Recorrido en anchura o En un recorrido en anchura (por niveles) de un árbol
binario los nodos se visitan nivel a nivel y, dentro de cada nivel, de izquierda a derecha
19
A
B C
E D F
G
Por niveles: ABCDEFG
4. Operaciones de recorrido Recorridos en profundidad o En profundidad: los nodos se visitan bajando por las ramas
del árbol Pre-Orden:
1º) raíz, 2º) sub-árbol izquierdo, 3º) sub-árbol derecho In-Orden:
1º) sub-árbol izquierdo, 2º) raíz, 3º) sub-árbol derecho Post-Orden:
1º) sub-árbol izquierdo, 2º) sub-árbol derecho, 3º) raíz
20
A
B C
E D F
G
Pre-Orden: ABDEGCF In-Orden: DBGEACF Post-Orden: DGEBFCA
4. Operaciones de recorrido Ejercicio 2 oMuestra el resultado de recorrer en pre-orden, in-orden,
post-orden y por niveles el siguiente árbol:
21
+
5 *
2 -
/ 1
8 4
5. Árboles binarios de búsqueda Conceptos básicos o Estructura de datos muy versátil, sirve para la
implementación de diccionarios y de colas de prioridad
o Es una generalización de la búsqueda dicotómica
o Soporta eficientemente las operaciones de búsqueda, localizar el mínimo, el máximo, el predecesor y el successor
o También soporta eficientemente las operaciones de inserción y borrado
22
5. Árboles binarios de búsqueda Definición oUn árbol binario es de búsqueda si:
Los datos de su subárbol izquierdo son menores que el raíz
Los datos de su subárbol derecho son mayores que el raíz
Los subárboles izquierdo y derecho también son árboles binarios de búsqueda
o Si se imprime en in-orden resulta una secuencia ordenada
23
7
2 9
5 1
3
Árbol Binario de Búsqueda:
7
2 9
5 1
8 3
Árbol Binario (que no es de Búsqueda):
5. Árboles binarios de búsqueda Representación enlazada
24
NodoABB dato
izq der
ABB
raíz
NodoABB NodoABB
5. Árboles binarios de búsqueda La clase NodoABB
25
package librerias.estructurasDeDatos.jerarquicos; class NodoABB<E> E dato; // Dato almacenado en el nodo NodoABB<E> izq, der; // Nodos hijo // Constructores NodoABB(E dato, NodoABB<E> izquierdo, NodoABB<E> derecho) this.dato = dato; this.izq = izquierdo; this.der = derecho; NodoABB(E dato) this(dato, null, null);
5. Árboles binarios de búsqueda La clase ABB
26
package librerias.estructurasDeDatos.jerarquicos; public class ABB<E extends Comparable<E>> // Atributos protected NodoABB<E> raiz; protected int talla; /** Constructor de un ABB vacio **/ public ABB() raiz = null; talla = 0; …
nodo raíz del árbol número de nodos del árbol
5. Árboles binarios de búsqueda Búsqueda en un ABB
27
// Busca el dato x en el ABB y lo devuelve. // Si no lo encuentra devuelve null public E recuperar(E x) NodoABB<E> nodo = raiz; while (nodo != null) int resC = x.compareTo(nodo.dato); if (resC == 0) return nodo.dato; nodo = resC < 0 ? nodo.izq : nodo.der; return null;
7
2 9
5 1
3
Ejemplo: búsqueda del dato 3
5. Árboles binarios de búsqueda Ejercicio
28
o Ejercicio 3: si se busca el número 363 en un ABB que contiene números del 1 al 1000 ¿Cuál de las siguientes secuencias de nodos no puede ser la secuencia de nodos examinada?
a) 2, 252, 401, 398, 330, 344, 397, 363 b) 924, 220, 911, 244, 898, 258, 362, 363 c) 925, 202, 911, 240, 912, 245, 363 d) 2, 399, 387, 219, 266, 382, 381, 278, 363 e) 935, 278, 347, 621, 299, 392, 358, 363
5. Árboles binarios de búsqueda Inserción en un ABB
29
// Inserta el dato x en el ABB sin permitir repetidos public void insertar(E x) NodoABB<E> ant = null, nuevo, nodo = raiz; int resC = -1; while (nodo != null && ((resC = x.compareTo(nodo.dato)) != 0)) ant = nodo; nodo = resC < 0 ? nodo.izq: nodo.der; if (nodo == null) nuevo = new NodoABB<E>(x); if (raiz == null) raiz = nuevo; else if (resC < 0) ant.izq = nuevo; else ant.der = nuevo; talla++;
5. Árboles binarios de búsqueda Inserción en un ABB
30
o Ejemplo: insertar el 6
o El método para actualizar un dato del ABB sería muy similar al anterior:
7
2 9
5 1
3 6
public E actualizar(E x) E res = null; … // Igual que insertar else // Si el dato ya existe res = nodo.dato; nodo.dato = x; return res;
5. Árboles binarios de búsqueda Mínimo y máximo en un ABB
31
o El mínimo en un ABB no tiene hijo izquierdo y no pertenece a ningún subárbol derecho de ningún nodo.
// Devuelve el mínimo public E recuperarMin() NodoABB<E> nodo = raiz; if (nodo == null) return null; while (nodo.izq != null) nodo = nodo.izq; return nodo.dato; o El máximo es el caso simétrico.
5. Árboles binarios de búsqueda Borrado del mínimo en un ABB
32
o El borrado del mínimo se diseña de forma distinta para su posterior reutilización en el método eliminar:
public E eliminarMin() if (raiz == null) return null; return eliminarMin(raiz, null).dato; protected NodoABB<E> eliminarMin(NodoABB<E> nodo, NodoABB<E> padre) NodoABB<E> ant = padre; while (nodo.izq != null) ant = nodo; nodo = nodo.izq; if (ant == null) raiz = raiz.der; else if (ant.izq == nodo) ant.izq = nodo.der; else ant.der = nodo.der; talla--; return nodo;
5. Árboles binarios de búsqueda Borrado en un ABB
33
Posibles casos:
a) El nodo a eliminar no tiene hijos Ejemplo: el 3 (se elimina sin problemas)
7
2 9
5 1
3
b) El nodo a eliminar tiene un hijo Ejemplo: el 5 Su hijo ocupa su posición:
7
2 9
3 1
c) El nodo a eliminar tiene dos hijos Ejemplo: el 2 El mínimo de su subárbol derecho ocupa su posición:
7
3 9
5 1
5. Árboles binarios de búsqueda Borrado en un ABB
34
public E eliminar(E x) // Elimina el nodo que contiene x E res; NodoABB<E> nodo = raiz, ant = null; int resC = -1; while (nodo!=null && ((resC=x.compareTo(nodo.dato))!=0)) ant = nodo; nodo = resC < 0 ? nodo.izq : nodo.der; if (nodo == null) return null; // No encontrado res = nodo.dato; if (nodo.izq != null && nodo.der != null) // 2 hijos nodo.dato = eliminarMin(nodo.der, nodo).dato; else // 1 hijo o ninguno NodoABB<E> aux = nodo.izq != null ? nodo.izq : nodo.der; if (ant == null) raiz = aux; else if (ant.izq == nodo) ant.izq = aux; else ant.der = aux; talla--; return res;
5. Árboles binarios de búsqueda Recorridos en profundidad o La forma natural de implementar los recorridos en
profundidad es recursiva:
35
public String preOrden() // Lanzadera return preOrden(raiz); private String preOrden(NodoABB<E> actual) if (actual == null) return ″″; return actual.dato.toString() + ″\n″ + preOrden(actual.izq) + preOrden(actual.der);
o Los métodos para imprimir en Post-Orden y en In-Orden son muy similares (sólo cambia el orden de las instrucciones)
5. Árboles binarios de búsqueda Recorrido en anchura o El recorrido por niveles, al ser iterativo, utiliza una Cola como
estructura auxiliar
36
public String porNiveles() if (raiz == null) return ""; Cola<NodoABB<E>> q = new ArrayCola<NodoABB<E>>(); q.encolar(raiz); String res = ""; while (!q.esVacia()) NodoABB<E> actual = q.desencolar(); res += actual.dato.toString() + "\n"; if (actual.izq != null) q.encolar(actual.izq); if (actual.der != null) q.encolar(actual.der); return res;
5. Árboles binarios de búsqueda Cálculo del sucesor/predecesor o Si un nodo tiene subárbol derecho, el sucesor de dicho nodo
es el mínimo de su subárbol derecho
o Sino, el sucesor es el ascendiente por la derecha más cercano
o El sucesor de un nodo equivale al siguiente nodo que se obtendría en un recorrido in-orden del árbol:
37
5
2 7
3 1 9
sucesor(5) = 7 sucesor(1) = 2 sucesor(3) = 5 sucesor(9) = null
5. Árboles binarios de búsqueda Cálculo del sucesor/predecesor
/** Obtiene el sucesor de e en un ABB. * Si no existe tal sucesor, devuelve null para * advertirlo */ public E sucesor(E e) E sucesor = null; NodoABB<E> aux = this.raiz; while (aux != null) int resC = aux.dato.compareTo(e); if (resC > 0) sucesor = aux.dato; aux = aux.izq; else aux = aux.der; return sucesor;
38
5. Árboles binarios de búsqueda Coste de las operaciones
39
Θ(1)
Θ(N)
minimo ()
Θ(N)
Θ(1)
Θ(N)
Θ(N)
buscar(x)
Θ(1)
Θ(N)
eliminarMin()
LEG Ordenada
Lista Enlazada / Array
Coste promedio EDA
Θ(log N) Θ(log N) Θ(log N) Θ(log N) ABB
Array Ordenado Θ(log N) Θ(N) Θ(1) Θ(1)
insertar(x)
o El coste de las operaciones en un ABB está en función de la altura del árbol (h)
o La altura h está entre Ω(log2n) y O(n)
o En el peor caso (ABB desbalanceado), los costes son lineales
5. Árboles binarios de búsqueda Ejercicios
40
o Ejercicio 4: Diseñar un método que devuelva el dato que está en el nodo padre de un elemento dado. Indica el coste temporal del método.
o Ejercicio 5: Diseña un método que devuelva el nivel del nodo que contiene el dato x (se supone que no hay datos duplicados)
o Ejercicio 6: Diseña un nuevo constructor para la clase ABB que, partiendo de un ABB vacío, inserte los datos de un vector de forma que el ABB resultante quede equilibrado.
5. Árboles binarios de búsqueda Ejercicios
41
o Ejercicio 7: Diseñar los siguientes métodos en la clase ABB: Obtener el número total de hojas del árbol Visualizar los datos de los nodos del nivel k del árbol Calcular la altura del árbol
o Ejercicio 8: Diseña la clase ABBInteger como un ABB que trabaja con datos de tipo Integer, y añade los siguientes métodos: Un método que obtenga la suma de todos los elementos que
sean mayores o iguales a un valor entero dado Un método que cambie el signo de todos los datos del árbol. El
ABB debe seguir manteniendo la propiedad de orden
5. Árboles binarios de búsqueda Ejercicios
42
o Ejercicio 9: Diseñar un método en un ABB para eliminar todos los elementos menores que uno dado.
o Ejercicio 10: Diseña en la clase ABB un método para obtener el predecesor de un dato x dado El predecesor de un nodo es el máximo de su subárbol izquierdo
(si tiene) o, en caso contrario, el ascendiente por la izquierda más cercano.
6. La clase ABBMap Propuesta de implementación
43
o El modelo Map permite realizar búsquedas por clave para obtener el valor asociado a dicha entrada
oUna entrada es un par (clave, valor)
oNo se permiten elementos repetidos, es decir, dos entradas con la misma clave
⇒ Para implementar la interfaz Map necesitamos definir la clase EntradaDic
public interface Map<C, V> V insertar(C c, V v); V eliminar(C c); V recuperar(C c); boolean esVacio(); int talla(); ListaConPI<C> claves();
6. La clase ABBMap La clase EntradaMap
44
class EntradaMap<C extends Comparable<C>,E> implements Comparable<EntradaMap<C,E>> C clave; E valor; public EntradaMap(C c, E e) clave = c; valor = e; public EntradaMap(C c) this(c, null); public boolean equals(Object x) return ((EntradaMap<C,E>)x).clave.equals(this.clave); public int compareTo(EntradaMap<C,E> x) return this.clave.compareTo(x.clave); public String toString() return this.clave + " => " + this.valor;
6. La clase ABBMap Propuesta de implementación
45
public class ABBMap<C extends Comparable<C>,V> implements Map<C,V> private ABB<EntradaMap<C,V>> abb; public ABBMap() abb = new ABB<EntradaMap<C,V>>(); public V insertar(C c, V v) EntradaMap<C,V> nuevo = new EntradaMap<C,V>(c,v); EntradaMap<C,V> ant = abb.actualizar(nuevo); return ant == null ? null : ant.valor; public V eliminar(C c) EntradaMap<C,V> ant = abb.eliminar( new EntradaMap<C,V>(c)); return ant == null ? null : ant.valor; ...
7. La clase ABBColaPrioridad Propuesta de implementación
46
o Los métodos eliminarMin y recuperarMin se heredan tal cual de la clase ABB
o Es necesario definir el método esVacia ya que cambia de género (en ABB se llama esVacio)
oHace falta sobrescribir el método insertar para permitir la inserción de elementos duplicados
public interface ColaPrioridad<E extends Comparable<E>> void insertar(E e); E eliminarMin(); E recuperarMin(); boolean esVacia();
7. La clase ABBColaPrioridad Propuesta de implementación
47
public class ABBColaPrioridad<E extends Comparable<E>> extends ABB<E> implements ColaPrioridad<E> public boolean esVacia() return super.esVacio(); public void insertar(E x) NodoABB<E> ant = null, nodo = raiz; int resC = -1; while (nodo != null) resC = x.compareTo(nodo.dato); ant = nodo; nodo = resC < 0 ? nodo.izq: nodo.der; NodoABB<E> nuevo = new NodoABB<E>(x); if (raiz == null) raiz = nuevo; else if (resC < 0) ant.izq = nuevo; else ant.der = nuevo; talla++;
8. Árboles equilibrados Introducción
48
o Los árboles balanceados son estructuras de datos basadas en árboles que incluyen información y/o operaciones adicionales para conseguir un equilibrio en los árboles
o Su funcionamiento se basa en efectuar rotaciones: se intercambian nodos y subárboles en un árbol binario de búsqueda para conseguir otro equivalente
Rotación a la derecha
Rotación a la izquierda
8. Árboles equilibrados Los árboles balanceados más conocidos
49
oÁrboles AVL Almacenan el factor de equilibrio en cada nodo
Permanecen balanceados en todo momento
oÁrboles rojo-negro Cada nodo tiene un atributo indicando su color (rojo o negro)
Al igual que los AVL, permanecen equilibrados en todo momento
o Splay-trees Suben (mediante rotaciones) el elemento insertado/buscado a la raíz y
con ello se mantiene balanceado
oDay–Stout–Warren (DSW) Consigue balancear el ABB (esté como esté previamente) en O(n)