Algoritmi e strutture dati Alberi binari di ricerca (BST)

Algoritmi e strutture dati

•Alberi binari di ricerca (BST)

Algoritmi e strutture dati 2

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

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


albero binario di ricerca/249

91

57

8222

17

20

88

94

49

91

47

8222

17

20

88

94errato!ok


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


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


rappresentazionecollegata dei nodi

public class BSTNode {/* Qui può essere presente un campo info */protected Comparable key;

// interface Comparable richiede metodo compareTo

BSTNode left, right; // rappr. minimapublic BSTNode() {…}public BSTNode(Object el) {…}public BSTNode(Object el, BSTNode lt, BSTNode

rt) {…}public void visit() { key.visit(); }public boolean isLeaf() {…}

}


operazioni sui BSTpublic 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);void delete(Comparable el);

}


altre operazioni sui BST

BSTNode minimum(BSTNode v);BSTNode maximum(BSTNode v);BSTNode successor(BSTNode v);BSTNode predecessor(BSTNode v);

D.: quali sono gli elementi max. e min. ?


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), …


ricerca in un BSTBSTNode search(BSTNode p, Comparable el) {

while (p != null) if (el.equals(p.key)) return p; else if (el.compareTo(p.key)<0) p = p.left; else p = p.right; return null; /* Se non lo trova */}


Versione ricorsivaBSTNode search(BSTNode p, Comparable el) { if(p == null)

return null; if (el.compareTo(p.key)<0)

return search(p.left, el); else if (el.compareTo(p.key)>0)

return search(p.right,el);else return p;/* Trovato !! */

}


costo della ricerca in un BST

BST di n nodi• caso peggiore

– O(n)

• caso medio– dipende dalla distribuzione

• caso migliore– O(1) (poco interessante)

49

52

56

67

77

83

54

75

21


• 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)

costo della ricerca in un BST/2


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


inserimento in un BST/2 public void insert(Comparable el) { BSTNode p = root, prev = null; while (p != null) {

prev = p; if (p.key.compareTo(el)<0) p = p.right; else p = p.left; } if (root == null) // albero vuoto; root = new BSTNode(el); else if (prev.key.compareTo(el)<0) prev.right = new BSTNode(el); else prev.left = new BSTNode(el); }

fase 1

fase 2


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

49

52

56

67

77

83

54

75

21

60


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 )

49

52

56

67

77

83

54

75

21

60


costo dell'inserimentoin un BST

• ogni inserimento introduce una nuova foglia

• il costo è (proporzionale a) la lunghezza del ramo radice-foglia

• nel caso peggiore O(n )


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


cancellazione da un BST/2

cancellazione di una foglia• basta individuare il nodo genitore e

mettere a null la variabile membro opportuna (left o right)

• 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)



cancellazione di 83

49

52

56

67

77

83

54

75

21

60

49

52

56

67

83

54

75

21

60

49

52

56

67

77

54

75

21

6077



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 )

w

uv

w

uv

w

uv

u v

w



cancellazione di 52

49

52

56

67

77

54

75

21

60

49

56

67

77

54

75

21

60

49

52

56

67

77

54

75

21

60



cancellazione di un nodo u con due figli (ci si riconduce ad uno dei casi precedenti – cancellazione per copiatura)

• individuare predecessore v (o successore) di u (secondo il valore della chiave)– 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


cancellazione per copiatura

u

v

u

v

cop

ia c

hia

ve

w w w

u u

w

canc

ella

v v


Cancellazione per copiatura/2

public void deleteByCopying(Comparable el) {BSTNode node, p = root, prev = null;

while (p != null && !p.key.equals(el)) {prev = p; if (p.key.compareTo(el)<0)

p = p.right; else p = p.left; } node = p;

/* Cerca il nodo *//* Continua alla prossima slide ..... */



/* Dalla slide precedente .... */

if (p != null && p.key.equals(el)) { if (node.right == null)

node = node.left; else if (node.left == null)

node = node.right; /* Casi semplici: il nodo ha un solo figlio */

/* Continua .... */




else { /* Due figli .... */ BSTNode tmp = node.left;

BSTNode previous = node; while (tmp.right != null) {

previous = tmp; tmp = tmp.right;

} node.key = tmp.key;

/* Copia anche info se presente */if (previous == node)

previous.left = tmp.left; else previous.right = tmp.left;

} /* Continua ... */




if (p == root) /* Trova padre nuovo nodo */

root = node; else if (prev.left == p) prev.left = node; else prev.right = node; } else if (root != null) System.out.println(“Elemento assente”); else System.out.println(“Albero vuoto");}


u

costo della cancellazionein 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 )

n/2

n/2da cancellare

predecessore

v


Cancellazione per fusione

u

v

x

u: nodo da cancellarex: nodo predecessore di u

v

x w

w


Domande

• Si implementi il metodo di visita in ordine simmetrico

• Cosa produce la visita simmetrica se le chiavi sono stringhe?

• Perché per implementare le basi di dati si usano alberi e non array?

Algoritmi e strutture dati Alberi binari di ricerca (BST)

Documents

Transcript of Algoritmi e strutture dati Alberi binari di ricerca (BST)