Algoritmi e strutture dati
•Alberi binari di ricerca (BST)
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
Algoritmi e strutture dati
2
albero binario di ricerca/2
49
22
17
49
82
57
20
22
88
ok
17
94
82
47
20
91
88
errato!
94
91
Algoritmi e strutture dati
3
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
Algoritmi e strutture dati
4
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
Algoritmi e strutture dati
5
rappresentazione
collegata dei nodi
public class BSTNode {
protected Comparable key;
// interface Comparable richiede metodo compareTo
BSTNode leftChild, rightChild; // rappr. minima
public BSTNode() {…}
public BSTNode(Object el) {…}
public BSTNode(Object el, BSTNode lt, BSTNode rt) {…}
public void visit() { key.visit(); }
public boolean isLeaf() {…}
}
Algoritmi e strutture dati
6
public interface Comparable
• public 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
Algoritmi e strutture dati
7
public interface Comparable/2
• 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"
Algoritmi e strutture dati
8
operazioni sui BST
public interface BST {
void clear();
boolean isEmpty();
BSTNode search(BSTNode p, Comparable el);
void insert(BSTNode node);
boolean isInTree(Comparable el);
int getSize();
void inorder(BSTNode p);
void preorder(BSTNode p);
void postorder(BSTNode p);
void breadthFirst();
int treeHeight(BSTNode radice);
}
Algoritmi e strutture dati
9
altre operazioni sui BST
BSTNode
BSTNode
BSTNode
BSTNode
minimum(BSTNode v);
maximum(BSTNode v);
successor(BSTNode v);
predecessor(BSTNode v);
Algoritmi e strutture dati
10
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), …
Algoritmi e strutture dati
11
ricerca in un BST
k(v) = chiave (tipo scalare) associata a nodo v
rt(v) = figlio destro di v
lt(v) = figlio sinistro di v
algorithm search (key k)
t = <root-node>
while(t != null)
if(k(t) > k) t = rt(t);
else if(k(t) < k) t = lt(t);
else return t; // o return k;
return null;
Algoritmi e strutture dati
12
ricerca in un BST/2
versione ricorsiva
algorithm search (key k, node p)
if(p == null)
return null;
if(k == k(p))
return p;
if (k < k(p))
return search(k, lt(p));
else
return search(k, rt(p));
Algoritmi e strutture dati
13
costo della ricerca in un BST
BST di n nodi
• caso peggiore
– O(n)
49
21 52
56
54 67
• caso medio
77
– dipende dalla distribuzione
75
83
• caso migliore
– O(1) (poco interessante)
Algoritmi e strutture dati
14
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)
Algoritmi e strutture dati
15
analisi del caso medio
• IPL (internal path length):
somma lungh. percorsi radice-nodo,
per tutti i nodi
• lungh. media percorso radice-nodo:
IPL/(#nodi)
Algoritmi e strutture dati
16
analisi del caso medio/2
• chiavi 1,…,n presenti in un BST di n nodi (senza
perdita di generalità)
• Pn (i ): percorso medio in BST di n nodi avente
chiave i in radice
• Pn : percorso medio in BST di n nodi
se k(radice) = i
allora
– sottoalbero sx ha
i – 1 chiavi
– sottoalbero dx ha
n – i chiavi
(Pi 1  1)(i  1)  (Pn i  1)(n  i )
Pn (i ) 
n
n
P (i )

i 1 n
Pn 
 ...  O(lgn )
n
Algoritmi e strutture dati
17
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
Algoritmi e strutture dati
18
inserimento in un BST/2
Algorithm insert(key k)
p = root;
while (p != null) {
prev = p;
if (k(p) < k) p = rt(p);
else p = lt(p);
}
if (root == null)
// BST vuoto
root = new BSTNode(k);
else if (k(prev) < k)
rt(prev) = new BSTNode(k);
else lt(prev) = new BSTNode(k);
Algoritmi e strutture dati
fase 1
fase 2
19
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
• la fase 2 si limita a
collegare una nuova
foglia
Algoritmi e strutture dati
60
49
21 52
56
54 67
77
75
83
20
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 )
Algoritmi e strutture dati
49
21 52
56
54 67
60 77
75
83
21
costo dell'inserimento
in un BST
• ogni inserimento introduce una nuova
foglia
• il costo è (proporzionale a) la
lunghezza del ramo radice-foglia
• nel caso peggiore O(n )
Algoritmi e strutture dati
22
cancellazione da un BST
tre casi
1.
cancellazione di una foglia
2. cancellazione di un nodo con un solo figlio
3. cancellazione di un nodo con due figli
Algoritmi e strutture dati
23
cancellazione da un BST/2
cancellazione di una foglia
• basta individuare il nodo genitore e
mettere a null la variabile membro
opportuna (leftChild o rightChild)
• individuare il genitore significa
sostanzialmente effettuare una ricerca
(come nella fase 1 dell'inserimento)
– un approccio alternativo è basato sulla
tramatura dell'albero (i nodi contengono altri
riferimenti, ad es., al genitore)
Algoritmi e strutture dati
24
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
83
83
Algoritmi e strutture dati
25
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
v
w
w
w
w
u
v
Algoritmi e strutture dati
u
v
u
26
cancellazione da un BST/4
cancellazione di 52
49
49
49
21 52
21 52
21 56
56
56
54 67
54 67
54 67
60 77
60 77
75
75
Algoritmi e strutture dati
60 77
75
27
cancellazione da un BST/5
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
– v è foglia o ha un solo figlio
Algoritmi e strutture dati
28
cancellazione da un BST/6
u
u
v
w
u
u
v
w
Algoritmi e strutture dati
w
v
w
29
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
Algoritmi e strutture dati
30