Introducció
Són un tipus abstracte de dades (TAD), és a dir, un conjunt d'elements i un conjunt d'operacions sobre ells.
Un diccionari és un conjunt d'elements amb una clau associada (treta d'un conjunt amb un ordre total definit) amb les operacions de cercar, inserir i esborrar un element.
Una estructura de dades és una estructura que ens permet implementar TAD.
Implementacions de diccionaris
1) Taules (no ordenades)
- Inserir un element nou: [latex]\theta(1)[/latex].
- Esborrar un element: cost de cercar l'element ([latex]O(n)[/latex]) + cost de treure'l de la taula (varia segons el mecanisme d'eliminació, possiblement [latex]O(n)[/latex]).
2) Llistes (enllaçades, encadenades)
Per recórrer una llista s'ha de fer de forma seqüencial, mitjançant iteradors (punters).
- Inserir un element nou:
– al principi: [latex]\theta(1)[/latex];
– al final de la llista, recorrent-la sencera: [latex]\theta(n)[/latex]. - Cercar un element: [latex]O(n)[/latex]
- Esborrar un element: [latex]O(n)[/latex]
3) Taules de dispersió (hash tables)
El disseny de la funció de hash és molt important per obtenir taules ben equilibrades.
En cas pitjor, el cost serà de [latex]\theta(n)[/latex], inserint al final amb una funció de dispersió que resulti en llistes llargues. Però, si la funció de dispersió està ben dissenyada, repartirà els elements equitativament, resultant llistes de mitjana [latex]\alpha = \frac{n}{M}[/latex] amb un cost [latex]\theta(\alpha)[/latex].
4) Arbres binaris de cerca (ABC, o Binary Search Tree, BST)
Un ABC és un arbre binari on cada node té una clau associada i els sub-arbres esquerra i dret compleixen les següents propietats:
- [latex]\forall[/latex] clau [latex]y[/latex] associada a un node del sub-arbre esquerra d'un node amb clau [latex]x[/latex] es compleix que [latex]y < x[/latex].
- [latex]\forall[/latex] clau [latex]y[/latex] associada a un node del sub-arbre dret d'un node amb clau [latex]x[/latex] es compleix que [latex]y > x[/latex].
Observacions:
- Suposem que totes les claus són diferents.
- Un arbre buit és per definició un ABC.
- Construir un ABC a partir d'un arbre buit i un conjunt d'[latex]n[/latex] claus:
– cas millor: [latex]\theta(n log n)[/latex] (arbre equilibrat);
– cas mitjà: [latex]\theta(n log n)[/latex], suposant que totes les permutacions de les [latex]n[/latex] claus són igualment probables;
– cas pitjor: [latex]\theta(n^2)[/latex] (ordenats). - Inserir una clau en un arbre d'[latex]n[/latex] nodes: [latex]\theta(h)[/latex], on [latex]h[/latex] és l'alçada de l'arbre.
[latex]h = \begin{cases}n & \small en\ cas\ pitjor \\ log n & \small en\ el\ cas\ millor\ i\ mitj\grave{a}\end{cases}[/latex] - Cercar una clau en un arbre d'alçada [latex]h[/latex]: [latex]\theta(h)[/latex].
- Esborrar:
– Esborrar el 9: esborrar un fulla; és fàcil.
– Esborrar el 7: esborrar un node amb un sub-arbre buit, és fàcil.
– Esborrar l'11: cal substituir-lo pel mínim del sub-arbre dret (o bé pel màxim del sub-arbre esquerra).
Arbres AVL (Adel'son-Vel'skîi-Landis)
Un arbre AVL és un arbre binari de cerca tal que per tot node l'alçada del seu seu-arbre esquerre no difereix en més d'una unitat que l'alçada del seu sub-arbre dret.
- Cercar una clau: algorisme idèntic al dels ABC i de cost [latex]O(log n)[/latex].
- Inserir una clau: es fa servir el mateix algorisme dels ABC i desprès, si la propietat de les alçades ja no és certa, es reestructura l'arbre per tal que torni a ser un arbre AVL.
Per tal de dur a terme la reestructuració, cada node ha de contenir informació de la seva alçada. A més, definim el concepte de factor d'equilibri, com a l'alçada del sub-arbre esquerra menys l'alçada del sub-arbre dret; per ser [latex]{-1, 0, 1}[/latex]. Al fer una inserció, el primer node en tenir un mal factor d'equilibri (és a dir, de valor absolut superior a 1) és el node crític i és on caldrà fer una rotació. Podem trobar-nos amb quatre casos:- Inserció al sub-node esquerre del sub-node esquerre del node crític (cas LL, left-left): cal fer una rotació simple.
- Inserció al sub-node dret del sub-node esquerre del node crític (cas LR): cal fer una rotació doble.
- Inserció al sub-node esquerre del sub-node dret del node crític (cas RL): cal fer una rotació doble.
- Inserció al sub-node dret del sub-node dret del node crític (cas RR): cal fer una rotació doble.
El cost d'una inserció és [latex]\theta(h)[/latex] (on h és l'alçada de l'abre, [latex]h = \theta(log n)[/latex]) i el d'una rotació és [latex]\theta(1)[/latex].
- Esborrar una clau: poden caldre fins a [latex]log n[/latex] passos per a rebalancejar l'arbre.
Cues de prioritat
Es creen en temps [latex]O(n)[/latex] amb l'algorisme heapify; són un arbre que compleix la propietat que la clau de tot node és inferior o igual a la clau del node pare.
- Crear una cua de prioritats: [latex]O(n)[/latex].
- Consultar-ne el valor mínim o màxim: [latex]\theta(1)[/latex].
- Esborrar-ne el valor mínim o màxim: [latex]\theta(log n)[/latex].
- Inserir un element: [latex]O(log n)[/latex].
Tipus abstractes de dades de la llibreria estàndard de C++
<stack> | push, pop, top, size, empty | LIFO |
<queue> | push, pop, front, size, empty | FIFO |
priority_queue | push, pop, top, size, empty | ordenada |
pair | Amb <utility>, proporciona operadors (==, >=, <=, etc.) sobrecarregats per a parells de dades. | |
<set> | cost d'inserció: [latex]O(log n)[/latex] begin → de tipus set<…>::iterator end → ídem, referencia l'element següent a l'últim |
You are reading: Apunts d'Estructures de Dades i Algorismes
- Apunts d'Estructures de Dades i Algorismes: Càlcul de costs
- Apunts d'Estructures de Dades i Algorismes: Dividir i Vèncer
- Apunts d'Estructures de Dades i Algorismes: Diccionaris
- Apunts d’Estructures de Dades i Algorismes: Grafs
- Apunts d'Estructures de Dades i Algorismes: Cerca exhaustiva
- Apunts d'Estructures de Dades i Algorismes: Les classes de problemes P i NP
- Apunts d'Estructures de Dades i Algorismes: Programació dinàmica