algoritmi e strutture dati
Dizionari
Alberi binari di ricerca (BST)
Dizionari
Associa Informazioni a Chiavi
Tre operazioni fondamentali:



Insert(key)
Remove(key)
Search(key)
Diverse implementazioni possibili
maggio 2003
ASD 02-03
2
Dizionari – Tipo di dato astratto
public interface Dictionary_adt {
void insert(Comparable key );
void remove(Comparable key );
Object search(Comparable key ) ;
}
maggio 2003
ASD 02-03
3
concetto di chiave
insieme di campi di un record che
caratterizza l'intero record

es.: {<nome>, <cognome>, <codiceFiscale>,
<dataNascita>, <indirizzo>}
il <codiceFiscale> è una possibile chiave
spesso in una struttura dati vengono
memorizzate coppie (<chiave>,
<riferimento>), in cui <riferimento> è un
riferimento per l'accesso ad un insieme di
informazioni
maggio 2003
ASD 02-03
4
chiavi
in Java le chiavi sono spesso realizzate
come riferimenti Comparable

solo se occorre stabilire ordinamenti fra
chiavi
talvolta, a scopo esemplificativo, si
usano come chiavi stringhe o interi

facilita la descrizione di una struttura dati
maggio 2003
ASD 02-03
5
interface Comparable
da: documentazione API JFC
richiede metodo int compareTo(Object o)
returns a negative integer, zero, or a positive integer
as this object is less than, equal to, or greater than
the specified Object o



The implementor must ensure sgn(x.compareTo(y)) == sgn(y.compareTo(x)) for all x and y. (This implies that
x.compareTo(y) must throw an exception iff
y.compareTo(x) throws an exception.)
The implementor must also ensure that the relation is
transitive: (x.compareTo(y)>0 && y.compareTo(z)>0)
implies x.compareTo(z)>0
Finally, the implementer must ensure that
x.compareTo(y)==0 implies that sgn(x.compareTo(z)) ==
sgn(y.compareTo(z)), for all z
maggio 2003
ASD 02-03
6
interface Comparable /2
da: documentazione API JFC
It is strongly recommended, but not strictly
required that (x.compareTo(y)==0) ==
(x.equals(y)). Generally speaking, any class
that implements the Comparable interface
and violates this condition should clearly
indicate this fact. The recommended
language is "Note: this class has a natural
ordering that is inconsistent with equals"
maggio 2003
ASD 02-03
7
albero binario di ricerca
albero binario che soddisfa la seguente
proprietà
per ogni nodo, tutte le chiavi nel
suo sottoalbero sinistro sono ≤
della chiave v associata al nodo e
tutti le chiavi nel suo sottoalbero
destro sono ≥ di v
maggio 2003
ASD 02-03
8
albero binario di ricerca/2
49
22
17
49
82
57
20
22
88
ok
17
94
maggio 2003
47
20
91
82
88
errato!
94
91
ASD 02-03
9
albero binario di ricerca/3
indicato spesso come BST (binary search
tree)
utilizzabile quando le chiavi appartengono a
un universo totalmente ordinato
ipotesi semplificativa di lavoro: chiavi
strettamente minori nei sottoalberi sinistri e
strettamente maggiori nei sotto alberi destri
maggio 2003
ASD 02-03
10
rappresentazione dei nodi
in molti casi può essere la stessa usata
negli alberi binari (classe BinaryNode)

in alternativa, la si può estendere
per le variabili membro possiamo usare
lo specificatore di accesso private o
protected

