Algoritmi e Laboratorio a.a. 2006-07Lezioni

(1)

Università di Torino – Facoltà di Scienze MFN Corso di Studi in Informatica

Curriculum SR (Sistemi e Reti)

Algoritmi e Laboratorio a.a. 2006-07 Lezioni

prof. Elio Giovannetti

Parte 16 – Alberi binari

Quest' opera è pubblicata sotto una Licenza Creative Commons Attribution-NonCommercial-ShareAlike 2.5.

22/02/2007 E. Giovannetti - AlgELab-06-07 - Lez.16 2

Una definizione induttiva di albero binario astratto

• L'albero vuotoè un albero binario di elementi di tipo E:

empty

• Se T1e T2sono due alberi binari di elementi di tipo E, ed elè un valore di tipo E:

T1 T2 el

el

T1 T2

allora (T1 el T2)è un albero binario di elementi di tipo E:

(2)

Notazione lineare infissa per alberi binari.

Esempio: 12

5 20

8 5 8 16

7

4 11

3

per brevità, indichiamo qui l'albero vuoto con il simbolo •, e omettiamo la coppia di parentesi più esterne:

(((•3•) 8 •) 5((•4•) 5 (•11•)))12 ((•8•) 20((•7•) 16 •))

Notazioni prefissa e postfissa.

• Si noti che la scelta, nella rappresentazione lineare con parentesi, di scrivere la radice fra i due sottoalberi, è arbitraria; si può scegliere invece di scriverla prima dei due sottoalberi, oppure dopo; ad esempio, notazione prefissa:

12 (5 (8 (3••) •) (5 (4••) (11••)) (20 (8••) (16 (7••) •)) postfissa: (((••3) • 8) ((••4) (••11) 5) 5) ...

12

5 20

8 5 8 16

7

4 11

3

Tuttavia la notazione infissa risulterà partcolarmente utile per gli alberi binari di ricerca.

(3)

Principio di induzione strutturale su alberi binari

Se per una proprietà valgono i due fatti seguenti:

• essa vale per l'albero vuoto;

• quando vale per due alberi T1 e T2, in tal caso vale per l'albero (T1 el T2);

allora essa vale per tutti gli alberi binari.

Tuttavia, per dimostrare proprietà di alberi binari può essere necessario usare, invece del principio di induzione strutturale, il principio di induzione ordinario (ad es. sull'altezza dell'albero).

Realizzazione di alberi binari "in stile C"

• Si rappresenta l'albero vuoto come null.

• Si rappresenta un albero non vuoto come una struttura.

• In Java (usato in stile C) ciò si realizza nel modo seguente:

public class BinTree { // in Java le strutture diventano oggetti protected String element;

protected BinTree left, right;

public BinTree(String element, BinTree left, BinTree right) { this.element = element;

this.left = left;

this.right = right;

}

public BinTree(String element) { this(element, null, null);

}

... con metodi tutti statici (vedi slides successive).

(Nota: il codice C vero e proprio sarà presentato direttamente nelle slides sugli alberi binari di ricerca)

(4)

Alberi e ricorsione.

• Il tipo-albero, come il tipo-lista, è un tipo ricorsivo, perché è definito in termini di se stesso, in accordo con la definizione induttiva di albero in senso astratto.

• La programmazione ricorsiva è quindi particolarmente adatta a questo tipo di dato:

• in particolare, i problemi che richiedono una visita per profondità di tutto l'albero hanno soluzioni naturali con ricorsione ramificata, e quindi inerentemente ricorsive, cioè tali che le corrispondenti procedure iterative sono non banali e devono fare uso di uno stack esplicito;

• i problemi che invece richiedono di percorrere un solo cammino lineare nell'albero, ad esempio dalla radice a una foglia, e che quindi presentano una ricorsione lineare (anche se non di coda), possono essere risolti in modo naturale (e più efficiente) anche iterativamente (benché ciò risulti talvolta, come vedremo, un po' più complicato).

Alberi binari alla C: visite in preordine e inordine.

public static void printPreOrder(BinTree t) { if(t != null) {

System.out.println(t.element);

printPreOrder(t.left);

printPreOrder(t.right);

} }

public static void printPreOrder(BinTree t) { while(t != null) {

t = t.right;

} }

Eliminando la ricorsione di coda:

Analoghe le due versioni della visita in inordine.

(5)

Alberi binari alla C: visite in postordine.

public static void printPostOrder(BinTree t) { if(t != null) {

printPostOrder(t.left);

printPostOrder(t.right);

} }

Nessuna delle due chiamate ricorsive è di coda.

Si noti che i tre generi di visita corrispondono alle tre notazioni lineari introdotte in precedenza.

La sequenza che si ottiene dalla stampa in ciascun ordine è infatti la sequenza data dalla notazione corrispondente ove si tolgano le parentesi e i nodi vuoti.

Alberi binari alla C: altri esempi.

Si possono definire, per mezzo di metodi statici, tutte le procedure sugli alberi cui si è interessati.

Esempi:

altezza di un albero:

import static java.lang.Math.max;

...

public static int height(BinTree t) {

if(t == null) return -1; (oppure 0, a seconda di come si conta) else return 1 + max(height(t.left), height(t.right));

}

numero dei nodi:

...

ecc.

(6)

Alberi binari alla C: uso.

Se la classe BinTree è definita in un package rectrees:

import rectrees.*;

import static rectrees.BinTree.*;

...

BinTree leaf1 = new BinTree("Ada");

BinTree leaf2 = new BinTree("Edo");

BinTree leaf3 = new BinTree("Ugo");

BinTree bt1 = new BinTree("Giorgio",leaf1,leaf2);

BinTree bt2 = new BinTree("Paolo",leaf3,null);

BinTree bt3 = new BinTree("Eva",bt1,bt2);

printPreOrder(bt3);

System.out.println();

System.out.println(height(bt3));

...

Alberi e programmazione a oggetti

• Nello stile di programmazione a oggetti, ovviamente, le procedure che agiscono sugli alberi non sono metodi statici che agiscono su alberi passati come argomenti, bensì metodi di istanza che agiscono sull'oggetto this.

(7)

Alberi e programmazione a oggetti.

• Analogamente al caso delle liste concatenate, nella realizzazione alla C l'albero vuoto non è un oggetto, e quindi non è possibile definire metodi di istanza che siano applicabili a qualunque albero.

• Due generi di soluzioni:

• mantenere l'albero come tipo ricorsivo, ma introdurre un oggetto esplicito per rappresentare l'albero vuoto;

• come nel caso delle liste, definire una classe (magari annidata) Nodo(o Node) ricorsiva, con una classe circondante Albero(o BinTree) che contiene solo il riferimento alla radice.

• La scelta più comune è la seconda, ma i due generi di soluzioni possono anche essere combinati, nel senso che si può decidere di rappresentare il nodo "vuoto" con un oggetto invece che con null (ciò ha vantaggi e svantaggi), come faremo nella implementazione degli alberi AVL.

1) Albero come tipo ricorsivo con albero vuoto come oggetto

