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:

  1. [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].
  2. [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:

  1. Suposem que totes les claus són diferents.
  2. 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

Related posts: