PDF de programación - Tema 3: Algoritmos de Búsqueda

Imágen de pdf Tema 3: Algoritmos de Búsqueda

Tema 3: Algoritmos de Búsquedagráfica de visualizaciones

Publicado el 13 de Junio del 2019
578 visualizaciones desde el 13 de Junio del 2019
1,5 MB
80 paginas
Creado hace 3a (11/09/2016)
Tema 3: Algoritmos
de Búsqueda

3.1 Algoritmos básicos de
búsqueda

J.Dorronsoro, P. Varona, C. Aguirre

Resultados conocidos

 Búsqueda lineal





 Búsqueda binaria



 Tenemos que calcular

3

NNNiBLineCSiTkpiTknNABLin1])[(])[()(cdc OBcon )(NNWBLin)()1()lg()lg()(NAONNNWfBBinBBin)(NAeBBin J.Dorronsoro, P. Varona, C. Aguirre

Coste medio de BBin con éxito.
 Veamos un ejemplo:

T=[1 2 3 4 5 6 7] N=7=23-1

4

2

6

1

3

5

7

 Para N=2k-1 se tiene

Obs: N=2k-1klog(N)

4

)3333221(71])[(71)(71iBBineiTknNABBin)2·32·22·1(71)4·32·21(71)(210NAeBBin]1)lg([1)(]122[121)(11NNNNNAkNiNNAekkkiieBBinBBin)1()lg()(11)lg()(ONNANNNAeeBBinBBin J.Dorronsoro, P. Varona, C. Aguirre

Árbol de decisión para algoritmos de
búsqueda por CDC: Definición



Si A es un algoritmo de búsqueda por comparación de
clave y N es un tamaño de tabla, se puede construir su
árbol de decisión TA
siguientes 5 condiciones:

N para N tal que cumple las

1. Contiene nodos de la forma i que indica la cdc entre el

elemento i-ésimo de la tabla y una clave genérica k.
Si k coincide con el elemento i-ésimo (T[i]==k) entonces la
búsqueda de la clave k termina en el modo i
El subárbol izquierdo del nodo i en TA
(cdcs) que realiza el algoritmo A si k < T[i].
El subárbol derecho del nodo i en TA
que realiza el algoritmo A si k > T[i].
Las hojas H en TA
fallidas.
Los nodos la de las búsquedas con éxito.

N recogen la evolución de las búsquedas

N contiene el trabajo

N contiene el trabajo (cdcs)

2.

3.

4.

5.

6.

5

Árbol de decisión: Ejemplos

J.Dorronsoro, P. Varona, C. Aguirre

3
=

>

<

<

F

>

2
=

1
=

<

F

<

F
>

F

4
=

>

5
=

<

F

<

F

1
=

>

<

F

2
=

>

3
=

>

F

<

F

Tabla ordenada

>

F

<

1
=

Tabla no ordenada

<

2
=

>

>

<

2
=

>

3
>=

F

<

F

3
=

>

F

<

F

3
>=

F

<

F

3
=

>

F

<

F

Obs: TA

N es un árbol binario con al menos N nodos internos. Esto da la cota inferior:

WA(N)≥profmin(N)

Profundidad mínima de un
árbol con al menos N nodos internos

6

5BBinT3BLordT3BLT J.Dorronsoro, P. Varona, C. Aguirre

Árbol de decisión: Cotas inf. Caso Peor
 Estimamos profmin(N)

N

1

2

3

4

7

T

Profmin(N)

1

2

2

3

3

7

Cotas inferiores en búsqueda por cdcs

J.Dorronsoro, P. Varona, C. Aguirre

 Tenemos que

WA(N)≥profmin(N) =lg(N)+1
WA(N)=(lg(N))  AB con
B={A: algoritmo de búsqueda por cdc}

 BBin es óptimo para el caso peor.

 Se puede demostrar también
AA(N)=(lg(N))  AB

 BBin es óptimo para el caso medio.

8

J.Dorronsoro, P. Varona, C. Aguirre

¿Ya hemos acabado?

 Observación: la búsqueda no es una



operación aislada
Los elementos no sólo se buscan sino que
también se insertan o se borran

 No sólo importa cómo se busca sino también

dónde se busca

 Contexto: TAD Diccionario

9

J.Dorronsoro, P. Varona, C. Aguirre

En esta sección hemos …

 Recordado los costes peor y medio de

búsqueda lineal y binaria

 Aprendido el concepto de árbol de

decisión en búsqueda por cdcs

 Aprendido a construir árboles de decisión

en búsqueda por cdcs

 Visto que la búsqueda binaria es óptima
en los casos peor y medio dentro de los
algoritmos de búsqueda por cdcs

10

3.2 Búsqueda sobre
diccionarios

J.Dorronsoro, P. Varona, C. Aguirre

TAD Diccionario

 Diccionario: conjunto ordenado de datos con

las primitivas.
 pos Buscar(clave k, dicc D)

 Devuelve la posición de la clave k en el diccionario D o un

código de error ERR si k no está en D.

 status Insertar (clave k, dicc D)



Inserta la clave k en el diccionario D y devuelve OK o ERR
si k no se pudo incorporar a D.

 void Borrar (clave k, dicc D)

 Elimina la clave k en el diccionario D

12

J.Dorronsoro, P. Varona, C. Aguirre

EdDs para Diccionarios I
 ¿Qué EdD es la más adecuada para un

diccionario?

 Opción 1: Tabla ordenada (|D|=N)

 Buscar: Usamos BBin => nBuscar(k,D)=O(log(N)) => óptimo.



Insertar: Hay que mantener la tabla ordenada => la
inserción es costosa

 Ejemplo:

Insertar 26

Hay que desplazar a la
derecha estos elementos

24 25 27 29

 Si se inserta en la posición 1, hay que desplazar N

elementos

 En el caso medio se desplazan N/2 elementos
 Por tanto nInsertar(k,D)=(N): malo!!

13

J.Dorronsoro, P. Varona, C. Aguirre

EdDs para Diccionarios II
 Opción 2: Árbol binario de búsqueda (ABdB)

 Definición: Un ABdB es un árbol binario T que para

todo nodo T’T se cumple:

Info(T’’)<Info(T’)<Info(T’’’)

para cualquier nodo T’’ a la izq de T’ y T’’’ a la derecha
de T’



Es decir, todos los nodos a la izquierda de T’ tienen
un valor menor que info(T’) y todos los nodos a la
derecha de T’ tienen un valor mayor que info(T’)

Ejemplo:

5

2

7

1

4

6

9

8

11

14

J.Dorronsoro, P. Varona, C. Aguirre

Buscar sobre ABdBs I
 Ejemplo

B(k=8)

5

8>5

2

7

8>7

1

4

6

8<9

9

8

11

k==8

15

J.Dorronsoro, P. Varona, C. Aguirre

Buscar sobre ABdBs II

 Pseudocódigo:

AB Buscar (clave k, AB T)
si T==NULL : return NULL;
si info(T)==k : return T;
si k<info(T) :

return Buscar(k,izq(T));

si k>info(T) :

return Buscar(k,der(T));

 Observación:

nBuscar(k,T)=prof(k, T) + 1 = O(prof(T))

16

J.Dorronsoro, P. Varona, C. Aguirre

Insertar en ABDBs I
 Ejemplo

I(k=3)

BuscarUltimo

3<5

5

2

3>2

7

izq(4)==3

4

6

9

1

8

11

1

3<4

NULL

Último, 3<4 y izq(4)==NULL

2

3

5

7

4

6

9

8

11

17

J.Dorronsoro, P. Varona, C. Aguirre

Insertar en ABDBs II
 Pseudocódigo

status Insertar (clave k, AB T)

AB BuscarUltimo(clave k, AB T)

T’=BuscarUltimo(k,T);
T’’=GetNodo();
si T’’==NULL : return ERR;
info(T’’)=k;
si k<info(T’) :

izq(T’)=T’’

else :

der(T’)=T’’;

return OK;

 Observación

si k == info(T): return NULL;
si (k<info(T) y izq(T) ==NULL) o
(k>info(T) y der(T) ==NULL):
return T;

si k<info(T) y izq(T) !=NULL :

return BuscarUltimo(k,izq(T));

si k>info(T) y der(T) !=NULL :

return BuscarUltimo(k,der(T));

nInsertar(k,T)=nBuscarUltimo(k,T)+1 nInsertar(k,T)=O(prof(T))

18

J.Dorronsoro, P. Varona, C. Aguirre

Borrar en ABdBs

 Pseudocódigo:

void Borrar (clave k, AB T)

T’=Buscar(k,T);
si T’!=NULL :

EliminaryReajustar(T’,T);

 Por tanto:

nBorrar (k,T)=nBuscar (k,T)+ nEyR (T’,T)

 En EliminaryReajustar hay tres posibles

casos, dependiendo del número de hijos que
tenga el nodo T’ a eliminar

19

J.Dorronsoro, P. Varona, C. Aguirre

Eliminar y Reajustar I
 Caso 1: El nodo a eliminar no tiene hijos

 se libera el nodo T’ (free(T’)), y
 el puntero del padre de T’ que apuntaba a T’ se

reasigna a NULL.

 Coste EliminaryReajustar = O(1)

T

T’

EliminaryReajustar(T’)

T

NULL

NULL

NULL

20

J.Dorronsoro, P. Varona, C. Aguirre

Eliminar y Reajustar II
 Caso 2: El nodo a eliminar tiene sólo un hijo

 el puntero del padre de T’ que apuntaba a T’ se

hace apuntar al único hijo de T’ y

 se libera T’

 Coste EliminaryReajustar = O(1)

T

T’

EliminaryReajustar(T’)

T

T’’

NULL

T’’

21

J.Dorronsoro, P. Varona, C. Aguirre

Eliminar y Reajustar III

 Caso 3: El nodo a eliminar tiene dos hijos

B(5)

17

5

3

14

17

6

17

6

Caso 1

3

14

3

14

1

4

11

15

1

4

11

15

1

4

11

15

6

12

7

6

12

7

Sucesor

12

7

22

J.Dorronsoro, P. Varona, C. Aguirre

Eliminar y Reajustar IV
 Cuando el nodo a eliminar tiene dos hijos

 T’ se sustituye por el nodo que contiene al sucesor

(el elemento siguiente en la tabla ordenada), y

 se elimina el nodo T’ según el caso 1 o 2.

 Coste EliminaryReajustar ≤ prof(T)

T

T’

T

T

T’Sucesor’

T’Sucesor’

T’’’

T’’

T’’’

T’’

T’’’

T’’

T’Sucesor’

T’’’’

T’

T’’’’

T’’’’

23

J.Dorronsoro, P. Varona, C. Aguirre

Búsqueda del Sucesor
 Pseudocódigo

AB BuscarSucesor(AB T’)

T’’=der(T’);
mientras izq(T’’)!=NULL :

T’’=izq(T’’);

return T’’ ;

 Obs: Si k’ es el sucesor en un ABdB de k,

entonces izq(k’)==NULL:
 Si izq(k’)==k’’ se tendria que k’’<k’
 Pero k’’>k, pues k’’ está a la derecha de k
 Luego se tiene que k<k’’<k’ y
 Por tanto, k’ no puede ser el sucesor de k.

24

J.Dorronsoro, P. Varona, C. Aguirre

Eficacia de Primitivas sobre ABdB



nEyR(T’,T)= nBuscarSucesor+nReajustarPunteros=
= O(prof(T))+O(1) =O(prof(T))

 Por tanto

nBorrar(k,T)=O(prof(T))+ O(prof(T))= O(prof(T))

Buscar

EyR

 ABdB es eficaz siempre que prof(T)= (lg(N))
 Pero sobre todos los árboles WBuscar(N)=N:

¡¡malo!!

1

2

3

N

25

J.Dorronsoro, P. Varona, C. Aguirre

Coste medio de búsqueda en ABdBs I
 Ae

Buscar(N)= coste medio de (1) la búsqueda de

todos los elementos (2) para todos los T

Por tanto

26

)T, )((nN1N!1)(TAN!1(N)AσΣσN1iBuscarΣσσeBuscareBuscarNNi]))((11[!1]1))(([1!111NNNiNiiprofNNiprofNNNNTnNNiprofNNCrearNi)(!111]))((!1111)(11)(NANNACreareBuscar J.Dorronsoro, P. Varona, C. Aguirre

Coste medio de búsqueda en ABdBs II
 Vemos a un pseudocódigo alternativo

=[3 5 2 6 4 1]

Crear

3

Caso similar a QS:
nC ()=N-1+ nC(i)+ nC(d)

[2 1]

[5 6 4]

para Crear

AB Crear (tabla )

T=IniAB();
InsAB((1),T);
Repartir(, i, d);
Ti=Crear(i);
Td=Crear(d);
izq(T)=Ti;
der(T)=Td;
return T;

Por tanto:

27

))(log()()log(211)(11)(NNONNNNANNACreareBuscar)()log(2)(NONNNACrear J.Dorronsoro, P. Varona, C. Aguirre

Resumen de primitivas sobre ABdBs
 Si B es un algoritmo general de Búsqueda por

cdc

WB(N)=(lg(N))

 Si la EdD es un ABdB las primitivas son

eficaces en promedio

 Si aseguramos que para todo N se tiene un

ABdB tal que prof(T)=(lg(N)) tendríamos
que

WBuscar(N)= (lg(N))

28

J.Dorronsoro, P. Varona, C. Aguirre

En esta sección hemos …

 Introducido el concepto de diccionario y

sus primitivas

 Estudiado su implementación sobre

ABdBs

 Comprobado que su coste viene

determinado por la profundidad del ABdB
 Comprobado que dicha implementación

es óptima en el caso medio

 Comprobado que en el caso peor dicha
implementación tiene un coste (lg(N))

29

J.Dorronsoro, P. Varona, C. Aguirre

Herr
  • Links de descarga
http://lwp-l.com/pdf16118

Comentarios de: Tema 3: Algoritmos de Búsqueda (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad