Tema 8- El Árbol Binario de Búsqueda - dsic.upv.esnprieto/clases/EDA0506/T8/Traspas8.pdf ·...

1

1

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 ArbolBinarioBusqueda4. Implementación de las EDA Diccionario y Cola de Prioridad

según un ABB: las clases ABBDiccionario y ABBColaPrioridad5. El problema de la Selección, otra vez

3

Bibliografía básica:

Weiss, M.A. Estructuras de datos en Java. Adisson-Wesley, 2000. Capítulo 18, apartados del 1 al 3, ambos inclusive.

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

2

4

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ómicapermite en el Peor de los Casos una cota logarítmica, pero la inserción se encarece (es lineal)

¿ y si la Aplicación/Modelo se basa en la Búsqueda ?

Búsqueda Estática

5

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

El Problema de la Búsqueda de un Dato x en una Colección de numDatos

3

6

Aplicaciones Orientadas a la Búsqueda:Modelo Diccionario

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

La Búsqueda en un Diccionario es Dinámica

Una Implementación adecuada del Diccionario consigue que sus operaciones se ejecuten en un tiempo independiente de su número de Entrada’s

7

Aplicaciones Orientadas a la Búsqueda:Modelo Cola de Prioridad

La operación básica de la Cola de Prioridad es buscar elDato 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) yeliminar(x)

Al insertar(x) puede estar repetido

La Búsqueda en una Cola de Prioridad es Dinámica

Una Implementación adecuada de la Cola de Prioridadconsigue que excepto eliminarMin() las demás operaciones se ejecuten en un tiempo promedio constante

4

8

El Problema de la Búsqueda sobre una Colección de Datos: soluciones y costes sobre diferentes

Representaciones

Θ(1)

Θ(N)

Θ(1)

Θ(N)

buscarMin()

Θ(1)

--

Θ(N)

Θ(1)

insertar(x)

Θ(N)

Θ(N)

Θ(N)

Θ(N)

buscar(x)

Θ(log N)

Θ(N)

Θ(1)

Θ(N)

eliminarMin()

MonticuloBinario

ArbolBinario

LEIOrdenada

LEI

Coste medio

Representación

Para ser más eficiente ….¿ Qué características tendría que tener la Representación

de la EDA Orientada a la Búsqueda?

9

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

Para ser más eficiente ….¿ Qué características tendría que tener la

Representación de una EDA Orientada a la Búsqueda?

Árbol Binario de Búsqueda (ABB)

5

10

Definición de Árbol Binario Equilibrado

Árbol Binario en el que la diferencia de Alturas de losHijos Derecho e Izquierdo es como máximo 1

insertar(new Integer(1)) ;12

8 16

104

2

14

6

12

8 16

104

2

14

6

1Árbol Binario Equilibrado Árbol Binario

11

7

2 9

51

3

Árbol Binario de Búsqueda

Árbol Binario

7

2 9

51

83

Un Árbol Binario es de Búsqueda (o cumple la propiedad de Búsqueda Ordenada) si:1. todos los Datos de su subÁrbol Izquierdo son menores

que el que ocupa su Raíz2. todos los Datos de su subÁrbol Derecho son mayores

que el que ocupa su Raíz3. los subÁrboles Izquierdo y Derecho también son ABB

El Árbol Binario de Búsqueda (ABB) como Representación de una EDA Orientada a la

Búsqueda

6

12

• Si se imprime en InOrden .....

• El Dato mínimo se encuentra en .....

• El Dato máximo se encuentra en .....

7

2 9

51

3

1 2 3 5 7 9

resulta una Secuencia Ordenada

Propiedades del Árbol Binario de Búsqueda (ABB)

el último Nodo Izquierdo de su primera Rama

el último Nodo Derecho de su última Rama

13

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:

Cuestiones propuestas:

7

2 9

51

3

¿dónde se encuentra el sucesor del 2 en este ABB?¿y su predecesor?


⇒ SIGUE

7




15

6

2

3

4

7

13

9

18

17 20

15

buscar(x)

7

2 9

51

3

= 4

esfuerzo de Comparación(x) = 1+Nivel de x

4 Comparaciones

7

2 9

51

3

buscar(x) = 9

9

2 Comparaciones

= 3

Operaciones sobre un ABB y su coste:buscar(x) Búsqueda del Nodo del ABB que contiene a x

