Post on 16-Oct-2020
transcript
ADT albero binario completoADT albero binario completo
Strutture Dati
Un albero binario completo è un albero binario in cui ogni livello, fino al penultimo, è completamente riempito. L'ultimo livello è riempito da sinistra a destra
a
b
d e f g
c
h i l m n
1 nodo
2 nodi
4 nodi
livelli completamente riempiti:contengono il massimo numero possibile di nodi
l'ultimo livello può contenere un numero di nodi inferiore al massimo possibile, ma deve essere riempito da sinistra a destra
ADT albero binario completoADT albero binario completo
Strutture Dati
L'ADT albero binario completo è un caso speciale dell'ADT albero binario
Metodi aggiuntivi:
add(e): aggiunge e restituisce un nuovo nodo esterno (foglia) v che memorizzerà l'elemento e in modo tale che il risultante albero sia
un albero binario completo avente v come ultimo nodo
remove(): rimuove l'ultimo nodo dell'albero restituendo il suo elemento
a
b
d e f g
c
h i l m n
ultimo nodo
ADT albero binario completoADT albero binario completo
Strutture Dati
Relativamente all'operazione di add si possono verificare sostanzialmente due casi:
CASO 1 (ultimo livello non pieno)
a
b
d e
c
a
b
d e f
c
ADT albero binario completoADT albero binario completo
Strutture Dati
Relativamente all'operazione di add si possono verificare sostanzialmente due casi:
CASO 2 (ultimo livello pieno)
a
b
d e f g
c
h
a
b
d e f g
c
ADT albero binario completoADT albero binario completoInterfacciaInterfaccia
Strutture Dati
public interface CompleteBinaryTree<E> extends BinaryTree<E> {
public Position<E> add(E elem);
public E remove();}
ADT albero binario completoADT albero binario completoImplementazione con arraylistImplementazione con arraylist
Strutture Dati
Tutti i nodi dell'albero binario completo sono memorizzati in un array list A
a
b
d e f g
c
h i l m n
a b c d e f g h i l m n
la radice è memorizzata all'indice 1
per ogni nodo v memorizzato all'indice i:
- il suo figlio sinistro è memorizzato all'indice 2i - il suo figlio destro è memorizzato all'indice 2i + 1
i 2i 2i+1
l'ultimo nodo è memorizzato in A[n]
ADT albero binario completoADT albero binario completoImplementazione con arraylistImplementazione con arraylist
Strutture Dati
a
b
d e f g
c
h i l m n
a b c d e f g h i l m n
i 2i 2i+1
le operazioni di add e remove richiedono tempo O(1) viene coinvolto solo l'ultimo elemento dell'arraylist
ADT albero binario completoADT albero binario completoImplementazione con arraylistImplementazione con arraylist
Strutture Dati
a
b
d e f g
c
h i l m n
a b c d e f g h i l m n
i 2i 2i+1
le operazioni di add e remove richiedono tempo O(1) viene coinvolto solo l'ultimo elemento dell'arraylist
o
o
ADT albero binario completoADT albero binario completoImplementazione con arraylistImplementazione con arraylist
Strutture Dati
a
b
d e f g
c
h i l m n
a b c d e f g h i l m n
i 2i 2i+1
le operazioni di add e remove richiedono tempo O(1) viene coinvolto solo l'ultimo elemento dell'arraylist
o
o
in caso venga usato un arraylist estensibile, si può dimostrare che le operazioni di add e remove richiedono O(1) in tempo ammortizzato
ADT albero binario completoADT albero binario completoImplementazione con arraylistImplementazione con arraylist
Strutture Dati
public class ArrayListCompleteBinaryTree<E> implements CompleteBinaryTree<E> { protected IndexList<BTPos<E>> T; // indexed list of tree positions
protected static class BTPos<E> implements Position<E> {E element; int index; // indice di questa posizione nell'array list
public BTPos(E elt, int i) { element = elt; index = i; } public E element() { return element; } public int index() { return index; } public E setElement(E elt) {
E temp = element; element = elt; return temp; }
public String toString() { return("[" + element + "," + index + "]"); } }...
ADT albero binario completoADT albero binario completoImplementazione con arraylistImplementazione con arraylist
Strutture Dati
public ArrayListCompleteBinaryTree() { T = new ArrayIndexList<BTPos<E>>();T.add(0, null); // the location at rank 0 is deliberately empty
}/** Returns the number of (internal and external) nodes. */public int size() { return T.size() - 1; } /** Returns whether the tree is empty. */ public boolean isEmpty() { return (size() == 0); }
/** Returns whether v is an internal node. */public boolean isInternal(Position<E> v) throws InvalidPositionException {
return hasLeft(v); // if v has a right child it will have a left child}/** Returns whether v is an external node. */public boolean isExternal(Position<E> v) throws InvalidPositionException {
return !isInternal(v);}/** Returns whether v is the root node. */public boolean isRoot(Position<E> v) throws InvalidPositionException {
BTPos<E> vv = checkPosition(v);return vv.index() == 1;
}...
ADT albero binario completoADT albero binario completoImplementazione con arraylistImplementazione con arraylist
Strutture Dati
public boolean hasLeft(Position<E> v) throws InvalidPositionException { BTPos<E> vv = checkPosition(v);return 2*vv.index() <= size();
}/** Returns whether v has a right child. */public boolean hasRight(Position<E> v) throws InvalidPositionException {
BTPos<E> vv = checkPosition(v);return 2*vv.index() + 1 <= size();
}/** Returns the root of the tree. */public Position<E> root() throws EmptyTreeException {
if (isEmpty()) throw new EmptyTreeException("Tree is empty");return T.get(1);
} /** Returns the left child of v. */public Position<E> left(Position<E> v) throws InvalidPositionException, BoundaryViolationException {
if (!hasLeft(v)) throw new BoundaryViolationException("No left child");BTPos<E> vv = checkPosition(v);return T.get(2*vv.index());
}...
ADT albero binario completoADT albero binario completoImplementazione con arraylistImplementazione con arraylist
Strutture Dati
public Position<E> right(Position<E> v) throws InvalidPositionException {
if (!hasRight(v)) throw new BoundaryViolationException("No right child");BTPos<E> vv = checkPosition(v);return T.get(2*vv.index() + 1);
}/** Returns the parent of v. */public Position<E> parent(Position<E> v) throws InvalidPositionException, BoundaryViolationException {
if (isRoot(v)) throw new BoundaryViolationException("No parent");BTPos<E> vv = checkPosition(v);return T.get(vv.index()/2);
}/** Returns an iterable collection of the children of v. */ public Iterable<Position<E>> children(Position<E> v) throws InvalidPositionException {
PositionList<Position<E>> children = new NodePositionList<Position<E>>();if (hasLeft(v))
children.addLast(left(v));if (hasRight(v))
children.addLast(right(v));return children;
}
ADT albero binario completoADT albero binario completoImplementazione con arraylistImplementazione con arraylist
Strutture Dati
public Iterable<Position<E>> positions() {PositionList<Position<E>> positions = new NodePositionList<Position<E>>();for (int i =1; i < T.size(); i++)
positions.addLast(T.get(i));return positions;
}/** Replaces the element at v. */public E replace(Position<E> v, E o) throws InvalidPositionException {
BTPos<E> vv = checkPosition(v);return vv.setElement(o);
}/** Adds an element just after the last node (in a level numbering). */public Position<E> add(E e) {
int i = size() + 1;BTPos<E> p = new BTPos<E>(e,i);T.add(i, p);return p;
}/** Removes and returns the element at the last node. */public E remove() throws EmptyTreeException {
if(isEmpty()) throw new EmptyTreeException("Tree is empty");return T.remove(size()).element();
}...
ADT albero binario completoADT albero binario completoEserciziEsercizi
Strutture Dati
Completare l'implementazione con i restanti metodi e aggiungere il metodopublic Position<E> sibling(Position<E> v) che prende in input un nodoe restituisce il suo fratello.
HeapHeap
Strutture Dati
Un heap è un albero binario che memorizza una collezione di entrate nei suoi nodi e che soddisfa le due seguenti proprietà:
1) (proprietà di ordinamento) ogni nodo diverso dalla radice memorizza un elemento la cui chiave è maggiore o uguale di quella del suo padre;
2) (proprietà strutturale) in ogni livello dell'albero c'è il massimo numero di nodi possibile, tranne che nell'ultimo che è riempito da sinistra a destra, cioè deveessere un albero binario completo.
3
5
7 9 5 7
4
7 8 13 10 5
Tutte le foglie sono addossate a sinistra
Altezza di un heapAltezza di un heap
Strutture Dati
Qual è il massimo numero di nodi di un heap di altezza h?
h
124...2h=2h1
−1
Altezza di un heapAltezza di un heap
Strutture Dati
Qual è il minimo numero di nodi di un heap di altezza h?
h-1
124...2h−11=2h
−11=2h
Altezza di un heapAltezza di un heap
Strutture Dati
h h-1
2h≤n≤2h1
−1implies log n1−1≤h≤ log n
2h≤ n ≤ 2h1
−1
⇒ log n1−1≤ h ≤ log n
⇒ h = ⌊ log n⌋
Quindi:
Un heap con n entrate ha altezza h = ⌊log n⌋
ADT Coda a PrioritàADT Coda a PrioritàInterfacciaInterfaccia
public interface PriorityQueue<K, V> {
public int size();
public boolean isEmpty();
/** Restituisce senza rimuoverla una entry con chiave minima. */public Entry<K,V> min() throws EmptyPriorityQueueException;
/** Inserisce una coppia key-value e restituisce la entry creata. */public Entry<K,V> insert(K key, V value) throws InvalidKeyException;
/** Rimuove e restituisce una entry con chiave minima. */public Entry<K,V> removeMin() throws EmptyPriorityQueueException;
}
Strutture Dati
ADT Coda a PrioritàADT Coda a PrioritàImplementazione con heapImplementazione con heap
Strutture Dati
L'ADT coda a priorità può essere implementato efficientemente con un heap.
L'implementazione basata su heap consiste dei seguenti elementi:
● un heap, cioè un albero binario completo che memorizza nei suoi nodientrate (chiave,valore) le cui chiavi soddisfano la proprietà di ordinamento dell'heap
● un comparatore, cioè un oggetto che definisce una relazione d'ordine totale tra le chiavi
ADT Coda a PrioritàADT Coda a PrioritàImplementazione con heapImplementazione con heap
Strutture Dati
Inserimento di una nuova entrata con chiave 4
5
5 8
7 8 12 11
11 9 14
ADT Coda a PrioritàADT Coda a PrioritàImplementazione con heapImplementazione con heap
Strutture Dati
5
5 8
7 8 12 11
11 9 14
Inserimento di una nuova entrata con chiave 4
1) eseguiamo prima un'operazione di add che preserva la proprietà di albero binario completo ma non quella di ordinamento
4
ADT Coda a PrioritàADT Coda a PrioritàImplementazione con heapImplementazione con heap
Strutture Dati
5
5 8
7 4 12 11
11 9 14
Inserimento di una nuova entrata con chiave 4
1) eseguiamo prima un'operazione di add che preserva la proprietà di albero binario completo ma non quella di ordinamento2) continuiamo a scambiare l'entrata del nuovo nodo z con quella di suo padre u fino a che chiave(z) ≥ chiave(u)
8
ADT Coda a PrioritàADT Coda a PrioritàImplementazione con heapImplementazione con heap
Strutture Dati
5
4 8
7 5 12 11
11 9 14
Inserimento di una nuova entrata con chiave 4
1) eseguiamo prima un'operazione di add che preserva la proprietà di albero binario completo ma non quella di ordinamento2) continuiamo a scambiare l'entrata del nuovo nodo z con quella di suo padre u fino a che chiave(z) ≥ chiave(u)
8
ADT Coda a PrioritàADT Coda a PrioritàImplementazione con heapImplementazione con heap
Strutture Dati
4
5 8
7 5 12 11
11 9 14
Inserimento di una nuova entrata con chiave 4
1) eseguiamo prima un'operazione di add che preserva la proprietà di albero binario completo ma non quella di ordinamento2) continuiamo a scambiare l'entrata del nuovo nodo z con quella di suo padre u fino a che chiave(z) ≥ chiave(u)
8
ADT Coda a PrioritàADT Coda a PrioritàImplementazione con heapImplementazione con heap
Strutture Dati
4
5 8
7 5 12 11
11 9 14
Inserimento di una nuova entrata con chiave 4
nel caso pessimo si eseguono un numero di swap pari all'altezza dell'albero, cioè ⌊log n⌋
8
ADT Coda a PrioritàADT Coda a PrioritàImplementazione con heapImplementazione con heap
Strutture Dati
Rimozione (RemoveMin)
5
5 8
7 8 12 11
20 9 14 15
ADT Coda a PrioritàADT Coda a PrioritàImplementazione con heapImplementazione con heap
Strutture Dati
Rimozione (RemoveMin)1) copiamo l'entrata e dell'ultimo nodo nella radice
15
5 8
7 8 12 11
20 9 14 15
ADT Coda a PrioritàADT Coda a PrioritàImplementazione con heapImplementazione con heap
Strutture Dati
Rimozione (RemoveMin)1) copiamo l'entrata e dell'ultimo nodo nella radice2) cancelliamo l'ultimo nodo
15
5 8
7 8 12 11
20 9 14
ADT Coda a PrioritàADT Coda a PrioritàImplementazione con heapImplementazione con heap
Strutture Dati
15
5 8
7 8 12 11
20 9 14
Rimozione (RemoveMin)1) copiamo l'entrata e dell'ultimo nodo nella radice2) cancelliamo l'ultimo nodo3) continuiamo a scambiare l'entrata e nel nodo u con quella del figlio di u avente la più piccola chiave fino a che la proprietà di ordinamento non verrà ristabilita
ADT Coda a PrioritàADT Coda a PrioritàImplementazione con heapImplementazione con heap
Strutture Dati
5
15 8
7 8 12 11
20 9 14
Rimozione (RemoveMin)1) copiamo l'entrata e dell'ultimo nodo nella radice2) cancelliamo l'ultimo nodo3) continuiamo a scambiare l'entrata e nel nodo u con quella del figlio di u avente la più piccola chiave fino a che la proprietà di ordinamento non verrà ristabilita
ADT Coda a PrioritàADT Coda a PrioritàImplementazione con heapImplementazione con heap
Strutture Dati
5
7 8
15 8 12 11
20 9 14
Rimozione (RemoveMin)1) copiamo l'entrata e dell'ultimo nodo nella radice2) cancelliamo l'ultimo nodo3) continuiamo a scambiare l'entrata e nel nodo u con quella del figlio di u avente la più piccola chiave fino a che la proprietà di ordinamento non verrà ristabilita
ADT Coda a PrioritàADT Coda a PrioritàImplementazione con heapImplementazione con heap
Strutture Dati
Rimozione (RemoveMin)1) copiamo l'entrata e dell'ultimo nodo nella radice2) cancelliamo l'ultimo nodo3) continuiamo a scambiare l'entrata e nel nodo u con quella del figlio di u avente la più piccola chiave fino a che la proprietà di ordinamento non verrà ristabilita
5
7 8
9 8 12 11
20 15 14
ADT Coda a PrioritàADT Coda a PrioritàImplementazione con heapImplementazione con heap
Strutture Dati
5
7 8
9 8 12 11
20 15 14
Rimozione (RemoveMin)
nel caso pessimo si eseguono un numero di swap pari all'altezza dell'albero, cioè ⌊log n⌋
ADT Coda a PrioritàADT Coda a PrioritàImplementazione con heapImplementazione con heap
Strutture Dati
Operazione Complessitàsize, isEmpty O(1)
min O(1)
insert O(log n)
removeMin O(log n)