public class BinTree { protected String element;

protected BinTree left, right;

public BinTree(String el, BinTree l, BinTree r) { element = el;

left = l;

right = r;

}

public BinTree() { // rappresenta l'albero vuoto this(null,null,null);

}

public BinTree(String element) {

this(element, new BinTree(), new BinTree());

} ...

Svantaggi: occupazione di memoria; inoltre è possibile costruire alberi che hanno fisicamente in comune dei sottoalberi, e che quindi non sono, a rigore, dei veri alberi (ma piuttosto dei grafi).

(8)

Albero come tipo ricorsivo con albero vuoto come oggetto (continua)

public boolean isEmpty() { \\ stabilisce se è vuoto

return element == null && left == null && right == null;

}

I metodi statici della realizzazione "alla C", che prendevano un albero come argomento, diventano metodi di istanza (aventi quindi come parametro implicito this).

Albero come tipo ric. con albero vuoto come oggetto: visite.

La procedura alla C:

public static void printPreOrder(BinTree t) { if(t != null) {

printPreOrder(t.right);

} }

diventa un metodo di istanza:

public void printPreOrder() { if(!isEmpty()) {

System.out.println(element);

left.printPreOrder();

right.printPreOrder();

} }

(9)

Eliminazione della ricorsione di coda

Naturalmente tale metodo ha una chiamata ricorsiva di coda.

Come si elimina ? Ricorda che un metodo di istanza è una procedura con un parametro implicito this, come se fosse:

public static void printPreOrder(BinTree questo) { if(questo.isEmpty()) {

System.out.println(questo.element);

questo.left.printPreOrder();

questo.printPreOrder();

} }

eliminandola si otterrebbe:

public static void printPreOrder(BinTree questo) { while(!questo.isEmpty()) {

questo.left.printPreOrder();

questo = questo.right;

} }

Eliminazione della ricorsione di coda (continua)

Tuttavia, come sappiamo bene, il parametro implicito this non può essere modificato. Occorre quindi prima assegnarlo ad una variabile locale del metodo:

public void printPreOrder() { BinTree t = this;

while(!t.isEmpty()) {

t.left.printPreOrder();

t = t.right;

} }

Realizzazioni analoghe per la visita in inordine.

(10)

Albero come tipo ric. con albero vuoto come oggetto: uso.

...

BinTree empty = new BinTree();

BinTree leaf1 = new BinTree("Ada");

BinTree leaf2 = new BinTree("Edo");

BinTree leaf3 = new BinTree("Ugo");

BinTree bt1 = new BinTree("Aldo",leaf1,leaf2);

BinTree bt2 = new BinTree("Luca",leaf3, empty);

BinTree bt3 = new BinTree("Eva",bt1,bt2);

bt3.printPreOrder();

...

BinTree bt4 = new BinTree("Adamo",bt1,bt2);

crea un albero che condivide con Eva tutti i discendenti.

2) Alberi binari con classe-nodo annidata nella classe-albero, e nodo vuoto rappresentato da null.

