Appunti di Programmazione e algoritmica

ALBERI BINARI DI RICERCA

Gli alberi binari di ricerca sono delle strutture dati che permettono molte operazioni sugli insiemi dinamici tra cui:

1. INSERIMENTO (di chiavi ed elementi)
2. CANCELLAZIONE (di)
3. RICERCA = cerco una chiave tra gli elementi del mio insieme e la sia uguale all'input della chiave di ricerca
4. MINIMO (MINIMUM) nel mio insieme
5. MAX (MAXIMUM)

Dove nel campo di ricerca avremo a sua volta due varianti, ossia:

1. PREDECESSORE = dato una chiave "x", mi permette di CERCARE lo massimo chiave nell'insieme che sia minore di "x" (ad esempio, dato un insieme con numeri 5,6,8,10 prendo come riferimento il "6" e posso dire che il suo predecessore e il 5).
2. SUCCESSORE = Analoga definizione per il predecessore.

N.B. tutte le strutture dati che vedremo manipolano le chiavi dato che la ricerca e le modifiche vengono effettuate in termini di chiavi che identificano l'oggetto.

Per implementare questi alberi binari di ricerca faremo l'uso delle liste, ad esempio...

...in una lista non ordinato (precedente) avremo i seguenti costi (in tempo):

1. RICERCA (che deve partire dalla testa e scansionare tutti gli elementi per trovare la chiave corretta) O(n).

2)

INSERIMENTO (inserendo [ad esempio] un nuovo elemento in testa mi costa un tempo costante O(1)). Esso consiste nell'inserire un nuovo nodo in testa, ovvero 1), successivamente modifico il campo successore (ovvero ho una testa precedente) e quindi la testa viene spostata nel nodo 1, che in termini pratici sarà...

₁ → ₆ → ₆ → ₈ → ₅

HEAD

3)

CANCELLAZIONE (ha la caratteristica di scandire tutta la lista partendo dalla testa, quindi non arrivo alla fine di ricerca [ovvero so nel mio caso per poi cancellarlo...] modificando il puntatore e infine cancellarlo, che in termini pratici sarà...

₁ → ₆ → ₆ → ₈ → ₅

HEAD EFFETTUATO

e di conseguenza ha un tempo costante la modifica del puntatore, ma il costo maggiore di questa cancellazione è la ricerca della fine (1^2) poiché devo scandire tutta la lista, quindi il costo sarà O(n)

4)

min (essendo che fa una lista non ordinata, devo scandire TUTTA le liste per trovare il nuovo tenendo sempre traccia del nuovo trovato, quindi il costo sarà O(n))

5)

MAX (Anche se riferimento fatto precedentemente con la ricerca del min, quindi deduco che anche per la ricerca del MAX il costo sarà O(n))

Ma quale delle tre visite (anticipata posticipata simmetrica) ci permette di stampare i valori in modo ordinato (crescente)?

Dato il seguente albero binario

la sua visita che ci permette di stampare i valori in modo ordinato è quella simmetrica, e il suo pseudocodice corrispondente è:

Simmetrica (x)

if x ≠ NULL

Simmetrica (x.left) print (x.key) Simmetrica (x.right)

N.B. la visita simmetrica cos’è?

Prima di visitare il nodo x corrente, visita prima il sottoalbero sinistro (trovando elementi < x del nodo x) e li stampa e sx di x, e successivamente stampa gli elementi trovati nel sottoalbero dx di x (trovando elementi ≥ x) e li posiziona a dx di x, ovvero

2 5 5 x 7 8 —>> lista completa degli elementi ordinati, considerando Θ(n) il costo di tutte le operazioni. Visita sotto albero sx + stampa e ordinamento Visita sottoalbero dx + stampa e ordinamento.

Il costo complessivo nel tempo è O(h) perchè nel primo caso, finora al massimo h è il minimo che verrà in cammino verso la foglia più a sinistra del sottoalbero. Anche nel secondo caso il tempo è O(h) perchè da un modo fa la possibilità di salire fino alla radice e quindi spendere un tempo che è dipeso dell'altezza dell'albero (O(h)).

RICERCA DEL PREDECESSORE NEGLI ALBERI BINARI

Come nella ricerca del successore, i predecessori e i sopramenzionati sono simetrici. Quando facciamo riferimento all'ABR dispresto precedentemente, scrivo il nostro ALGORITMO PSEUDOCODICE.