Tbuscar (N)∈ O(H)

8

16

eMC = ∑Nivel=0..H (nº Nodos de Nivel) (1+ Nivel) _________________________________

N

7

2 9

51

3

¿ esfuerzo Medio de Comparación (eMC) ?

Operaciones sobre un ABB y su coste:eMC() TeMC (N)∈ Θ (N)

7

2 9

51

3

insertar(x) = 10

10

7

2 9

51

3

insertar(x) = 6

Operaciones sobre un ABB y su coste: insertar(x)

¿ Se puede calcular el esfuerzo Medio de Comparación conforme se van insertando los Datos ?

1. Búsqueda del lugar de inserción de x en el ABB2. Resolución de la Búsqueda: insertar en tal lugar el nuevo Nodo que contiene a x

Tinsertar (N)∈ O(H)

9

buscarMin()

7

2 9

51

3

Operaciones sobre un ABB y su coste:buscarMin() y buscarMax()

buscarMax()

7

2 9

51

3

Recorrido de una determinada Rama del ABB

TbuscarMin/Max (N)∈ Θ (H)

eliminar(x) = 17

2 9

51

3

7

2 9

51

3

eliminar(x) = 57

2 9

51

3

eliminar(x) = 2

o Caso 3: eliminar un Nodo n con 2 Hijos

o Caso 1: eliminar un Nodo n con 0 Hijos

o Caso 2: eliminarun Nodo n con 1 Hijo

n = (n.izq != null) ? n.izq: n.der;

Operaciones sobre un ABB y su coste: eliminar(x)

3

null

n = null

buscarMin()

⇓ Caso único:

n = ( n.izq != null ) ? n.izq: n.der;

n.dato=buscarMin(n.der).dato;

n.der = eliminarMin(n.der);

1. Búsqueda del Nodo que contiene a x2. Resolución de la Búsqueda: eliminarlo

null

Teliminar (N)∈ O(H)

¿ ?

10

7

2 9

51

3

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)

21

7

2 9

51

3

5

2 7

31 9

Equilibrado, Altura y eMC de un ABB

¡¡¡ cuanto más Equilibrado el ABBmenor será su Altura, su eMC y el coste de sus

operaciones !!!

1

2

3

5

7

9

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

11

22

Equilibrado, Altura y eMC de un ABB:

talla, instancias significativas y costeEn 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:

la estructura de la clase correspondiente (atributos)

las operaciones de inserción y eliminación

23

Θ(1)

Θ(N)

Θ(1)

Θ(N)

buscarMin()

Θ(1)

--

Θ(N)

Θ(1)

insertar(x)

Θ(N)

Θ(N)

Θ(N)

Θ(N)

buscar(x)

Θ(log N)

Θ(N)

Θ(1)

Θ(N)

eliminarMin()

Monticulo Binario

Arbol Binario

LEI Ordenada

LEI

Coste medio Representación

Θ(log N)Θ(log N)Θ(log N)Θ(log N)ABB


Representaciones

12

24

Ο(1)

Ο(N)

Ο(1)

Ο(N)

buscarMin()

Ο(log N)

--

Ο(N)

Ο(1)

insertar(x)

Ο(N)

Ο(N)

Ο(N)

Ο(N)

buscar(x)

Ο(log N)

Ο(N)

Ο(1)

Ο(N)

eliminarMin()

Monticulo Binario

Arbol Binario

LEI Ordenada

LEI

Coste peorRepresentación

Ο(N)Ο(N)Ο(N)Ο(N)ABB


Representaciones

25

un Árbol Binario TIENE UN Nodo Binario Raíz

Árbol Binario, donde un Nodo define al Árbol del que es Raíz

un Árbol Binario TIENE UN numTotalInserciones y numTotalComparaciones tal que:

eMC = numTotalComparaciones / numTotalInserciones

Representación de un ABB

13

26

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,363924,220,911,244,898,258,362,363925,202,911,240,912,245,3632,399,387,219,266,382,381,278,363935,278,347,621,299,392,358,363

Ejemplo propuesto

Ejemplo propuesto: a partir de ArbolBinarioBusqueda, diseñar las clases ABBDiccionario y ABBColaPrioridad para que implementen, respectivamente, Diccionario y ColaPrioridad mediante un ABB

