Dati e Algoritmi

IMPLEMENTAZIONE:

In un albero ogni nodo corrisponde ad un oggetto di tipo position<T> prima della classe

position definisco l’interfaccia dove imposto i metodi generali come T element(); che serve

ad ottenere l’elemento contenuto nel nodo o void setElement(T element) per settare

l’elemento

Posso definire poi l’implementazione effettiva di Position che implementa l’interfaccia e con i

vari attributi T element (valore del nodo), position<T> parent (riferimento al nodo genitore)

e List<Position<T>> children (lista di position riferimento ai children)

(tutti questi attributi conviene metterli private)

L'interfacciaTree<T> rappresenta una struttura ad albero generico che estende un'altra

interfaccia chiamata container, seguono sotto tutti i metodi utili per un albero

Inoltre potrebbero tornare utili i metodi:

- Iterator<T> iterator() restituisce un iteratore per iterare sugli elementi memorizzati

nell albero

- Iterable<Position<T>> position() restituisce un oggetto iterabile dalle posizioni

presenti nell’albero

In pratica con Iterator<T> iterator() si restituisce un iteratore che permette di scorrere tutti

gli elementi contenuti nell’albero, per iteratore si intende una struttura che ti consente di

accedere sequenzialmente agli elementi uno alla volta senza doverli conoscere tutti prima

Il metodo position() invece restituisce una collezione iterabile di oggetti<Position<T>>

che rappresentano i nodi dell'albero.

Differenza tra iterator() e positions():

Con il metodo iterator() accedo direttamente agli elementi dell'albero (elementi(T)), il metodo

positions() invece da accesso ai nodi dell'albero stessi (Position<T>)

i termini //snapshot suggeriscono che questi metodi di iterazione potrebbero utilizzare un

approccio di tipo snapshot iterator

Prima di implementare la Classe Tree devo creare la classe Container da cui erediterò

metodi utili per la gestione dell’albero, questa classe è creata con degli obiettivi:

- deve essere generica così da poter gestire qualsiasi tipo di elemento

- deve fornire metodi fondamentali che possono essere utilizzati anche da una classe

Tree

- deve essere progettata in modo che Tree possa facilmente estenderla e aggiungere

funzionalità specifiche per un albero

Ora dunque posso creare la classe Tree che estende la classe Container che fornirà

funzionalità di base per gestire una collezione di elementi

ESEMPIO IMPLEMENTAZIONE SU UN MAIN:

public class Main {

public static void main(String[] args) {

Tree<String> tree = new Tree<>("Root"); // Crea un albero con radice "Root"

Position<String> root = tree.getRoot(); // Aggiunge figli alla radice

tree.addChild(root, "Child 1");

tree.addChild(root, "Child 2");

Position<String> child1 = root.getChildren().get(0); // Aggiunge un figlio al primo figlio

tree.addChild(child1, "Grandchild 1");

for (Position<String> position : tree.getElements()) { // Stampa gli elementi dell'albero

System.out.println(position.getElement());

}

}

}

ALBERI BINARI:

Un albero binario è un albero ordinato di grado 2 con le seguenti proprietà:

- ogni figlio può chiamarsi destro o sinistro

- in un nodo avente due figli il figlio sinistro precede il destro nell'ordinamento

posizionale dei figlio

- il figlio sinistro viene rappresentato a sinistra e sotto il genitore

- Un albero si dice proprio quando tutti i nodi hanno 2 figli se invece esiste un nodo

con 1 figlio allora si dice improprio

- L’attraversamento in ordine simmetrico attraversa tutti i nodi da sinistra a destra

indipendentemente dalla loro profondità d

- Il livello d di un albero binario da al massimo nodi

2

Un albero binario è completo se:

- Ogni livello dell'albero, tranne eventualmente l'ultimo, è completamente riempito.

- I nodi nell'ultimo livello sono inseriti il più a sinistra possibile.

Dato: ¿ +

n n n n n

n

→ foglie dell’albero → non foglie dell’albero → ❑

e i e i

h → altezza dell’albero

h( v) → altezza del nodo V

(v)

S → sottoalbero sinistro di v

L (v )

S → sottoalbero destro di v

R

In un albero non vuoto:

h

<2

1<n

- [induzione forte su h]

e h

< −1

h<n 2

- [induzione forte su h]

i h+1

- [somma precedenti]

−1

h+1<n< 2

(n+

lo g 1)−1< h<h+1

- [deriva precedente]

2

IMPLEMENTAZIONE:

Interfaccia BinaryTreee<T>

Definisce genericamente un albero binario estendendo l’interfaccia Tree<T>, contiene i

metodi per ottenere il figlio sinistro e destro di un nodo (left e right)e verificarne la presenza

(hasLeft e hasRight)

Interfaccia BTNode<T>

rappresenta un nodo in un albero binario, la sua struttura e data da:

Un elemento (dato generico T) → è il valore memorizzato nel nodo

- riferimento al genitore → nodo da cui discende

- due riferimenti ai figli → left (figlio sinistro)e right (figlio destro) ogni nodo

- può avere al più 2 figli

I metodi principali sono getter e setter dell’elemento, figli e dei genitori, implementando

l’interfaccia Position<T>, ogni nodo è anche una posizione nell’albero, che permette di

