PDF de programación - Programa de teoría AED I. Estructuras de Datos

Programa de teoría

AED I. Estructuras de Datos.

1. Abstracciones y especificaciones.

2. Conjuntos y diccionarios.

3. Representación de conjuntos mediante árboles.
4. Grafos.



AED II. Algorítmica.

1. Análisis de algoritmos.

2. Divide y vencerás.

3. Algoritmos voraces.

4. Programación dinámica.

5. Backtracking.

6. Ramificación y poda.


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I

AED I: ESTRUCTURAS DE DATOS



Tema 3. Representación de

conjuntos mediante árboles.

3.1. Árboles Trie.

3.2. Relaciones de equivalencia.

3.3. Árboles de búsqueda balanceados.

3.4. Árboles B.


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



2

1

3.1. Árboles Trie.

• Aplicación: representación de diccionarios (o en

general conjuntos) grandes de palabras.

• Ejemplo. Corrector ortográfico interactivo.


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



3

3.1. Árboles Trie.

• Diccionario español: ~ 3 millones de palabras.

• Muchas palabras  Mucha memoria y

operaciones lentas.

• Pero la búsqueda de una palabra no puede

tardar más de 1 milisegundo...



... esparto esparvar esparvel esparver espasmar espasmo

espasmódica espasmódico espata espatarrada
espatarrarse espática espático espato espátula

espatulomancia espaviento espavorecida espavorecido

espavorida espavorido espay especería especia

especial ...


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



4

2

3.1. Árboles Trie.

• Idea: muchas palabras tienen prefijos comunes.

P. ej.: espasmar, espasmo, espasmódico,
espasmódica, ...


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



5

3.1. Árboles Trie.

• Un Trie es, básicamente, un árbol de prefijos.

• Sea A un alfabeto. Por ejemplo A= {a, b, c, ..., z}

• Añadimos a A una marca de fin de palabra: $.



• Definición: un Trie es una estructura de árbol en la que:

1. La raíz del árbol representa la cadena vacía.

2. Un nodo puede tener tantos hijos como caracteres del
alfabeto A más uno. Cada hijo está etiquetado con un
carácter o una marca de fin $.

3. La sucesión de etiquetas desde la raíz hasta un nodo hoja,

etiquetado con la marca de fin $, representa una palabra.

4. A todos los nodos, excepto a la raíz y a las hojas

etiquetadas con $, se les denomina prefijos del árbol.


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



6

3

3.1. Árboles Trie.

• Ejemplo, C= {ELLA, ELLO, EL, TU, Y, YO}

T

U

$

Y

O

$

$

E

$

O

$

L

L

A

$

• ¿Cómo usarlo en el corrector interactivo?


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



7

3.1. Árboles Trie.

• Se pueden representar otros tipos de información, cambiando el

alfabeto A.

• Ejemplo: representación de URL de páginas web.

.com

.es

.org

.net

.google

.um

.upct

.emule

www

dis

ditec

$

/~ginesgm

$

$


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



8

4

3.1.1. Representación de tries.

• Cuestión: ¿Cómo representar árboles trie?

tipo

ArbolTrie[A]= Puntero[NodoTrie[A]]



• Reformulamos la pregunta: ¿Cómo representar

los nodos del árbol trie?

NodoTrie

A

C

N

T

$


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



9

3.1.1. Representación de tries.

• Un NodoTrie[A] es un Diccionario[tclave, tvalor],

donde tclave= A y tvalor= Puntero[NodoTrie[A]]

• Operaciones:

Consulta (n: NodoTrie[A]; caract: A):



Puntero[NodoTrie[A]]



Inserta (var n: NodoTrie[A]; caract: A;



ptr: Puntero[NodoTrie[A]])

TomaNuevo (var n: NodoTrie[A]; caract: A)


para cada caract hijo del nodo n hacer



acción


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



10

5

3.1.1. Representación de tries.

A

C

N

T

$

NodoTrie

- Representación mediante arrays.

A

B

C

D





.



.



Z



$

- Representación mediante listas con nodo cabecera.

$

A

C

N

T



car
sig
ptr


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



11

3.1.1. Representación de tries.

- Representación mediante arrays.

A

B

C

D





.



.



Z



$

tipo

NodoTrie[A]= array [A] de Puntero[NodoTrie[A]]



• Ventaja: acceso muy rápido a los valores.

• Inconveniente: desperdicia muchísima memoria.


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



12

6

3.1.1. Representación de tries.

• Ejemplo, C= {ELLA, ELLO, EL, TU, Y, YO}

T

U

$

Y

O

$

$

E

$

O

$

L

L

A

$


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



13

3.1.1. Representación de tries.

• Ejemplo, C= {ELLA, ELLO, EL, TU, Y, YO}


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



