Story Transcript
Tema 8- El Árbol Binario de Búsqueda
Duración: 2 semanas aprox. Índice general: 1. El problema de la Búsqueda sobre una Colección de Datos: soluciones y costes sobre diferentes Representaciones 2. Árbol Binario de Búsqueda (ABB): definición, Representación, Equilibrio y coste de sus operaciones 3. Implementación en Java del ABB: la clase ArbolBinarioBusqueda 4. Implementación de las EDA Diccionario y Cola de Prioridad según un ABB: las clases ABBDiccionario y ABBColaPrioridad 5. El problema de la Selección, otra vez
1
Bibliografía básica:
9
Weiss, M.A. Estructuras de datos en Java. Adisson-Wesley, 2000. Capítulo 18, apartados del 1 al 3, ambos inclusive.
9
Wiener, R., Pinson, L.J. Fundamentals of OOP and Data Structures in Java. Cambridge University Press. 2000. Capítulo 15, apartados 3, 4 y 9
3
1
El Problema de la Búsqueda de un Dato x en una Colección de numDatos Sobre una Representación Lineal de la Colección: en el Peor de los Casos es proporcional a numDatos
• Si los Datos NO están ordenados, en el Peor de los
casos es proporcional a numDatos
• Si los Datos están ordenados, la Búsqueda Dicotómica
permite en el Peor de los Casos una cota logarítmica, pero la inserción se encarece (es lineal)
Búsqueda Estática ¿ y si la Aplicación/Modelo se basa en la Búsqueda 4?
El Problema de la Búsqueda de un Dato x en una Colección de numDatos La operación básica de una Aplicación/Modelo Orientado a la Búsqueda es buscar un Dato x dado. Para hacerla eficiente, la Representación de la Colección de Datos que manipula debe mantenerse ordenada de alguna forma 1. insertar(x) y eliminar(x) sólo difieren de buscar(x) en la Resolución de la Búsqueda 2. buscar(x), insertar(x) y eliminar (x) son operaciones del núcleo del Modelo que NO difieren en coste Búsqueda Dinámica 5
2
Aplicaciones Orientadas a la Búsqueda: Modelo Diccionario 9 La operación básica del Diccionario es buscar en una Colección de Entrada’s una dada x:
buscar(x) consiste en realidad en buscar la Clave de x para devolver su Valor ⇒ Búsqueda Por Nombre o Clave
insertar(x) throws ElementoRepetido
9 La Búsqueda en un Diccionario es Dinámica 9 Una Implementación adecuada del Diccionario consigue que sus operaciones se ejecuten en un tiempo independiente de su número de Entrada’s 6
Aplicaciones Orientadas a la Búsqueda: Modelo Cola de Prioridad 9 La operación básica de la Cola de Prioridad es buscar el Dato Mínimo, con menor Prioridad, de una Colección
buscarMin() y eliminarMin() no requieren un requisito de Ordenación de los Datos tan fuerte como el de buscar(x) y eliminar(x)
Al insertar(x) puede estar repetido
9 La Búsqueda en una Cola de Prioridad es Dinámica 9 Una Implementación adecuada de la Cola de Prioridad consigue que excepto eliminarMin() las demás operaciones se ejecuten en un tiempo promedio constante 7
3
El Problema de la Búsqueda sobre una Colección de Datos: soluciones y costes sobre diferentes Representaciones buscar(x)
insertar(x)
buscarMin()
eliminarMin()
Θ(N)
Θ(1)
Θ(N)
Θ(N)
LEIOrdenada
Θ(N)
Θ(N)
Θ(1)
Θ(1)
ArbolBinario
Θ(N)
--
Θ(N)
Θ(N)
Θ(N)
Θ(1)
Θ(1)
Θ(log N)
Coste medio Representación
LEI
MonticuloBinario
Para ser más eficiente …. ¿ Qué características tendría que tener la Representación de la EDA Orientada a la Búsqueda? 8
Para ser más eficiente …. ¿ Qué características tendría que tener la Representación de una EDA Orientada a la Búsqueda? 1. La única Estructura de Datos que puede proporcionar cotas de tiempo logarítmicas es el Árbol Binario Equilibrado ¾
PROPIEDAD ESTRUCTURAL
2. Si un Árbol Binario Equilibrado cumple la propiedad de la Búsqueda Ordenada, buscar(x) es logarítmica, al igual que el resto de operaciones ¾
PROPIEDAD DE ORDENACIÓN
Árbol Binario de Búsqueda (ABB) 9
4
Definición de Árbol Binario Equilibrado Árbol Binario en el que la diferencia de Alturas de los Hijos Derecho e Izquierdo es como máximo 1 insertar(new Integer(1)) ;
12 8 4 2
16 10
8
14
4
6
2
Árbol Binario Equilibrado
12 16
10
14
6
Árbol Binario
1
10
El Árbol Binario de Búsqueda (ABB) como Representación de una EDA Orientada a la Búsqueda Un Árbol Binario es de Búsqueda (o cumple la propiedad de Búsqueda Ordenada) si: 1. 2. 3.
todos que el todos que el
los Datos de su subÁrbol Izquierdo son menores que ocupa su Raíz los Datos de su subÁrbol Derecho son mayores que ocupa su Raíz
los subÁrboles Izquierdo y Derecho también son ABB 7
7 2 1
5 3
2
9
Árbol Binario de Búsqueda
1
9
Árbol Binario
5 3
8 11
5
Propiedades del Árbol Binario de Búsqueda (ABB)
• Si se imprime en InOrden .....
7
123579 2
resulta una Secuencia Ordenada • El Dato mínimo se encuentra en ..... el último Nodo Izquierdo de su primera Rama
1
9 5
3
• El Dato máximo se encuentra en ..... el último Nodo Derecho de su última Rama
12
Cuestiones propuestas: A partir de las definiciones y propiedades anteriores, respóndanse las siguientes cuestiones: 1. ¿dónde se encuentra el sucesor de un Dato dado x de un ABB? 2. ¿y el predecesor de x? Responder a las cuestiones planteadas sobre los siguientes ejemplos puede resultar útil: 7 2 1
5 3
¿dónde se encuentra el sucesor del 2 en este ABB? 9 ¿y su predecesor? ¿dónde se encuentra el sucesor del 9 en este ABB? ¿y su predecesor? ⇒ SIGUE 13
6
15 6 3 2
18 7
4
17
20
13 9
¿dónde se encuentra el sucesor del 15 en este ABB? ¿y su predecesor? ¿dónde se encuentra el sucesor del 13 en este ABB? ¿y su predecesor? ¿dónde se encuentra el sucesor del 9 en este ABB? ¿y su predecesor?
Operaciones sobre un ABB y su coste: buscar(x) Búsqueda del Nodo del ABB que contiene a x Tbuscar (N)∈ O(H) buscar(x) = 9
=34 buscar(x) = 7 2 1
7 9
2
5
1
3
9 5
3
4 Comparaciones
2 Comparaciones
esfuerzo de Comparación(x) = 1+Nivel de x
15
7
Operaciones sobre un ABB y su coste: TeMC (N)∈ Θ(N) eMC() 7 2 1
9 5
3
¿ esfuerzo Medio de Comparación (eMC) ? eMC = ∑Nivel=0..H (nº Nodos de Nivel) (1+ Nivel) _________________________________ N 16
Operaciones sobre un ABB y su coste: insertar(x) 1. Búsqueda del lugar de inserción de x en el ABB
2. Resolución de la Búsqueda: insertar en tal lugar el nuevo Nodo que contiene a x
Tinsertar (N)∈ O(H) insertar(x) = 6
insertar(x) = 10
7
7 2 1
5 3
2
9 10
1
9 5
3
¿ Se puede calcular el esfuerzo Medio de Comparación conforme se van insertando los Datos ?
8
Operaciones sobre un ABB y su coste: buscarMin() y buscarMax() Recorrido de una determinada Rama del ABB
TbuscarMin/Max (N)∈ Θ(H)
buscarMin()
buscarMax()
7
7
2 1
9
2
5
1
3
9 5
3
Operaciones sobre un ABB y su coste: eliminar(x) 1. Búsqueda del Nodo que contiene a x 2. Resolución de la Búsqueda: eliminarlo
Teliminar (N)∈ O(H) eliminar(x) = 1
eliminar(x) = 5
7 2 null 1
eliminar(x) = 2
7 9
2
5
1
3
7 9
5 3
2 3 1
9
buscarMin() 5
null 3
o Caso 3: eliminar un o Caso 1: eliminar un o Caso 2: eliminar Nodo n con 0 Hijos un Nodo n con 1 Hijo Nodo n con 2 Hijos n = null
⇓
Caso único:!= null)n.dato=buscarMin(n.der).dato; n = (n.izq ? n.izq: n.der;
n = ( n.izq != null ) ? n.izq: n.der;
n.der = ¿ eliminarMin(n.der);
?
9
Operaciones sobre un ABB y su coste: eliminarMin() y eliminarMax() Recorrido de una determinada Rama del ABB para borrar su último Nodo
TeliminarMin/Max (N)∈ Θ(H) 7 2 1
9 5
3
Equilibrado, Altura y eMC de un ABB Ejemplo: inicializar un Árbol Binario de Búsqueda con la secuencia 7, 2, 9, 1, 5, 3 5, 7, 2, 9, 1, 3 1, 2, 3, 5, 7, 9 7 2 1
9 5
1
5 2 1
2
7 3
9
3
¡¡¡ cuanto más Equilibrado el ABB menor será su Altura, su eMC y el coste de sus operaciones !!!
3 5 7 9 21
10
Equilibrado, Altura y eMC de un ABB: talla, instancias significativas y coste En un ABB Equilibrado de altura H y tamaño N H ≈ log N
⇒ Toperacion(N) ∈ Ο(log N)
En un ABB desEquilibrado de altura H y tamaño N H=N-1
⇒ Toperacion(N) ∈ Ο(N)
SOLUCIÓN : ABB’s Bien Equilibrados ó ABB’s a los que se añade una Condición de Equilibrio tal que H ≈ log N Ello obliga a realizar modificaciones en: 9 la estructura de la clase correspondiente (atributos) 9 las operaciones de inserción y eliminación 22
El Problema de la Búsqueda sobre una Colección de Datos: soluciones y costes sobre diferentes Representaciones Coste medio buscar(x) Representación
insertar(x)
buscarMin()
eliminarMin()
Θ(N)
Θ(1)
Θ(N)
Θ(N)
LEI Ordenada
Θ(N)
Θ(N)
Θ(1)
Θ(1)
Arbol Binario
Θ(N)
--
Θ(N)
Θ(N)
Θ(N)
Θ(1)
Θ(1)
Θ(log N)
Θ(log N)
Θ(log N)
Θ(log N)
Θ(log N)
LEI
Monticulo Binario ABB
23
11
El Problema de la Búsqueda sobre una Colección de Datos: soluciones y costes sobre diferentes Representaciones Coste peor buscar(x) Representación
insertar(x)
buscarMin()
eliminarMin()
LEI
Ο(N)
Ο(1)
Ο(N)
Ο(N)
LEI Ordenada
Ο(N)
Ο(N)
Ο(1)
Ο(1)
Arbol Binario
Ο(N)
--
Ο(N)
Ο(N)
Ο(N)
Ο(log N)
Ο(1)
Ο(log N)
Ο(N)
Ο(N)
Ο(N)
Ο(N)
Monticulo Binario ABB
24
Representación de un ABB Árbol Binario, donde un Nodo define al Árbol del que es Raíz ¾ un Árbol Binario TIENE UN Nodo Binario Raíz ¾ un Árbol Binario TIENE UN numTotalInserciones y numTotalComparaciones tal que: eMC = numTotalComparaciones / numTotalInserciones
25
12
Ejemplo propuesto
Si se busca el número 363 en un ABB que contiene números del 1 al 1000 ¿cuál de las siguientes secuencias no puede ser la secuencia de Nodos examinada?
2,252,401,398,330,344,397,363
924,220,911,244,898,258,362,363
925,202,911,240,912,245,363
2,399,387,219,266,382,381,278,363
935,278,347,621,299,392,358,363
26
Ejemplo propuesto: a partir de ArbolBinarioBusqueda, diseñar las clases ABBDiccionario y ABBColaPrioridad para que implementen, respectivamente, Diccionario y ColaPrioridad mediante un ABB
13
Ejemplo propuesto: a partir de ArbolBinarioBusqueda, diseñar las clases ABBDiccionario y ABBColaPrioridad para que implementen, respectivamente, Diccionario y ColaPrioridad mediante un ABB ArbolBinarioBusqueda NO implementa ninguna interfaz. Sus métodos son: los public comunes a cualquier Árbol Binario, que por tanto lanzan sus homónimos de NodoBinario
los protected sobre un Nodo Binario de Búsqueda, que serán lanzados (re-utilizados) por los métodos public de clases que implementan Modelos específicos, como
1. ABBDiccionario, extends ArbolBinarioBusqueda implements Diccionario 2. ABBColaPrioridad, extends ArbolBinarioBusqueda implements ColaPrioridad
Cuestiones: 1. ¿ Cuál de los dos métodos de inserción de ArbolBinarioBusqueda se lanza en ABBDiccionario ? ¿ y enABBColaPrioridad ? 2. Desde una aplicación que utiliza un Diccionario, ¿es correcto ejecutar Diccionario d = new ArbolBinarioBusqueda()? ¿ Por qué ?
La clase ArbolBinarioBusqueda: atributos y métodos públicos sobre this ABB package jerarquicos; import excepciones.*; public class ArbolBinarioBusqueda{ protected NodoBinario raiz; protected long numTotalInserciones, numTotalComparaciones; public ArbolBinarioBusqueda() { raiz = null; numTotalInserciones = numTotalComparaciones = 0; } public boolean esVacio() { return (raiz == null);} public double eMC(){ return ((double)numTotalComparaciones)/numTotalInserciones; } public int tamaño(){ return NodoBinario.tamaño(this.raiz); } public int altura(){ return NodoBinario.altura(this.raiz); } public String toString(){ if ( raiz != null ) return raiz.imprimirInOrden(); else return "*"; } public String imprimirPorNiveles(){ if ( raiz != null ) return raiz.imprimirPorNiveles(); else return "*";}
14
La clase ArbolBinarioBusqueda: métodos protected, para la Herencia, sobre la Raíz de this ABB, i.e. sobre un Nodo Binario de Búsqueda protected NodoBinario buscar(Object x, NodoBinario n) throws ElementoNoEncontrado {....} protected NodoBinario insertar(Object x, NodoBinario n) throws ElementoDuplicado {....} protected NodoBinario insertarTodos(Object x, NodoBinario n) {....} protected NodoBinario buscarMin(NodoBinario n) {....} protected NodoBinario buscarMax(NodoBinario n) {....} protected NodoBinario eliminarMin(NodoBinario n) {....} protected NodoBinario eliminarMax(NodoBinario n) {....} protected NodoBinario eliminar(Object x, NodoBinario n) throws ElementoNoEncontrado {....} ... 30
La clase ArbolBinarioBusqueda: diseño Recursivo del método protected buscar protected NodoBinario buscar(Object clave, NodoBinario n) throws ElementoNoEncontrado { /** Búsqueda Recursiva de clave en un Nodo Binario de Búsqueda ⇒ * Búsqueda Recursiva Binaria */ casoBase(talla(n)) return soluciónBase(talla(n)); buscar ”+clave); if ( n == null ) throw )new ElementoNoEncontrado(“al else { int resC = ((Comparable)n.dato).compareTo(clave); if ( mejorCaso() ( resC == 0 ) return n; ) return soluciónMejorCaso(); else {if ( resC > 0 ) return buscar(clave, n.izq) ; // Llamadas recursivas else soluciónPeorCaso(); return buscar(clave, n.der); return }
} Ejercicio propuesto: diseño Iterativo del método
protected buscar
15
La clase ArbolBinarioBusqueda: diseño Recursivo del método protected insertar protected NodoBinario insertar(Object clave, NodoBinario n) throws ElementoNoEncontrado { /** 1.- Búsqueda Binaria con éxito del lugar de inserción de clave en n; * 2.- Resolución: insertar allí el nuevo Nodo que contiene a clave */ if ( n == null ) return )new NodoBinario(clave); casoBase(talla(n)) return soluciónBase(talla(n)); else { int resC = ((Comparable)n.dato).compareTo(clave); if ( mejorCaso() ( resC == 0 ) throw new ElementoDuplicado(“al ...”); ) return soluciónMejorCaso(); else { if
( resC > 0 ) n.izq = insertar(clave, n.izq) ;
else // Llamadas recursivas n.der = insertar(clave, n.der); return n; return soluciónPeorCaso(); }
Ejercicios propuestos:
}
• diseño Iterativo del método protected insertar • diseño Recursivo del método insertarTodos
La clase ArbolBinarioBusqueda: diseño Recursivo del método protected eliminar protected NodoBinario eliminar(Object clave, NodoBinario n) throws ElementoNoEncontrado{ if ( n == null ) throw new ElementoNoEncontrado(“al eliminar ..”); int resC = ((Comparable)n.dato).compareTo(clave) ; if ( resC < 0 ) else if ( resC > 0 )
n.der = eliminar(clave, n.der); n.izq = eliminar(clave, n.izq);
else { if ( n.izq != null && n.der != null ) { /** clave encontrada en Nodo n: eliminarlo */ n.dato = buscarMin(n.der).dato;
}
n.der = eliminarMin(n.der); } else n = ( n.izq != null ) ? n.izq: n.der;
return n; }
16
La clase ArbolBinarioBusqueda: diseño de los método protected buscarMin y eliminarMin /**SII esVacio() */ protected NodoBinario buscarMin(NodoBinario n) { if (n.izq != null ) n.izq = buscarMin(n.izq) ; return n; } /**SII esVacio() */ protected NodoBinario eliminarMin( NodoBinario n ) { if (n.izq != null ) n.izq = eliminarMin(n.izq) ; else n = n.der; return n; }
Ejercicios propuestos:
• diseño Iterativo de los métodos protected buscarMin y
eliminarMin • diseño Recursivo e Iterativo de buscarMax y eliminarMax
Ejemplos propuestos en la Práctica 4
Añadir a la clase ArbolBinarioBusqueda dos métodos que dado un Objeto x encuentren, respectivamente, el sucesor y predecesor de x en el ABB ¿Cómo tiene que ser el Objeto x?
35
17
El Problema de la Selección, otra vez Cálculo del k-ésimo Dato más pequeño de una Colección si laN,Colección se representa sobre un array dea)talla 1≤k≤N Ejemplo: 7,2,9,1,5,3, k = 3 y N = 6 7
2
/** Solución 1 */
9
1
5
3
TseleccionDirectaKmedio(N) ∈ O(k*N)
public static void seleccionDirectaK(Object v[], int k){ for ( int i = 0; i < k; i++ ) { int j = posMin(v,i,N-1); intercambiar(v,i, j); } }
/** k-ésimo Mínimo de la Colección en v[k-1] */ 1 2 3 7 5 9
El Problema de la Selección, otra vez Cálculo del k-ésimo Dato más pequeño de una Colección si laN,Colección se representa sobre un array dea)talla 1≤k≤N Ejemplo: 7,2,9,1,5,3, k = 3 y N = 6
7
2
/** Solución 2 */
9
1
5
3
TquickSortmedio(N) ∈ O(N*logN)
public static void quickSort(Object heapSort(Objectv[]){ v[]){ .... }
/** k-ésimo Mínimo de la Colección en v[k-1] */ 1 2 3 7 5 9
18
El Problema de la Selección, otra vez Cálculo del k-ésimo Dato más pequeño de una Colección si laN,Colección se representa sobre un array dea)talla 1≤k≤N Ejemplo: 7,2,9,1,5,3, k = 3 y N = 6 7
2
9
1
5
3
TseleccionRapidamedio(N) ∈ O(N)
/** Solución 3 */
public static void seleccionRapida(Object v[], int k, int izq, int der){ if ( izq < der ){ int indP = particion(v, izq, der); if ( k-1 < indP ) seleccionRapida(v, k, izq, indP-1); else if ( k-1 > indP ) seleccionRapida(v, k,indP+1, der); }
}
/** k-ésimo Mínimo de la Colección en v[k-1] */ 1 2 3 7 5 9
El Problema de la Selección, otra vez
Cálculo del k-ésimo Dato más pequeño de una Colección b) siN, la 1≤k≤N Colección se representa sobre un ABB de talla Ejemplo: 7,2,9,1,5,3, k = 3 y N = 6 n→ 7
2 1
tamañoNIzq = 4
k=1
9 5
3
• Si se imprime en InOrden un ABB resulta una Colección Ordenada .... pero sigue siendo O(N) • Mejor aún, ¿ dónde se encuentra el mínimo del ABB n ? ¿ y su segundo mínimo, k = 2 ? ... ¿ hasta que k se encontrará en n.izq ? hasta el 4º
19
El Problema de la Selección, otra vez b) si la Colección se representa sobre un ABB k=3
k=5
k = 10
n→
n→
n→
7
2 1
2
9 1
5
7 9
5
2 1
3
3
tamañoNIzq = 4
9 5
3
tamañoNIzq = 4
if (k tamañoNIzq + 1) buscarKesimo(k, n.der)
buscarKesimo(k, n.izq) el k-ésimo es n.dato
k-tamañoNIzq-1
Ampliación de la clase ArbolBinarioBusqueda: el método buscarKesimo protected NodoBinario buscarKesimo(int k, NodoBinario n) throws ElementoNoEncontrado {
TbuscarKesimo(N) ∈ Ο(N)
if ( n == null ) throw new ElementoNoEncontrado(“al buscar K-ésimo”); int tamañoNIzq = NodoBinario.tamaño(n.izq); if ( k == tamañoNIzq + 1 ) return n; else if ( k 0 ) n.izq = insertar(clave, n.izq); else
n.der = insertar(clave, n.izq);
return n; } } 44
Ejercicio propuesto: además de insertar, indíquese qué métodos de ArbolBinarioBusqueda se ven afectados por la introducción en NodoBinario del nuevo atributo tamanyo y realícense las modificaciones oportunas en su código ¿Varía el coste de alguno de ellos?
45
22