accedere all'elemento tramite getElement()

Classe LinkedBinaryTree<T>:

Implementa l’interfaccia BinaryTree<T> e memorizza la dimensione dell'albero (size) e un

riferimento alla radice dell’albero

Metodi: → aggiunge la radice

- addRoot()

e addRight → aggiunge figlio destro o sinistro

- addleft

siblings → per ottenere il nodo fratello

- remove → rimuove un nodo

-

L'interfaccia CompleteBInaryTree estende BinaryTree e aggiunge metodi specifici per

gestire la proprietà di completezza, assicurandosi che:

- Gli elementi vengano aggiunti o rimossi seguendo questa struttura.

- La gestione dell'albero sia ottimizzata per applicazioni che richiedono questa forma

specifica (es., heap binari).

La classe ArrayCompleteBinaryTree<T> è l’implementazione concreta dell interfaccia

CompleteBinaryTree utilizzando un array, e come attributo ha una ArrayList<T> poi

inizializzato nel costruttore e seguono i metodi utili come:

root() → (restituisce null se l’albero è vuoto)

-

- add() e remove() di un nodo (si basa su i metodi della libreria di ArrayList)

Infine la classe ArrayPosition<T> è la classe che serve a rappresentare una posizione in un

albero binario completo che è implementato utilizzando un array, quindi questo incapsula

due informazioni principali ovvero:

elemento → il valore del nodo nell’albero cioè l’oggetto di tipo T che si

- trova nella posizione corrispondente dell’array

indice → la posizione dell elemento nell array fondamentale per navigare

- tra i nodi dell’albero

Code prioritarie: {vero }

f : S × S → , falso

Relazione d’ordine: è una funzione avente la proprietà:

- riflessiva

- transitiva

- antisimmetrica

- totalità [ogni elemento è confrontabile] [non obbligatoria ma rende la relazione totale]

In questo tipo di code ogni elemento ha una “priorità” e gli elementi sono ordinati per priorità,

si può accedere solo all'elemento con priorità maggiore o minore, questi livelli di priorità

devono appartenere ad un insieme totalmente ordinato

Implementazione:

1) Interfaccia Entry<K,V>

Questa interfaccia crea la singola coppia chiave-valore e permette l’accesso alla

chiave e alla modifica e lettura del valore

2) Classe SimpleEntry <K,V> che implementa Entry<K,V>

E’ un implementazione concreta dell’interfaccia Entry, quindi viene usata per creare

effettivamente oggetti che rappresentano una coppia chiave-valore

3) Interfaccia PriorityQueue<K,V> che estende Container

Definisce i metodi che ogni coda prioritaria deve implementare container e quindi

eredita le funzionalità base di una struttura dati contenitore, l’interfaccia definisce in

generale i metodi che ogni coda prioritaria deve implementare

4) Eccezioni varie: InvalidKeyException, EmptyPriorityQueueException

a) InvalidKeyException che estende RuntimeException è un eccezione che viene

lanciata quando si tenta di utilizzare una chiave non valida nella coda prioritaria

b) EmptyPriorityQueueException che estende RunTimeException è un'eccezione che

viene lanciata quando si tenta di accedere a un elemento in una coda prioritaria

vuota

5) Classe Comp che implementa dalla libreria java.util.Comparator<K>

Implementa l’interfaccia Comparator<K> per confontare due chiavi, viene utilizzata dalla

coda prioritaria per determinare l’ordine degli elementi

Il metodo principale è il compare(k k1,k k2) che ritorna:

- Un valore negativo se k1 < k2

- 0 se k1 == k2

- ritorna un valore positivo se k1 > k2

Supporta chiavi generiche (K) purché siano comparable

Utilizzo delle classi e interfacce:

Soffermandosi sulla creazione dell'oggetto ArrayPriorityQueue che è un'implementazione

della cosa prioritaria basata su un array, nelle parentesi specifico i tipi che corrispondono

alle chiavi e ai valori quindi:

- K (le chiavi) saranno di tipo Integer

- V (i valori associati) saranno di tipo String

Passo un comparatore come parametro:

si sta creando quindi un'istanza della classe Comp che implementa l’interfaccia

comparator<K> per confrontare le chiavi

Heap:

E’ un albero completo tale che: (v )=(key

e , val)

- in ciascun nodo è composto da una entry

∀ ∈T ∨v ()⇒ (T (v ))≤ (

v ≠ T . root Key . parent key v)

- → si inserisce un nodo nell’albero in modo da mantenerlo completo

- Insert ≤

poi lo si confronta con il genitore finché non è di esso, se così non è lo si

scambia ⇓

O(log(n))

(Up Heap Bubbling)

→ scambio la radice con il nodo che posso rimuovere

- RemoveMin

mantenendo completo il tutto

parto dalla radice e identifico il figlio w di v avente chiave minima:

- se w > v termino

- se w < v scambio w e v

- procedo con i prossimi figli di v se presenti

⇓

O(log(n))

(Down Heap Bubbling)

→ procedura per trasformare un array in un heap implementato

- Heapify

come un array [possibilità di effettuarlo sul posto o no]

- Sul posto:

Iterando tutto l’array con i e per ogni i si fa un up heap bubbl