14

7

3.1.1. Representación de tries.

Consulta (n: NodoTrie[A]; car: A): Puntero[NodoTrie[A]]

devolver n[car]


Inserta (var n: NodoTrie[A]; car: A; ptr: Puntero[NodoTrie[A]])

n[car]:= ptr


TomaNuevo (var n: NodoTrie[A]; car: A)

n[car]:= NUEVO NodoTrie[A]



• Se supone que al crear un nodo se inicializa todo a NULO.

• ¿Cómo sería el iterador: para cada caract hijo de n hacer…?


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



15

3.1.1. Representación de tries.

- Representación mediante listas con nodo cabecera.

car
sig
ptr



A

D



car
sig
ptr

$

N

T



tipo NodoTrie[A]= registro



car: A

sig, ptr: Puntero[NodoTrie[A]]

finregistro



• Ventaja: uso razonable de memoria.

• Inconveniente: operaciones más lentas.


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



16

8

3.1.1. Representación de tries.

• Ejemplo, C= {ELLA, ELLO, EL, TU, Y, YO}

T

U

$

Y

O

$

$

E

$

O

$

L

L

A

$


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



17

3.1.1. Representación de tries.

• Ejemplo, C= {ELLA, ELLO, EL, TU, Y, YO}

a

E

T

Y





U



$





$



O



$







$







L



L



A

O



$





$






Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



18

c

9

3.1.1. Representación de tries.

Consulta (n: NodoTrie[A]; c: A): Puntero[NodoTrie[A]]
si c == $ entonces devolver nptr

tmp:= nsig


mientras tmp ≠ NULO AND tmpcar < c hacer



tmp:= tmpsig


si tmp ≠ NULO AND tmpcar == c entonces devolver tmpptr

sino devolver NULO


Inserta (var n: NodoTrie[A]; car: A; ptr: Puntero[NodoTrie[A]])
1. Tratamiento especial si el carácter car es $

2. En otro caso, recorrer la lista buscando el carácter car

3. Si se encuentra, modificar el puntero ptr

3. En otro caso, añadir un nuevo nodo en la posición



adecuada, con el carácter car y el puntero ptr


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



19

3.1.1. Representación de tries.

Inserta (var n: NodoTrie[A]; car: A; ptr: Puntero[NodoTrie[A]])
si c == $ entonces nptr:= ptr

sino



tmp:= PunteroA(n)
mientras tmpsig ≠ NULO AND tmpsigcar < c hacer
tmp:= tmpsig
si tmpsig≠NULO AND tmpsigcar == c entonces tmpptr:= ptr

sino
tmpsig:= NUEVO NodoTrie[A](car, ptr, tmpsig)

finsi

finsi



• ¿Cómo sería la operación TomaNuevo?

• ¿Cómo sería el iterador para nada carácter…?


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



20

10

3.1.2. Operaciones con tries.

• Utilizando la representación de nodos trie (con listas o con

arrays) implementar las operaciones de inserción,
eliminación y consulta sobre el trie.

• Ejemplo. Insertar ELLE.

E

L

L E

$

i

E

$

pos

E

L

L

A

$

$

O

$


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



T

U

$

Y

O

$

$



21

3.1.2. Operaciones con tries.

operación Inserta (var a: ArbolTrie[A]; s: cadena)
var pos: Puntero[NodoTrie[A]]



si Consulta (pos, s[i]) == NULO entonces
TomaNuevo (pos, s[i])
pos:= Consulta (pos, s[i])
i:= i + 1

i:= 1
pos:= a
mientras s[i] ≠ $ hacer



finmientras
Inserta (pos, $, pos)

• Modificar el procedimiento para que haga una consulta.
• Si queremos añadir información asociada a cada

palabra, ¿dónde debería colocarse?

• ¿Cómo listar todas las palabras del trie (en orden)?


Tema 3. Repr. de conjuntos mediante árboles

A.E.D. I



22

11

3.1.2. Operaciones con tries.

operación ListarTodas (var n: ArbolTrie[A], palabra: cadena)


para cada car hijo del nodo n hacer



si car == $ entonces Escribir(palabra)
sino ListarTodas(Consulta(n, car), palabra+car)

finpara

• Llamada inicial: ListarTodas(raiz, “”)



• ¿Cómo sería el uso del trie en el corrector interactivo?
• Empezar una palabra
Colocar pos en la raíz del árbol
• Pulsar una tecla c en una palabra
Si Consulta (pos, c) == NULO entonces la palabra es

incorrecta, en otro caso moverse en el árbol

• Acabar una palabra
Si Consulta (pos, $) == NULO entonces la palabra es

incorrecta, en otro caso es correcta


Tema 3. Repr. de conjuntos me