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

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