Algoritmi e strutture dati - Appunti 2022/2023

Definizione di albero con radice ordinato

Un albero con radice ordinato è un albero con radice in cui ogni classe di equivalenza (rispetto alla relazione "essere fratello di") è totalmente ordinata.

Definizione di albero binario

Un albero binario è un albero con radice ordinato in cui:

• I nodi possono avere al massimo 2 figli
• I figli di un nodo sono distinti come figlio sinistro e figlio destro

Definizioni

• Pieno: Un albero binario si dice pieno se tutti i livelli sono saturi tranne eventualmente l'ultimo
• Completo: Un albero binario si dice completo se è pieno e i nodi sull'ultimo livello sono tutti disposti il più a sinistra possibile

Proprietà Matematiche

FATTO: Un albero binario completo di altezza h ha un numero di nodi che soddisfa la relazione h+1 ≤ n ≤ 2^h - 1. Di conseguenza, l'altezza di un albero binario completo con n nodi soddisfa la relazione h ~ log n.

1. Un albero binario si dice degenere se ha nodi e altezza n-1 ⇒ n
2. DEFINIZIONE Un albero binario localmente completo è un albero in cui ogni nodo ha 0 o 2 figli
3. Teorema n(n + 1) Un albero binario localmente completo con n nodi interni ha n + 1 foglie
4. Dimostrazione per induzione
   • Caso Base: 0 nodi interni, 1 foglia (la radice)
   • Induzione: tolta la radice rimangono k nodi interni, nel sottoalbero sinistro e n - k nodi interni nel sottoalbero destro. Per il numero totale di foglie è ((k - 1) + 1) + ((n - k) + 1) = n - 1
5. Teorema n LC = LC + 2n In un albero binario localmente completo con n nodi interni vale la relazione
6. Dimostrazione Ogni albero si può ottenere partendo da un albero formato dalla sola radice e iterando un processo che seleziona una foglia e la trasforma in nodo interno. Inizialmente si ha LC = 0, k = 0. LC := LC + k. Quando si trasforma una foglia

di livello si ha mentree i i iLC := LC − k + 2(k + 1) = LC + k + 2 n LC = LC + 2n. Dopo passi si hae e e e i12- Visita di GrafiPROBLEMA [ Attraversamento in Ampiezza ]⟨V, ⟩G = E s ∈ VInput : ( non orientato e connesso ) e sOutput : una sequenza che contiene tutti i nodi del grafo, ordinati rispetto alla distanza dapublic void Ampiezza(s){Queue<Nodo> q=new Queue<Nodo>();List<Lato> u=new List<Lato>();q.enqueue(s);nuovo[s]=0;for (v in V) if (v!=s) nuovo[v]=1;while (!q.isEmpty()){v = q.front();q.dequeue();v.visita();for (w in Lista di adiacenza di v)if (nuovo[w]){nuovo[w]=0;q.enqueue(w);u.Insert({v,w},1);}}} fi 10 di 3213- Visita di AlberiDEFINIZIONE ALTERNATIVA⟨r⟩• ( la radice è una foglia ) è un albero con radice ordinato ⟨ ⟩T , T , . . . , T r r, T , T , . . . , TSe sono alberi con radice ordinati e è un nodo allora è un• 1 2 m 1 2 malbero con radice ordinatoMetodi di attraversamento:•

Preorder• Postorder ⇒• Levelorder Attraversamento in Ampiezza• Solo per gli alberi binari c’è anche il metodo Inorder
Complessità: TPer ogni strategia di visita a un albero vale che:
• Ogni nodo di è parametro attuale di una e una sola chiamata ricorsivi
• Ogni nodo di viene visitato una e una sola volta
T O(1) O(1)
• Per ogni nodo di visitato si e ettuano operazioni di costo
Di conseguenza: Θ(n)
Tempo di calcolo : O(n) n
Complessità in spazio : ( Lo stack per supportare la ricorsione al massimo contiene
O(1)record di attivazione ciascuno dei quali occupa spazio )
14- Visita Iterativa di Alberi