le conseguenze sono differenti
maggio 2003
ASD 02-03
11
rappresentazione
collegata dei nodi/1
public class BSTNode {
protected Comparable key;
protected BSTNode leftChild;
protected BSTNode rightChild;
public BSTNode() {
leftChild = rightChild = null;
}
public BSTNode(Comparable el) {
this(el,null,null);
maggio
} 2003
ASD 02-03
12
rappresentazione
collegata dei nodi/2
protected BSTNode(Comparable el, BSTNode lt, BSTNode rt) {
key = el; leftChild = lt; rightChild = rt;
}
public Comparable getKey() {
return key;
}
public BSTNode getLeftChild() {
return leftChild;
}
public BSTNode getRightChild() {
return rightChild;
}
public void visit() {
maggio 2003
ASD 02-03
13
rappresentazione
collegata dei nodi/3
System.out.print(key.toString());
}
public boolean isLeaf() {
return (leftChild == null) && (rightChild == null);
}
}
maggio 2003
ASD 02-03
14
BST – Tipo di dato astratto
public class BSTree implements Dictionary_adt {
protected BSTNode root = null;
protected int size = 0;
/**
* Creates an empty BSTree
*/
public BSTree(){
}
maggio 2003
ASD 02-03
15
elementi o nodi?
il metodo che implementa l’operazione search
può restituire elementi (Object) o nodi
(BSTNode)

Object
 viene rafforzato l’incapsulamento
 variabili membro protected

BSTNode
 operazioni su sottoalberi
 variabili membro private e metodi accessori/modificatori
il dilemma vale anche per altri metodi

successor, delete (parametro formale), …
maggio 2003
ASD 02-03
16
ricerca in un BST
public BSTNode search(BSTNode p, Comparable
el) {
if(p == null)
return null;
if(el.compareTo(p.key) == 0)
return p;
if (el.compareTo(p.key) < 0)
return this.search(p.leftChild, el);
else
return this.search(p.rightChild, el);
maggio}2003
ASD 02-03
17
ricerca in un BST/2
public BSTNode iterativeSearch(BSTNode p,
Comparable el) {
while (p != null)
if (el.compareTo(p.key) == 0)
return p;
else if (el.compareTo(p.key) < 0)
p = p.leftChild;
else p = p.rightChild;
return null;
}
in questo caso, la versione iterativa non
richiede l'uso di una pila: perché?
maggio 2003
ASD 02-03
18
costo della ricerca in un BST
BST di n nodi
caso peggiore

49
21 52
O(n)
56
caso medio

dipende dalla distribuzione
caso migliore

O(1) (poco interessante)
maggio 2003
ASD 02-03
54 67
77
75
83
19
costo della ricerca in un BST/2
nel caso di distribuzione uniforme
delle chiavi il valore atteso dell'altezza
dell'albero è O(lg n)

N.B. L'altezza di un albero binario di n
nodi varia in {lg2 n + 1,…, n}
 un BST con chiavi uniformemente
distribuite ha un costo atteso di
ricerca O(lg n)
maggio 2003
ASD 02-03
20
analisi del caso medio
IPL (internal path length):
somma lungh. percorsi radice-nodo,
per tutti i nodi
lungh. media percorso radice-nodo:
IPL/(#nodi)
maggio 2003
ASD 02-03
21
analisi del caso medio/2
supp. chiavi 1,…,n presenti in un BST di n nodi
(senza perdita di generalità)
Pn(i): lungh. percorso medio in BST di n nodi avente
chiave i in radice (IPL/#nodi)
Pn: percorso medio in BST di n nodi (IPL/#nodi)
se k(radice) = i allora
– sottoalbero sx ha i – 1
chiavi
– sottoalbero dx ha n – i
chiavi
maggio 2003
ASD 02-03
22
ricerca predecessore in BST
data una chiave a, trovare la chiave
b = pred(a), ovvero la più grande fra le
chiavi < a

operazione sfruttata nell'algoritmo di eliminazione
dove si trova b rispetto a?


se esiste sottoalbero sinistro si trova in tale
sottoalbero
se non esiste sottoalbero sinistro si trova sul
percorso radice – nodo contenente a
maggio 2003
ASD 02-03
23
ricerca predecessore in BST /2
Esiste un sottoalbero sinistro
di u.
cerchiamo pred(k(u)) nel
sottoalbero di radice u
non può essere nel sottoalbero
del figlio destro (chiavi > k(u))
il max nel sottoalbero del figlio
sinistro è un candidato

si tratta del "nodo più a destra",
individuabile scendendo sempre a
destra in tale sottoalbero, fino a
trovare un nodo senza figlio
destro
maggio 2003
ASD 02-03
u
x
v
w
non qui
24
ricerca predecessore in BST /3
Non esiste un
sottoalbero sinistro di u
cerchiamo pred(k(u)) sul
cammino verso la radice
non può essere fuori dal
percorso radice – u (per
le proprietà del BST)
E’ il primo nodo con chiave
minore di u che si incontra
sul cammino verso la radice
maggio 2003
ASD 02-03
v
u
25
ricerca predecessore in BST /4
public BSTNode predecessor(BSTNode p, Comparable el) {
BSTNode pred = null;
while(p != null)
if(el.compareTo(p.key) <= 0)
p = p.leftChild;
else {
pred = p;
p = p.rightChild;
}
return pred;
}
maggio 2003
ASD 02-03
26
ricerca predecessore in BST /5
costo ricerca predecessore
proporzionale all'altezza dell'albero
nel caso peggiore O(n)
la ricerca del successore si realizza in
modo analogo e simmetrico.
costo O(n)
maggio 2003
ASD 02-03
27
inserimento in un BST
nuovo nodo u viene inserito come foglia
fase 1: cerca il nodo genitore v
fase 2: inserisci u come figlio di v
maggio 2003
ASD 02-03
28
inserimento in un BST/2
public void insert(BSTNode node) {
BSTNode p = root, prev = null;
Comparable el = node.getKey();
while (p != null) { // find a place for insert new node;
prev = p;
if (p.key.compareTo(el) < 0)
p = p.rightChild;
else p = p.leftChild;
}
maggio 2003
ASD 02-03
29
inserimento in un BST/3
if (root == null) // tree is empty;
root = node;
else if (prev.key.compareTo(el) < 0){
prev.rightChild = node;
}
else {
prev.leftChild = node;
}
this.size++;
}
maggio 2003
ASD 02-03
30
inserimento in un BST/3
la fase 1 termina quando si
raggiunge un nodo del BST
privo del figlio in cui
avrebbe avuto senso
continuare la ricerca


non necessariamente una
foglia
è il nodo inserito che diviene
foglia
la fase 2 si limita a
collegare una nuova foglia
maggio 2003
ASD 02-03
60
49
21 52
56
54 67
60
77
75
83
31
inserimento in un BST/4
caso peggiore
costo fase 1: O(n )
costo fase 2: O(1)
costo totale: O(n )
caso medio (distrib. unif.)
costo fase 1: O(lg n )
costo fase 2: O(1)
costo totale: O(lg n )
maggio 2003
ASD 02-03
49
21 52
56
54 67
60 77
75
83
32
costo dell'inserimento
in un BST
ogni inserimento introduce una nuova
foglia
il costo è (proporzionale a) la
lunghezza del ramo radice-foglia
interessato all'operazione
nel caso peggiore: O(n)
maggio 2003
ASD 02-03
33
cancellazione da un BST
tre casi


cancellazione di una foglia

cancellazione di un nodo con un solo figlio

cancellazione di un nodo con due figli
maggio 2003
ASD 02-03
34
cancellazione da un BST/2


cancellazione di una foglia


individuare nodo genitore e metterne a null la
variabile membro opportuna (leftChild o
rightChild); se foglia = radice (unico nodo)
mettere a null il riferimento alla radice
individuare genitore significa effettuare una
ricerca (come nella fase 1 dell'inserimento)

maggio 2003
un approccio alternativo è basato sulla tramatura
dell'albero (i nodi contengono altri riferimenti, ad es.,
al genitore)
ASD 02-03
35
cancellazione da un BST/3
cancellazione di 83
49
49
49
21 52
21 52
21 52
56
56
56
54 67
54 67
54 67
60 77
60 77
60 77
75
75
75
maggio 2003
83
ASD 02-03
83
36
cancellazione da un BST/4

cancellazione di un nodo u con un solo
figlio v


individuare genitore w di u; se u è radice v diviene
la nuova radice
se esiste w, sostituire al collegamento
(w,u) il collegamento (w,v)
v
u
maggio 2003
v
w
w
w
w
u
v
ASD 02-03
u
v
u
37
cancellazione da un BST/5
cancellazione di 52
49
49
49
21 52
21 52
21 56
maggio 2003
56
56
54 67
54 67
54 67
60 77
60 77
75
75
ASD 02-03
60 77
75
38
cancellazione da un BST/6

cancellazione di un nodo u con due
figli
(ci si riconduce ad uno dei casi precedenti)
individuare predecessore v (o successore)
di u

v non può avere due figli, altrimenti non sarebbe
predecessore (successore)
copiare la chiave di v al posto di quella di u
cancellare nodo v

maggio 2003
v è foglia oppure ha un solo figlio: caso già
trattato
ASD 02-03
39
cancellazione da un BST/7
u
v
v
v
w
ce
lla
w
v
w
can
w
u
u
copia chiave
u
maggio 2003
ASD 02-03
40
cancellazione da un BST/8
public Comparable remove(Comparable el) {
BSTNode p = root;
BSTNode parent = null;
while(p != null){
if(el.compareTo(p.key) > 0)
parent = p;
p = p.rightChild;
} else if(el.compareTo(p.key) < 0) {
parent = p;
p = p.leftChild;
} else break;
if(p == null) return; // el not in tree
maggio 2003
ASD 02-03
41
cancellazione da un BST/9
// 1st case: p is leaf
if(p.isLeaf())
if(parent == null) // p is root, too
root = null;
else if(parent.rightChild == p)
// p is rightChild
parent.rightChild = null;
else
// p is leftChild
parent.leftChild = null;
maggio 2003
ASD 02-03
42
cancellazione da un BST/10
// 2nd case: p has one child
else if(p.leftChild == null)
// p has only a rightChild
if(parent == null) // p is root, too
root = p.rightChild;
else if(parent.rightChild == p)
// p is rightChild
parent.rightChild = p.rightChild;
else
// p is leftChild
parent.leftChild = p.rightChild;
maggio 2003
ASD 02-03
43
cancellazione da un BST/11
else if(p.rightChild == null)
// p has only a leftChild
if(parent == null) // p is root, too
root = p.leftChild;
else if(parent.rightChild == p)
// p is rightChild
parent.rightChild = p.leftChild;
else
// p is leftChild
parent.leftChild = p.leftChild;
maggio 2003
ASD 02-03
44
cancellazione da un BST/12
// 3rd case: p has 2 children (then it has a predecessor!)
else {Comparable pred = this.predecessor(p.leftChild,
p.key).key;
this.remove(pred); // removing node doesn't have two children!
p.key = pred;
}
size--;
}
maggio 2003
ASD 02-03
45
costo della cancellazione
in un BST
la cancellazione di un nodo
interno richiede
l'individuazione del nodo da
cancellare nonché del suo
predecessore (o
successore)
nel caso peggiore entrambi
i costi sono lineari:
O(n) + O(n) = O(n)
da cancellare
n/2
u
v
n/2
predecessore
maggio 2003
ASD 02-03
46