Esercizio 16alberi binari di ricerca, inserimenti e visita inorder

Richiami

Inserimento (vedi Alberi binari di ricercaAlbero binario di ricerca come albero binario proprio con entry nei nodi interni e foglie vuote; inorder crescente; TreeSearch; get, put e remove (due casi, con predecessore inorder) in Theta(h); altezza fino a n-1; esempi di inserimenti; alberi aumentati con campi size e max e algoritmi di conteggio e interrogazione in O(h).Alberi binari di ricerca →): si parte dalla radice; si va a sinistra se la chiave è minore di quella del nodo, a destra se è maggiore, fino a trovare un posto vuoto (una foglia esterna), dove si crea il nodo. La visita in-order visita sinistra, nodo, destra e restituisce le chiavi in ordine crescente (Alberi binariAlbero binario e albero binario proprio; interfaccia; relazioni tra nodi, foglie e altezza (m = n-m+1, h+1 <= m <= 2^h, 2h+1 <= n <= 2^(h+1)-1) con dimostrazioni; visita inorder; parse tree e valutazione di espressioni; heightSum come esempio di calcolo di un'informazione più ricca.Alberi binari →, Visite di alberiVisite in preorder e postorder come schemi generali (template) da adattare; complessità Theta(n + somma dei costi di visita) perché la somma dei figli è n-1; esempi (indice di un libro, spazio occupato in un file system); profondità con il preorder, altezza con il postorder; antenato comune più basso.Visite di alberi →). Il numero di confronti per cercare una chiave è la profondità del suo nodo più uno: ad esempio, nell'albero del punto 1, cercare $9$ costa i confronti con $7$, $10$ e $9$, cioè $3$.

1. Chiavi $7, 3, 10, 1, 5, 9, 12$

• $7$: radice.
• $3 < 7$: figlio sinistro di $7$.
• $10 > 7$: figlio destro di $7$.
• $1 < 7$, $1 < 3$: figlio sinistro di $3$.
• $5 < 7$, $5 > 3$: figlio destro di $3$.
• $9 > 7$, $9 < 10$: figlio sinistro di $10$.
• $12 > 7$, $12 > 10$: figlio destro di $10$.

          7
        /   \
       3     10
      / \    / \
     1   5  9   12

(b) In-order: $1, 3, 5, 7, 9, 10, 12$ (ordine crescente, come sempre). L'albero è perfetto (tutti i livelli pieni): altezza $2$ con $7 = 2^3 - 1$ nodi.

2. Chiavi $5, 2, 8, 4, 7, 9, 3$

• $5$: radice.
• $2 < 5$: figlio sinistro di $5$.
• $8 > 5$: figlio destro di $5$.
• $4 < 5$, $4 > 2$: figlio destro di $2$.
• $7 > 5$, $7 < 8$: figlio sinistro di $8$.
• $9 > 5$, $9 > 8$: figlio destro di $8$.
• $3 < 5$, $3 > 2$, $3 < 4$: figlio sinistro di $4$.

        5
      /   \
     2     8
      \   / \
       4 7   9
      /
     3

(b) In-order: $2, 3, 4, 5, 7, 8, 9$. L'altezza è $3$ (cammino $5, 2, 4, 3$). Come si ottiene a mano: per il nodo $5$ prima tutto il sottoalbero sinistro (nodo $2$: nessun figlio sinistro, quindi $2$, poi il suo sottoalbero destro: nodo $4$ che ha il figlio sinistro $3$, quindi $3, 4$), poi $5$, poi il sottoalbero destro (nodo $8$: prima $7$, poi $8$, poi $9$).

(c) Complessità al caso pessimo della ricerca. La ricerca segue un unico cammino dalla radice, con un numero costante di operazioni per nodo: costa $\Theta(h)$, con $h$ altezza dell'albero. Nel caso pessimo l'albero degenera in una catena (ad esempio le chiavi inserite in ordine crescente) e $h = n - 1$: la ricerca costa $\Theta(n)$, quindi $O(n)$ e $\Omega(n)$ per quell'istanza (con $n=1000$ chiavi inserite in ordine, cercare l'ultima richiede $1000$ confronti, contro i circa $10$ di un albero bilanciato, $\lfloor\log_2 1000\rfloor+1$; Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →). In un albero bilanciato sarebbe $\Theta(\log n)$ (vedi Multi-way search tree e alberi (2,4)Multi-way search tree (nodi con più entry, d figli e d-1 chiavi ordinate), ricerca in O(d_max h), un MWS tree con n entry ha n+1 foglie; albero (2,4): nodi con 2-4 figli e tutte le foglie alla stessa profondità, altezza Theta(log n) con dimostrazione, operazioni in Theta(log n); idea di overflow e underflow; tabella di confronto con gli alberi binari di ricerca.Multi-way search tree e alberi (2,4) → per strutture con altezza logaritmica garantita).

Osservazione

Lo stesso insieme di chiavi dà alberi diversi a seconda dell'ordine di inserimento: le chiavi del punto 1 inserite come $1, 3, 5, 7, 9, 10, 12$ danno una catena di altezza $6$ invece di $2$. Ciò che non cambia è la visita in-order, sempre crescente. (Alberi e visite verificati con un'implementazione.)

Errori comuni

• Dimenticare che l'albero dipende dall'ordine di inserimento: ridisegnare l'albero a partire dalle chiavi ordinate è sbagliato.
• Confondere in-order con preorder: il preorder del punto 1 è $7, 3, 1, 5, 10, 9, 12$.
• Dire che la ricerca è sempre $O(\log n)$: lo è solo se l'albero è bilanciato.
• Confrontare con il figlio sbagliato dopo aver sceso un livello (si confronta sempre con il nodo corrente, non con la radice).