Appunti di Advanced algorithms and graph mining

Alberi

Un nodo dell'albero è chiamato radice. Ogni nodo eccetto la radice, è connesso da un arco esattamente ad un altro nodo dove è il genitore di (ovvero ha un solo genitore).

C'è un solo cammino dalla radice ad ogni nodo.

N.B: albero binario - ogni nodo nell'albero ha al massimo due figli, parliamo di albero binario.

Supponiamo di avere un albero come quello nella figura seguente, i cui nodi contengono chiavi intere tutte diverse in un intervallo limitato [0, b].

Possiamo rappresentare questo albero attraverso una semplice lista di dimensione do-b, dove in ogni posizione viene memorizzata la chiave del padre relativo al nodo con chiave i (eccetto il nodo radice che ha come nodo padre sé stesso).

Quindi, tale albero può essere memorizzato attraverso la seguente lista.

Nel caso in cui le chiavi non siano dei valori interi, possiamo memorizzare l'albero attraverso un dizionario, associando ad ogni chiave

il suo unico padre. Dobbiamo però tenere presente che la ricerca dell'elenco di tutti i nodi figli relativi ad una chiave, necessita di scorrere l'intera lista (o tutti i valori del dizionario). Dunque tale operazione ha un costo O(n), dove n è il numero di nodi dell'albero.

Possiamo sfruttare la definizione ricorsiva per rappresentare un albero con una lista di liste. In particolare, memorizziamo il valore della radice come primo elemento della lista. Il secondo elemento della lista sarà una lista che rappresenta il sottoalbero sinistro, mentre il terzo elemento della lista rappresenta il sottoalbero destro. Per illustrare questa strategia di memorizzazione, osserviamo l'esempio in figura, che mostra un semplice albero con le liste corrispondenti.

N.B: possiamo accedere ai sottoalberi della lista usando l'operatore di indicizzazione delle liste. myTree = ['a', #root['b', #left subtree['d', [], []],['e', [],

[['c', ['f', [], []], []]]
Il seguente codice illustra come creare un semplice albero usando la struttura delle li-ste. Una volta costruito l’albero, possiamo accedere alla radice ed ai suoi sottoalberi(ad esempio, la radice dell’albero sarà accessibile con <code>myTree[0]</code> ed il suo sottoalbero sinistro sarà accessibile con <code>myTree[1]</code>).
Una proprietà importante di questa implementazione con una lista di liste è che la struttura della lista che identifica un sottoalbero rappresenta ancora un albero. Dun-que, la struttura dati stessa è ricorsiva.
Inoltre, un sottoalbero che ha una radice e due liste vuote come sottoalberi è una fo-glia.
Infine, questa struttura può essere generalizzata ad un numero arbitrario di sottoalberi.

1 myTree = ['a', ['b', ['d', [], []], ['e', [], []]], ['c', ['f', [], []], []]]
→,23 print(myTree)
4 print('left

subtree = ', myTree[1])
print('root = ', myTree[0])
print('right subtree = ', myTree[2])

Formalizziamo questa definizione della struttura dati, fornendo alcune funzioni che rendono l'uso delle liste più comodo.

CAPITOLO 5. ALBERI

La funzione costruisce semplicemente un albero che ha una radice e due liste vuote come sottoalberi.

def BinaryTree(r):
    return [r, [], []]

Per aggiungere un sottoalbero sinistro alla radice di un albero, abbiamo bisogno di inserire una nuova lista in seconda posizione della lista radice. Però, se la lista radice possiede già un elemento in seconda posizione, allora tale elemento diventerà il sottoalbero sinistro della nuova lista che stiamo aggiungendo.

Perciò, per inserire un figlio sinistro, dobbiamo ottenere la lista (eventualmente vuota) che corrisponde al figlio sinistro corrente. Quindi, aggiungiamo il nuovo figlio sinistro, posizionando il vecchio figlio sinistro come figlio

sinistro del nuovo elemento. Questo permette di inserire un nuovo nodo nell'albero in qualsiasi posizione.


def insertLeft(root, newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1, [newBranch, t, []])
    else:
        root.insert(1, [newBranch, [], []])
    return root


Il codice per inserire un figlio destro è simile al precedente.


def insertRight(root, newBranch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2,[newBranch, [], t])
    else:
        root.insert(2,[newBranch, [], []])
    return root


Per completare la struttura, scriviamo una coppia di funzioni di accesso per ottenere o impostare il valore della radice o quello dei sottoalberi sinistro e destro.


def getRootVal(root):
    return root[0]

def setRootVal(root, newVal):
    root[0] = newVal

def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]


Possiamo invece sfruttare la definizione classica per rappresentare un albero attraverso nodi e riferimenti. In questo caso, definiamo una classe che ha

<div class="BinaryTree">
    <div class="root">
        <span class="key">attributi</span>
    </div>
    <div class="leftChild">
        <span class="key">left</span>
    </div>
    <div class="rightChild">
        <span class="key">right</span>
    </div>
</div>

Il codice per considera un insieme di casi simmetrico. Anche in questa situazione dobbiamo distinguere il caso in cui non sia presente un figlio destro oppure nel caso in cui dobbiamo inserire il nuovo elemento tra il nodo padre ed il figlio destro esistente.

def insertRight(self, newNode):
    if self.rightChild == None:
        self.rightChild = BinaryTree(newNode)
    else:
        t = BinaryTree(newNode)
        t.rightChild = self.rightChild
        self.rightChild = t

newNode):2 if None:self.rightChild ==3 self.rightChild = BinaryTree(newNode)4 else:5 t = BinaryTree(newNode)6 t.rightChild = self.rightChild7 self.rightChild = t

CAPITOLO 5. ALBERI 52

Per completare la definizione della struttura dati, scriviamo metodi di accesso per la
radice ed i sottoalberi sinistro e destro.

def getRightChild(self):
    return self.rightChild

def getLeftChild(self):
    return self.leftChild

def setRootVal(self, obj):
    self.key = obj

def getRootVal(self):
    return self.key

5.1 Visite di alberi

Adesso che abbiamo esaminato le funzionalità di base della struttura dati, analizziamo
il loro uso comune. Le forme con cui un albero può essere interrogato possono essere
divise in tre. La differenza è l'ordine con cui vengono visitati i nodi. Chiamiamo questa
attraversamento visita dei nodi dell'albero. Le tre visite che analizziamo sono dette:
- (preorder). In una visita anticipata, visitiamo prima la radice, quindi
anticipata eseguiamo

ricorsivamente una visita anticipata del sottoalbero sinistro seguita da una visita anticipata del sottoalbero destro.

Ad esempio, consideriamo l'albero di un libro, dove ogni "Chapter" è un figlio della radice "Book". Supponiamo di voler leggere questo libro dall'inizio alla fine. La visita anticipata fornisce esattamente questo ordine. Partendo dalla radice (ovvero il nodo "Book"), richiamiamo ricorsivamente preorder sul figlio sinistro (ovvero "Chapter1"). Chiamiamo ancora ricorsivamente preorder sul figlio sinistro per ottenere la "Section 1.1". Dal momento che "Section 1.1" non ha figli, non facciamo ulteriori visite ricorsive.

Quindi, ci muoviamo al livello superiore dell'albero. A questo punto abbiamo ancora bisogno di visitare il sottoalbero destro di "Chapter 1", ovvero "Section 1.2". Quindi, visitiamo il suo sottoalbero sinistro (ovvero "Section 1.2.1").

ed il suosottoalbero destro (ovvero “Section 1.2.2”). Perciò, ritorniamo al nodo “Book” eseguiamo la stessa procedura per “Chapter 2”.

Il seguente codice mostra una versione di visita anticipata, scritta come funzio-ne esterna che prende un albero binario come parametro. Il caso base controlla semplicemente se l’albero esiste. Se il parametro è allora la funzionetree None,

CAPITOLO 5. ALBERI 53