Rappresentazione dei grafi attraverso strutture dati

Esistono due modi per rappresentare un grafo $G$ di $V$ vertici ed $E$ archi (indicato con $G = (V, E)$), ed entrambi permettono di descrivere qualsiasi tipo di grafo: orientato o meno, pesato o meno, collegato o meno, denso o sparso, e così via.

Strutture dati: Alberi rosso-neri

Un albero rosso-nero (o Red-Black tree, RB Tree) è un albero binario di ricerca (si veda [4]) che riesce a mantenersi bilanciato grazie all'osservazione e al rispetto delle seguenti proprietà:

1- Ogni nodo è rosso o nero
2- La radice è nera
3- Tutte le foglie sono nere (puntatori nulli sono considerati neri)
4- Entrambi i figli di un nodo rosso sono neri
5- Tutti i cammini che vanno da un nodo qualsiasi ad una delle foglie contengono lo stesso numero di nodi neri

Per il resto, condivide tutte le caratteristiche che contraddistinguono gli alberi binari di ricerca, compreso il tempo di esecuzione di molte operazioni eseguite sull'albero.

Strutture dati: Alberi binari di ricerca

Un albero binario di ricerca (o binary search tree, BST) è un albero binario non bilanciato in cui ogni elemento (o nodo) $x$ dell'albero rispetta la seguente proprietà:

$y.value \le x.value$, se $y$ è un nodo nel sottoalbero sinistro di $x$.
$y.value \ge x.value$, se $y$ è un nodo nel sottoalbero destro di $x$.

Grazie a questa interessante proprietà si possono eseguire molte operazioni in tempo $O(\log n)$ (con $n$ numero di elementi dell'albero) se si riesce a mantenere un certo grado di bilanciamento nell'albero. In questo caso $O(\log n)$ è proprio l'altezza dell'albero.

Strutture dati: Hash table

Le tavole di hash sfruttano la principale caratteristica degli array di elementi contigui: poter accedere ad un elemento in tempo costante $O(1)$ se si conosce l'indice dell'elemento, anche quando il numero di elementi è estremamente elevato. In questo caso, però, usando un semplice array il consumo di memoria potrebbe rivelarsi un problema. Le Hash table, invece, limitano il consumo di memoria e mantengono il tempo di 'accesso agli elementi quanto più possibile vicino a $O(1)$ usando una combinazione di array e liste concatenate (si faccia riferimento all'immagine sotto nel prosieguo della lettura).

Strutture dati: Linked list

Le liste concatenate (doppiamente e non ordinate in questo caso) sono facilmente implementabili se si utilizzano strutture dati che mantengono puntatori agli elementi precedenti e successivi, oltre che ai dati propri di ogni elemento.

Strutture dati: Stack e Code

Stack e code sono strutture dinamiche basate sui classici metodi di transito per gli elementi su una coda (FIFO, First In Fist Out) o in una pila/stack (LIFO, Last In Fist Out).


Stack

Per l'implementazione è sufficiente un array e una variabile che mantenga l'elemento in cui inserire il successivo elemento. Un'ulteriore variabile è utilizzata per il numero di elementi dell'array usato come stack, che rappresenta quindi il numero massimo di elementi che si possono inserire su tale stack.