In Java una classe annidata può essere dichiarata statica oppure no: a seconda della scelta, si possono avere delle lievi differenze di implementazione.

(Lo studio preciso dei significati dei due generi di classi annidate esula dagli scopi del corso; chi è interessato può rivolgersi ai docenti).

Nota. Nella terminologia ufficiale Java:

• una classe annidata non dichiarata statica viene detta classe interna (inner class).

• le classi annidate statiche nonsono classi interne.

(11)

Alberi binari con classe-nodo annidata:

realizzazioni ricorsive dei metodi.

• Nella realizzazione con classe-nodo annidata, il tipo ricorsivo corrispondente al tipo-albero (BinTree) dell'esempio C è il tipo-nodo (Node) e non il tipo-albero.

• Pertanto un metodo pubblico richiamabile dall'esterno non può essere direttamente un metodo ricorsivo, bensì deve essere un semplice metodo che invoca un corrispondente metodo ricorsivo sui nodi.

• I metodi ricorsivi sui nodi possono essere in modo naturale definiti come metodi di istanza (= non statici) della classe nodo, oppure – meno elegantemente – come metodi statici della classe-albero.

• La classe-nodo non deve essere visibile dall'esterno: così non sarà possibile costruire alberi che condividano nodi, a meno che tale possibilità sia consapevolmente prevista, in modo controllato, dal realizzatore della classe-albero.

2.1) Alberi binari con classe Node annidata statica, e nodo vuoto rappresentato da null.

public class BinTree {

private static class Node { String element;

Node left, right;

Node(String element, Node left, Node right) {

this.element = element;

this.left = left;

this.right = right;

} ...

(12)

private static class Node { ...

}

private Node root; //

public BinTree() { root = null;

} ...

}

Come nel caso delle liste, un metodo ricorsivo può essere definito nella classe Node:

void printPreOrder() {

System.out.println(element);

if(left != null) left.printPreOrder();

if(right != null) right.printPreOrder();

}

e richiamato sulla radice dal metodo omonimo della classe circondante:

public void printPreOrder() {

if(root != null) root.printPreOrder();

}

(attenzione: non è possibile eliminare la ricorsione di coda secondo il semplice schema illustrato in precedenza )

(13)

Alberi binari con classe Node annidata statica: esempi.

Altezza dell'albero (vedi Prog. 2 corso A) Una possibile realizzazione

Nella classe Node:

int height() {

int leftHeight = -1;

int rightHeight = -1;

if(left != null) leftHeight = left.height();

if(right != null) rightHeight = right.height();

return 1 + Math.max(leftHeight , rightHeight);

}

Nella classe BinTree:

public int height() { return root.height();

}

Alberi binari con classe Node annidata statica: esempi.

Altezza dell'albero (vedi Prog. 2 corso A)

Un'altra realizzazione, meno object-oriented ma più facile:

static int height(Node nd) { if(nd == null) return -1;

else return 1 + max(height(nd.left),height(nd.right));

}

Nella classe BinTree:

public int height() {

return Node.height(root);

}

(14)

2.2) Alb. binari con classe Node interna (non statica).

private class Node { String element;

Node left, right;

Node(String element, Node left, Node right) { this.element = element;

this.left = left;

this.right = right;

} ...

}

private Node root;

...

}

Esempio: altezza dell'albero

Il metodo:

int height(Node nd) {

if(nd == null) return -1;

else return 1 + max(height(nd.left),height(nd.right));

}

non può essere statico, poiché la classe Node, tipo del parametro nd, non è statica; esso deve quindi essere dichiarato (come metodo di istanza) nella classe BinTree.

L'altra realizzazione del metodo altezza (slide 25), invece, resta invariata.

(15)

Esercizio

Negli esempi precedenti di albero con classe-nodo interna privata non è descritto né specificato come si aggiungono (o tolgono) nodi ad un albero; non è quindi descritto come si fa a costruire un albero non vuoto.

Negli alberi binari di ricerca verranno definiti gli opportuni metodi di inserimemto e cancellazione.

Per sperimentare con alberi generici si definisca invece, nella classe BinTree – richiamando un omonimo metodo ricorsivo di BinTree o di Node – un metodo add il quale, dato un elemento (ad es. stringa, o intero, ecc.) e una stringa costituita da una sequenza di caratteri L (per Left) o R (per Right), scende nell'albero successivamente a destra o a sinistra e va a creare ed inserire una nuova foglia al fondo del cammino descritto. Se al fondo del cammino non c'è una foglia null in cui inserire un nuovo nodo, lancia un'eccezione.

Esercizio (continua)

Se la foglia null viene raggiunta prima che la "stringa-path"

sia terminata, il nuovo nodo viene creato ed inserito in quel punto, trascurando la parte restante della stringa-path.

Esempio:

BinTree bt = new BinTree();

bt.add("Eva","");

bt.add("Giorgio", "L");

bt.add("Paolo", "RLLR"); // funziona, fermandosi alla prima R bt.add("Ada", "LL");

bt.add("Edo", "LR");

bt.add("Ugo", "RR");