PreOrder Iterativo

private void preOrdIt(Node r) {
    Stack<Node> s = new Stack<Node>();
    if (r!=NULL) s.push(r);
    while (!s.is_empty()) {
        r=s.top();
        s.pop();
        r.visit();
        if (r.dx != null) s.push(r.dx);
        if (r.sx != null) s.push(r.sx);
    }
}


InOrder Iterativo

private void inOrderIt(Node r){
    Stack<Node> s = new Stack<Node>();
    if (r!=NULL) s.push(r);
    while (!s.is_empty()) {
        while (r!=NULL) {
            s.push(r);
            r = r.sx;
        }
        r = s.top();
        s.pop();
        r.visit();
        r = r.dx;
    }
}

(r!=NULL) s.push(r);
while(!s.isEmpty()){
    r=s.top();
    s.pop();
    while(r!=null) {
        s.push(r);
        r=r.sx;
    }
    if (!s.is_Empty()){
        r=s.top();
        s.pop();
        r.visit();
        r=r.dx;
        s.push(r);
    }
}
ff 11 di 3215- Il Problema dell’ordinamento

Siano:
U• un insieme di elementi≤ ⊆ U × U U
• relazione d’ordine totaleuna su ( Ri essiva, Transitiva, Antisimmetrica )

Problema dell’ordinamento:
nX ∈ U
Input : X X [i ] ≤ X [i + 1] ∀1 ≤ i ≤ n
Output : la sequenza ordinata,

Classi ed attributi:
Identi chiamo due classi di algoritmi di ordinamento X [i ] ≤ X [ j ]
• Confronti e scambi : le operazioni eseguite sui dati sono quelle di confronto, , e
X [i ] := X [ j ]assegnamento,
• Digitali : le operazioni possono riguardare singoli ( o gruppi di ) bit della rappresentazione di
ciascun elemento

DEFINIZIONE
Un metodo di ordinamento si dice :
• STABILE : se rispetta l’ordine relativo degli elementi di ugual valore
• ADATTIVO : se i confronti e ettuati dipendono

dai dati

DEFINIZIONE [ Equivalenza per confronti ]

n ≈ ⊆ U × U X ≈ Y

Sia la relazione de nita da se e solo se

C C∀i, j X [i ] < X [ j ] ⇔ Y [i ] < Y [ j ]

X ≈ Y equivalenti per confronti

Due sequenze tali che si dicono

C⇒ ≈

FATTO è una relazione di equivalenza

CDEFINIZIONE [ Inversione ] n |X ∈ U (i, j ) i < j e X [i ] > X [ j ]

Un inversione in una sequenza è una coppian |X ∈ U N (X ) = #{(i, j ) (i, j ) e′ un inversione di X}

Il numero di inversioni di è invn(n − 1)n⇒ ∀X ∈ U 0 ≤ N (X ) ≤

FATTO inv 2N (X ) = 0 → X ordinata• inv n(n − 1)N (X ) = → X ordinata al contrario• inv 2

Limite inferiore al numero di confronti eseguiti nel caso peggiore per la classe “confronti escambi”

Lemma 1 ⌈ ⌉H(k) k H(k) ≥ log k

Sia l’altezza di un albero binario con foglie. Allora, 2

Teorema [ Lower bound per l’ordinamento

BUCKETSORT
public static void bucketsort(DEQueue<String> l){
    String w;
    DEQueue<String>[ ] s;
    s= new DEQueue<String>[NSIMB];
    for(int j=LENGTHWORD;j>0;j—){
        while(!Is_empty(l)){
            w=l.front();
            l.delete(1);
            e=Digit(w,j);
            s[e].enqueue(w);
        }
    }
    for(int i=1; i<NSIMB; i++){
        s[0].chain(s[I]);
        s[i]=null;
    }
    l=s[0];
    s[0]=null;
}