Alberi binari di ricerca

Definizione (albero binario di ricerca). Un albero binario di ricerca (ABR, binary search tree) implementa una mappa ordinata (vedi Mappe e dizionariADT mappa (chiavi distinte) con get, put, remove, keySet/values/entrySet; famiglia mappa/mappa ordinata/dizionario (multimappa); applicazioni; implementazioni semplici ma poco efficienti (lista, array indicizzato dalle chiavi); dizionario realizzato con una mappa di liste.Mappe e dizionari →) su chiavi di un universo ordinato (Campi ordinati (Q e R)Gli assiomi di somma, prodotto e ordine comuni a Q e R, da cui derivano le regole di equazioni e disequazioni.Campi ordinati (Q e R) →). È l'analogo ad albero della ricerca binaria su array (Ricerca lineare e binariaRicerca lineare su sequenze qualsiasi in O(n); ricerca binaria su sequenze ordinate in O(log n), versione iterativa e ricorsiva, invariante e errori di indice; modulo bisect.Ricerca lineare e binaria →): a ogni confronto si scarta un intero sottoalbero come là si scartava metà intervallo, con il vantaggio che inserire e togliere non richiede di spostare gli elementi. È un albero binario proprio (vedi 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 →) i cui nodi interni memorizzano entry e le cui foglie sono vuote (sentinelle esterne), tale che per ogni nodo interno $v$ con chiave $k$:

• le chiavi del sottoalbero sinistro di $v$ sono $< k$;
• le chiavi del sottoalbero destro di $v$ sono $> k$.

Esempio. Inserendo $30,40,24$ in un ABR vuoto si ha radice $30$, figlio destro $40$ e figlio sinistro $24$; l'inorder è $24,30,40$.

Conseguenza: la visita inorder (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 →) tocca le entry in ordine crescente di chiave: per ogni nodo prima tutto il sottoalbero sinistro (chiavi minori), poi il nodo, poi il destro (chiavi maggiori). L'albero con $n$ entry ha $n$ nodi interni e $n + 1$ foglie (vedi la relazione $m = n - m + 1$ in 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 →).

Ricerca

Algoritmo TreeSearch(k, v)
Input: chiave k, nodo v     Output: nodo di T_v con chiave k, o la foglia in cui k andrebbe
if T.isExternal(v) OR v.getElement().getKey() = k then return v
if k < v.getElement().getKey() then return TreeSearch(k, T.left(v))
else return TreeSearch(k, T.right(v))

