New ADT albero binario completo · 2012. 4. 11. · ADT albero binario completo Strutture Dati...

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


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


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


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]


Strutture Dati

a

b

d e f g

c

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


Strutture Dati

a

b

d e f g

c

h i l m n


i 2i 2i+1


o

o


Strutture Dati

a

b

d e f g

c

h i l m n


i 2i 2i+1


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


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 + "]"); } }...


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;

}...


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());

}...


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;

}


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


Strutture Dati

Qual è il minimo numero di nodi di un heap di altezza h?

h-1

124...2h−11=2h

−11=2h


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


Strutture Dati

Inserimento di una nuova entrata con chiave 4

5

5 8

7 8 12 11

11 9 14


Strutture Dati

5

5 8

7 8 12 11

11 9 14


1) eseguiamo prima un'operazione di add che preserva la proprietà di albero binario completo ma non quella di ordinamento

4


Strutture Dati

5

5 8

7 4 12 11

11 9 14


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


Strutture Dati

5

4 8

7 5 12 11

11 9 14



8


Strutture Dati

4

5 8

7 5 12 11

11 9 14



8


Strutture Dati

4

5 8

7 5 12 11

11 9 14


nel caso pessimo si eseguono un numero di swap pari all'altezza dell'albero, cioè ⌊log n⌋

8


Strutture Dati

Rimozione (RemoveMin)

5

5 8

7 8 12 11

20 9 14 15


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


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


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


Strutture Dati

5

15 8

7 8 12 11

20 9 14



Strutture Dati

5

7 8

15 8 12 11

20 9 14



Strutture Dati


5

7 8

9 8 12 11

20 15 14


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⌋


Strutture Dati

Operazione Complessitàsize, isEmpty O(1)

min O(1)

insert O(log n)

removeMin O(log n)

New ADT albero binario completo · 2012. 4. 11. · ADT albero binario completo Strutture Dati...

Documents

Transcript of New ADT albero binario completo · 2012. 4. 11. · ADT albero binario completo Strutture Dati...