University » Corsi precedenti » ASD » Costo Range Query

Costo della Range Query

Nel corso di Algoritmi e strutture dati si studia l’importante algoritmo della Range Query, che permette, con costo , di determinare l’insieme delle chiavi di un albero binario avente altezza che cadono in un determinato intervallo. Stanco di affermare “si dimostra che il costo è “, senza effettivamente dimostrarlo, ho deciso di presentare qui una dimostrazione.

Contiamo il numero di nodi visitati dall’algoritmo. Il costo della visita di ogni nodo è costante, quindi la complessità asintotica dell’algoritmo è pari al numero di nodi visitati.

Sia l’intervallo della range query. Classifichiamo i nodi visitati considerando dove cade la chiave rispetto all’intervallo . Se è un nodo visitato di chiave , tre casi possono verificarsi:

1. ;
2. ;
3. .

Evidentemente abbiamo nodi di tipo 2: sono i nodi dati in output dalla Range Query.

Per contare i nodi di tipo 1, osserviamo che, se ed sono due nodi di tipo 1 con allora uno di essi deve essere un antenato dell’altro. Se così non fosse, infatti, allora esisterebbe un nodo antenato di ed tale che appartiene al sottoalbero sinistro di , al sottoalbero destro di . (Tale nodo è il più basso antenato comune di e , come è facile constatare.) Poiché sia che sono raggiunti dalla visita, entrambi i sottoalberi di sono visitati, e quindi è un nodo di tipo 2. Dunque sussistono le seguenti relazioni:

• , perché è di tipo 2;
• , perché è di tipo 1 per ipotesi;

e, di conseguenza, , in contraddizione con il fatto che si trova nel sottoalbero destro di .

Dunque i nodi di tipo 1 sono, a due a due, l’uno antenato dell’altro: il che equivale a dire che tutti i nodi di tipo 1 si trovano su un medesimo percorso radice-foglia dell’albero. Essi sono al più . Simmetricamente, esistono al più nodi di tipo 3. Sommando il numero di nodi di ogni tipo, otteniamo un totale di nodi visitati, da cui la tesi.

Commenti dei visitatori

Accedi per lasciare commenti.