Alberi binari di ricerca

In questa pagina 6

Un albero binario di ricerca (ABR, binary search tree) implementa una mappa ordinata (vedi Mappe e dizionari) su chiavi di un universo ordinato. È un albero binario proprio (vedi 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$ .

Conseguenza: la visita inorder tocca le entry in ordine crescente di chiave. L'albero con $n$ entry ha $n$ nodi interni e $n + 1$ foglie (vedi la relazione $m = n - m + 1$ in 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(). La correttezza è immediata dalla definizione. Complessità (albero della ricorsione, vedi 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

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)$ .

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$ ).

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

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)).

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.

Versione ripasso

ABR = albero binario proprio con entry nei nodi interni (foglie vuote): sinistra $<$ chiave $<$ destra. Inorder = chiavi crescenti; $n$ entry $\Rightarrow$ $n+1$ foglie (vedi Alberi binari).
TreeSearch( $k$ , $v$ ): se $v$ esterno o chiave uguale restituisce $v$ , altrimenti scende a sinistra o a destra; $\Theta(h)$ .
get $\Theta(h)$ $Θ (h)$ ; put: foglia $\to$ $\to$ nodo interno con due nuove foglie, o sostituzione del valore; $\Theta(h)$ $Θ (h)$ ; remove:
- caso 1 (almeno una foglia figlia): il figlio interno sostituisce $w$ ;
- caso 2 (due figli interni): si copia in $w$ l'entry del predecessore inorder (massimo del sottoalbero sinistro) e si elimina quel nodo col caso 1; $\Theta(h)$ .
Altezza: $h \le n-1$ (inserimenti ordinati ⇒ lista), $\Theta(n)$ nel caso pessimo; bilanciato $\Theta(\log n)$ (AVL, rosso-neri, (2,4): vedi Multi-way search tree e alberi (2,4)). L'ordine di inserimento cambia l'albero.
Esempi: $30, 40, 24, 58, 48, 26, 11, 13$ ⇒ inorder $11, 13, 24, 26, 30, 40, 48, 58$ , $h = 3$ ; $7,3,10,1,5,9,12$ ⇒ perfetto, $h = 2$ ; $5,2,8,4,7,9,3$ ⇒ inorder $2,3,4,5,7,8,9$ , $h = 3$ .
Aumentati (campi aggiornati risalendo): size ⇒ conteggio chiavi $\le k$ lungo un solo cammino, $\Theta(h)$ ; max ⇒ TFR: se $v.max < i$ scarta il sottoalbero; $O(h)$ .
Pseudocodice: TreeSearch(k, v): se $v$ è esterno o v.key = k restituisce $v$ ; se k < v.key ricorre su left(v), altrimenti su right(v). get(k): $w \leftarrow$ TreeSearch(k, root); se $w$ esterno restituisce null, altrimenti il valore.
put: $w$ esterno ⇒ diventa nodo interno con la entry e due nuove foglie (expandExternal), size++, restituisce null; $w$ interno ⇒ sostituisce il valore e restituisce il vecchio.
remove, caso 2: $y$ = nodo più a destra del sottoalbero sinistro di $w$ (predecessore inorder, chiave immediatamente minore); si copia la sua entry in $w$ e si elimina $y$ , che non ha figlio destro interno, con il caso 1. Da $30,40,24,58,48,26,11,13$ : remove(26), remove(24), remove(30) danno preorder finale $13, 11, 40, 58, 48$ .
Fatto: $n$ entry ⇒ $n$ nodi interni e $n+1$ foglie.
Errori: $h = \Theta(\log n)$ sempre; predecessore dimenticato nel caso 2; stesso albero per ordini diversi; campi non aggiornati.