Per cercare in tutto l'albero si parte da T.root(). Traccia di TreeSearch(26) sull'albero delle chiavi $30,40,24,58,48,26,11,13$ (vedi gli esempi sotto): in $30$ si ha $26<30$, si va a sinistra; in $24$ si ha $26>24$, si va a destra; in $26$ la chiave coincide e si restituisce il nodo, dopo 3 chiamate. Per TreeSearch(25) si arriverebbe alla foglia sinistra di $26$ (dopo $25<26$): è dove $25$ andrebbe inserito. La correttezza è immediata dalla definizione. Complessità (albero della ricorsione, vedi Algoritmi ricorsiviAlgoritmi ricorsivi come induzione eseguita; albero della ricorsione e record di attivazione nello stack; esempi ReverseArray, LinearSum, Power in tempo logaritmico, Fibonacci ricorsivo (esponenziale) e con memoizzazione; analisi della complessità con l'albero della ricorsione e correttezza per induzione.Algoritmi ricorsivi →): le chiamate sono sui nodi di un cammino di lunghezza $\le h$, una per nodo, ciascuna $\Theta(1)$; esistono istanze in cui il cammino arriva alla foglia più profonda: $\Theta(h)$ (intendendo $\Theta(h + 1)$ per includere $h = 0$).

Metodi della mappa

Definizione (get, put e remove su un ABR)

• get(k): $w \leftarrow$ TreeSearch(k, root); se $w$ è esterno restituisce null, altrimenti il valore di $w$. $\Theta(h)$.

• put(k, x): $w \leftarrow$ TreeSearch. Se $w$ è interno si sostituisce il valore e si restituisce il vecchio; altrimenti $w$ è una foglia e si espande: diventa nodo interno con la entry $(k, x)$ e due nuove foglie come figli; si incrementa il numero di entry e si restituisce null. $\Theta(h)$.

• remove(k): $w \leftarrow$ TreeSearch; se è esterno restituisce null. Altrimenti due casi:

  1. $w$ ha almeno un figlio foglia: si elimina $w$ e la foglia e si collega l'altro figlio $u$ al padre di $w$ (se $w$ era la radice, $u$ diventa radice);
  2. $w$ ha due figli interni: si prende $y$ = predecessore inorder di $w$ (il nodo più a destra del sottoalbero sinistro: entry con la chiave immediatamente minore) e si copia la sua entry in $w$; $y$ non ha figlio destro interno, quindi si elimina $y$ con il caso 1. L'albero resta di ricerca: la nuova chiave in $w$ è maggiore di tutte le chiavi a sinistra e minore di quelle a destra.

  Costo: $\Theta(h)$ per la ricerca, $O(h)$ per trovare il predecessore, $O(1)$ per aggiornare i nodi: $\Theta(h)$.

Esempio. In un ABR con inorder $11,13,24,30,40,48,58$, remove(30) con due figli interni sostituisce la entry con il predecessore inorder, cioè $24$.

Esempi

Inserimenti (albero inizialmente vuoto) delle chiavi $30, 40, 24, 58, 48, 26, 11, 13$: $30$ radice; $40$ a destra; $24$ a sinistra; $58$ figlio destro di $40$; $48$ figlio sinistro di $58$; $26$ figlio destro di $24$; $11$ figlio sinistro di $24$; $13$ figlio destro di $11$. Preorder $30, 24, 11, 13, 26, 40, 58, 48$, inorder $11, 13, 24, 26, 30, 40, 48, 58$, altezza $3$.

L'ordine di inserimento conta. Le stesse chiavi inserite nell'ordine $13, 11, 24, 26, 30, 40, 48, 58$ danno un albero diverso (preorder $13, 11, 24, 26, 30, 40, 48, 58$, altezza $6$, tutta la parte destra è un cammino).

Altri due casi d'esame: inserendo $7, 3, 10, 1, 5, 9, 12$ si ottiene un albero perfetto di altezza $2$, con inorder $1, 3, 5, 7, 9, 10, 12$; inserendo $5, 2, 8, 4, 7, 9, 3$ la radice è $5$, a sinistra $2$ con figlio destro $4$ che ha figlio sinistro $3$, a destra $8$ con figli $7$ e $9$ (inorder $2, 3, 4, 5, 7, 8, 9$, altezza $3$).

Contare le chiavi $\le 26$ con size. Nell'albero del primo esempio i campi size sono: $30{:}8$, $24{:}4$ (24, 11, 13, 26), $11{:}2$, $26{:}1$, $40{:}3$. contaMinoriUguali(root, 26): in $30$, $26<30$, si va a sinistra; in $24$, $26\ge24$, si somma size(sinistro $=11$)$=2$ più $1$ per $24$ stesso, e si prosegue a destra; in $26$, $26\ge26$, si somma size(sinistro $=$ foglia$)=0$ più $1$ e si prosegue a destra, su una foglia che dà $0$. Totale $2+1+0+1=4$: le chiavi $11,13,24,26$.

Rimozioni dall'albero del primo esempio: remove(26) (caso 1: $26$ ha solo foglie): inorder $11, 13, 24, 30, 40, 48, 58$; poi remove(24) ($24$ ha solo il figlio sinistro $11$: caso 1, $11$ prende il suo posto); poi remove(30) sulla radice (caso 2: predecessore $13$, che sostituisce la radice): preorder $13, 11, 40, 58, 48$.

Altezza e caso pessimo

Proprietà (altezza e costo delle operazioni su un ABR). Le tre operazioni costano $\Theta(h)$ e $h$ può arrivare a $n - 1$ (chiavi inserite in ordine crescente o decrescente: l'albero degenera in una lista), per cui al caso pessimo sono $\Theta(n)$; in un albero bilanciato $h = \Theta(\log n)$. Per ottenere $\Theta(\log n)$ garantito: alberi che si ristrutturano (AVL, rosso-neri) oppure nodi più capienti, gli alberi (2,4) (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) →).

Esempio. Inserendo $1,2,3,4,5$ in ordine crescente l'albero diventa un cammino: $h=n-1=4$ e ogni operazione costa $\Theta(n)$. Il grafico confronta l'altezza dell'albero degenere con quella minima possibile (albero completo, $\lfloor\log_2 n\rfloor$, vedi HeapAlbero binario completo e sua altezza floor(log2 n); heap = albero completo con heap-order property; proprietà (radice minima, cammini non decrescenti); rappresentazione su array con level numbering; insert con up-heap bubbling, removeMin con down-heap bubbling, rimozione di una entry qualsiasi; invarianti e costi Theta(log n); esempio svolto.Heap →): già con $n=1000$ chiavi sono $999$ contro $9$ passi di ricerca.

In media, inserendo le chiavi in ordine casuale (cioè con tutte le $n!$ permutazioni equiprobabili, vedi Calcolo combinatorio per la probabilitàNegli spazi uniformi bisogna contare: principio di moltiplicazione, disposizioni con ripetizione n^k, disposizioni semplici n!/(n−k)!, permutazioni n!, combinazioni (n su k); estrazioni con e senza reinserimento e distribuzione ipergeometrica.Calcolo combinatorio per la probabilità →) l'altezza è $\Theta(\log n)$: il caso degenere richiede un ordine particolare, ma i dati reali sono spesso già parzialmente ordinati, ed è per questo che servono alberi che si bilanciano da soli.

Alberi aumentati

Spesso gli esercizi aggiungono a ogni nodo $v$ un campo che riassume il sottoalbero $T_v$ e che si aggiorna, risalendo, a ogni inserimento o rimozione ($O(h)$ nodi coinvolti).

Contare le entry con chiave $\le k$ con v.size = numero di entry di $T_v$:

Algoritmo contaMinoriUguali(v, k)
Input: nodo v, chiave k    Output: numero di entry in T_v con chiave <= k
if T.isExternal(v) then return 0
if k < v.key then return contaMinoriUguali(T.left(v), k)
else return size(T.left(v)) + 1 + contaMinoriUguali(T.right(v), k)

(con size di una foglia uguale a $0$). Se $k < v.key$ tutto $v$ e il sottoalbero destro sono scartati; altrimenti $v$ e tutto il sottoalbero sinistro contano e si prosegue a destra. Si scende lungo un solo cammino: $\Theta(h)$.

Interrogazione con v.max (esame sui terremoti): $T$ è una mappa tempo $t \mapsto$ intensità $i_t$ e ogni nodo ha v.max = massima intensità in $T_v$. Si chiede se esiste una entry con chiave $\ge t$ e valore $\ge i$.

Algoritmo TFR(v, t, i)
Input: nodo v, tempo t, intensità i     Output: yes/no
if T.isExternal(v) OR v.max < i then return no       (nessuna entry in T_v può bastare)
if v.key >= t then
    if v.value >= i then return yes
    if TFR(T.left(v), t, i) = yes then return yes     (a sinistra ci sono chiavi < v.key, forse >= t)
return TFR(T.right(v), t, i)

Se $v.key < t$ tutto il sottoalbero sinistro ha chiavi $< t$ e si va solo a destra. Se $v.key \ge t$ tutto il sottoalbero destro ha chiavi $\ge t$, quindi per esso conta solo max.

Complessità $O(h)$. I nodi su cui l'algoritmo prosegue "a cavallo" della soglia $t$ formano un unico cammino radice-foglia. Da ciascuno di essi parte al più una seconda chiamata, sul sottoalbero interamente nell'intervallo: se il suo max è $< i$ termina subito con $no$ in $O(1)$; altrimenti esiste una entry valida, e la discesa lungo il cammino dei nodi con max $\ge i$ la trova restituendo $yes$ dopo al più $h$ passi (e a quel punto tutto finisce). In totale $O(h) + O(h) = O(h)$. Il codice è stato confrontato con la ricerca esaustiva su 500 alberi casuali.

Errori comuni

• Credere che $h = \Theta(\log n)$: vale solo se l'albero è bilanciato; il caso pessimo è $\Theta(n)$.
• Nel caso 2 della rimozione, eliminare $w$ senza sostituirlo con il predecessore (o con il successore): l'albero perde la proprietà di ricerca.
• Supporre che inserire le stesse chiavi in ordine diverso dia lo stesso albero.
• Dimenticare di aggiornare i campi aumentati (size, max) lungo il cammino dopo put e remove.