14

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, como1. ABBDiccionario, extends ArbolBinarioBusqueda implements Diccionario

2. ABBColaPrioridad, extends ArbolBinarioBusqueda implements ColaPrioridad

Ejemplo propuesto: a partir de ArbolBinarioBusqueda, diseñar las clases ABBDiccionario y ABBColaPrioridad para que implementen, respectivamente, Diccionario y ColaPrioridad mediante un ABB

Cuestiones:1. ¿ Cuál de los dos métodos de inserción de ArbolBinarioBusquedase lanza en ABBDiccionario ? ¿ y enABBColaPrioridad ?2. Desde una aplicación que utiliza un Diccionario, ¿es correcto ejecutar Diccionario d = new ArbolBinarioBusqueda()? ¿ Por qué ?

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 "*";}

La clase ArbolBinarioBusqueda: atributos y métodospúblicos sobre this ABB

15

30

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 {....}

...

protected NodoBinario buscar(Object clave, NodoBinario n)

throws ElementoNoEncontrado {

La clase ArbolBinarioBusqueda: diseño Recursivo del método protected buscar

/** Búsqueda Recursiva de clave en un Nodo Binario de Búsqueda ⇒* Búsqueda Recursiva Binaria */

if ( casoBase(talla(n)) ) return soluciónBase(talla(n));else {

if ( mejorCaso() ) return soluciónMejorCaso();

else {

// Llamadas recursivas

return soluciónPeorCaso();

}}

int resC = ((Comparable)n.dato).compareTo(clave);

if ( n == null ) throw new ElementoNoEncontrado(“al buscar ”+clave);

if ( resC == 0 ) return n;

if ( resC > 0 ) return buscar(clave, n.izq) ;

else return buscar(clave, n.der);

Ejercicio propuesto: diseño Iterativo del métodoprotected buscar

16

protected NodoBinario insertar(Object clave, NodoBinario n)


La clase ArbolBinarioBusqueda: diseño Recursivo del método protected insertar

/** 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 ( casoBase(talla(n)) ) return soluciónBase(talla(n));

else {

if ( mejorCaso() ) return soluciónMejorCaso();

else {

// Llamadas recursivas

return soluciónPeorCaso();

}}

int resC = ((Comparable)n.dato).compareTo(clave);

if ( n == null ) return new NodoBinario(clave);

if ( resC == 0 ) throw new ElementoDuplicado(“al ...”);

if ( resC > 0 ) n.izq = insertar(clave, n.izq) ;

else n.der = insertar(clave, n.der);

return n;

Ejercicios propuestos:• diseño Iterativo del método protected insertar• diseño Recursivo del método insertarTodos

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 ) n.der = eliminar(clave, n.der);else if ( resC > 0 ) n.izq = eliminar(clave, n.izq);

else {/** clave encontrada en Nodo n: eliminarlo */

}

return n;}

La clase ArbolBinarioBusqueda: diseño Recursivo del método protected eliminar

if ( n.izq != null && n.der != null ) {n.dato = buscarMin(n.der).dato; n.der = eliminarMin(n.der);

} else n = ( n.izq != null ) ? n.izq: n.der;

17

/**SII esVacio() */protected NodoBinario eliminarMin( NodoBinario n ) {

if (n.izq != null ) n.izq = eliminarMin(n.izq) ;else n = n.der;return n;

}

/**SII esVacio() */protected NodoBinario buscarMin(NodoBinario n) {

if (n.izq != null ) n.izq = buscarMin(n.izq) ;return n;

}

La clase ArbolBinarioBusqueda: diseño de los métodoprotected buscarMin y eliminarMin

Ejercicios propuestos:• diseño Iterativo de los métodos protected buscarMin y eliminarMin• diseño Recursivo e Iterativo de buscarMax y eliminarMax

35

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?

Ejemplos propuestos en la Práctica 4

18

Cálculo del k-ésimo Dato más pequeño de una Colecciónde talla N, 1≤k≤NEjemplo: 7,2,9,1,5,3, k = 3 y N = 6

El Problema de la Selección, otra vez

9 1 5 327

/** Solución 1 */

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] */

3 7 5 921

TseleccionDirectaKmedio(N) ∈ O(k*N)

a) si la Colección se representa sobre un array



9 1 5 327

/** Solución 2 */

public static void quickSort(Object v[]){

....}

/** k-ésimo Mínimo de la Colección en v[k-1] */3 7 5 921

TquickSortmedio(N) ∈ O(N*logN)


heapSort(Object v[]){

19



9 1 5 327

/** 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] */3 7 5 921

TseleccionRapidamedio(N) ∈ O(N)


7

2 9

51

3

• Si se imprime en InOrden un ABB resulta una Colección Ordenada

• Mejor aún, ¿ dónde se encuentra el mínimo del ABB n ?

k = 1

.... pero sigue siendo O(N)

¿ y su segundo mínimo, k = 2 ? ...¿ hasta que k se encontrará en n.izq ?

tamañoNIzq = 4

hasta el 4º

n→

El Problema de la Selección, otra vez Cálculo del k-ésimo Dato más pequeño de una Colecciónde talla N, 1≤k≤NEjemplo: 7,2,9,1,5,3, k = 3 y N = 6

b) si la Colección se representa sobre un ABB

20

7

2 9

51

3

7

2 9

51

3

7

2 9

51

3

tamañoNIzq = 4

n→ n→ n→k = 3

if (k <= tamañoNIzq) buscarKesimo(k, n.izq)

tamañoNIzq = 4 tamañoNIzq = 4

k = 5

if (k == tamañoNIzq + 1)

el k-ésimo es n.dato

k = 10

if (k > tamañoNIzq + 1)buscarKesimo(k, n.der)

k-tamañoNIzq-1

El Problema de la Selección, otra vez b) si la Colección se representa sobre un ABB

41

// Lo lanza el homónimo de una extensión de ArbolBinarioBusqueda

public Object buscarKesimo(int k) throws ElementoNoEncontrado

{ return buscarKesimo(k, raiz).dato; }

protected NodoBinario buscarKesimo(int k, NodoBinario 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 <= tamañoNIzq ) return buscarKesimo(k, n.izq);

else return buscarKesimo(k-tamañoNIzq-1,n.der);

}

Ampliación de la clase ArbolBinarioBusqueda:

el método buscarKesimo

TbuscarKesimo(N) ∈ Ο (N)

21

42

Mejorar la eficiencia de buscarKesimo (hasta

O(logN)) es mejorar la de tamaño (hasta Θ(1))

Mejorar la complejidad del método tamaño supone NO calcularlo a-posteriori, cuando ya se dispone del Árbol Binario SINO conforme se crean e insertan sus Nodos

⇓ Si un Nodo TIENE UN Tamaño, por definición de Tamaño

• Al crearlo, su Tamaño es 1

• Al insertar un nuevo Dato, cada Nodo del Camino de inserción incrementa Tamaño igual a 1+Tamaño

• Al borrar un Nodo, cada Nodo del Camino de borradoTIENE UN Tamaño igual a 1-Tamaño

final class NodoBinario { Object dato;NodoBinario izq, der;

NodoBinario(Object x, NodoBinario izq, NodoBinario der) {dato = x; this.izq = izq; this.der = der;

}

static int tamanyo(NodoBinario actual) { if ( actual == null ) return 0;else return 1 + tamanyo(actual.izq) + tamanyo(actual.der);

}......

}

int tamanyo;

tamanyo = 1;

Modificaciones en la clase NodoBinario

int tamanyo() { return tamanyo;

}

22

44

protected NodoBinario insertar(Object clave, NodoBinario n)

throws ElementoDuplicado {

if ( n == null ) return new NodoBinario(clave);

else { int resC = ((Comparable)n.dato).compareTo(clave) ;numTotalComparaciones++;if ( resC == 0 ) throw new ElementoDuplicado(“...”);

if ( resC > 0 ) n.izq = insertar(clave, n.izq);

else n.der = insertar(clave, n.izq);return n;

}}

n.tamanyo++;

Modificaciones en la clase ArbolBinarioBusqueda

45

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 tamanyoy realícense las modificaciones oportunas en su código ¿Varía el coste de alguno de ellos?

Tema 8- El Árbol Binario de Búsqueda - dsic.upv.esnprieto/clases/EDA0506/T8/Traspas8.pdf ·...

Documents

Transcript of Tema 8- El Árbol Binario de Búsqueda - dsic.upv.esnprieto/clases/EDA0506/T8/Traspas8.pdf ·...