Ho trovato this answer da @templatetypedef molto chiaramente spiegare circa l'intuizione e la prova di un albero binario indicizzato: La risposta ....
Intuitivamente, si può pensare di un albero binario indicizzato come rappresentazione compressa di un albero binario che è di per sé un'ottimizzazione di una rappresentazione di array standard. Questa risposta va in una possibile derivazione.
Supponiamo, ad esempio, di voler memorizzare le frequenze cumulative per un totale di 7 elementi diversi. Si potrebbe iniziare scrivendo fuori sette secchi in cui verranno distribuiti i numeri:
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
1 2 3 4 5 6 7
Ora, supponiamo che le frequenze cumulative aspetto qualcosa di simile:
[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105]
1 2 3 4 5 6 7
Usando questa versione della matrice , è possibile incrementare la frequenza cumulativa di qualsiasi elemento aumentando il valore del numero memorizzato in quel punto, quindi incrementando le frequenze di tutto ciò che viene dopo. Ad esempio, per aumentare la frequenza cumulativa di 3 da 7, potremmo aggiungere 7 a ciascun elemento della matrice in corrispondenza o dopo la posizione 3, come illustrato di seguito:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
1 2 3 4 5 6 7
Il problema è che ci vuole O (n) tempo per fare ciò, che è piuttosto lento se n è grande.
Un modo in cui possiamo pensare a migliorare questa operazione sarebbe quello di cambiare ciò che immagazziniamo nei contenitori. Anziché archiviare la frequenza cumulativa fino al punto specificato, è possibile invece pensare semplicemente a memorizzare la quantità di incremento della frequenza corrente rispetto al bucket precedente. Per esempio, nel nostro caso, ci sarebbe riscrivere i secchi di cui sopra come segue:
Ora, siamo in grado di incrementare la frequenza all'interno di un secchio in tempo O (1) semplicemente aggiungendo la quantità appropriata per quel secchio. Tuttavia, il costo totale di una ricerca ora diventa O (n), poiché dobbiamo ricalcolare il totale nel bucket sommando i valori in tutti i bucket più piccoli.
La prima informazione importante che dobbiamo ottenere da qui a un albero binario indicizzato è la seguente: piuttosto che ricalcolare continuamente la somma degli elementi dell'array che precedono un particolare elemento, e se dovessimo precompilare la somma totale di tutti gli elementi prima di punti specifici nella sequenza? Se potessimo farlo, allora potremmo calcolare la somma cumulativa in un punto semplicemente riassumendo la giusta combinazione di queste somme precalcolate.
Un modo per fare ciò è cambiare la rappresentazione da una serie di bucket a un albero binario di nodi. Ogni nodo sarà annotato con un valore che rappresenta la somma cumulativa di tutti i nodi a sinistra di quel dato nodo.Ad esempio, supponiamo si costruisce il seguente albero binario da questi nodi:
4
/ \
2 6
/\ /\
1 3 5 7
Ora, possiamo aumentare ogni nodo memorizzando la somma cumulativa di tutti i valori compresi quel nodo e il suo sottoalbero sinistro. Ad esempio, dato i nostri valori, avremmo immagazzinare le seguenti:
Before:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
1 2 3 4 5 6 7
After:
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
1 3 5 7
[ +5] [+15] [+52] [ +0]
Data questa struttura ad albero, è facile determinare la somma cumulativa fino a un certo punto. L'idea è la seguente: manteniamo un contatore, inizialmente 0, quindi eseguiamo una normale ricerca binaria fino a trovare il nodo in questione. Mentre lo facciamo, abbiamo anche il seguente: ogni volta che ci muoviamo a destra, aggiungiamo anche il valore corrente al contatore.
Per esempio, supponiamo di voler guardare la somma per 3. Per fare ciò, facciamo la seguente:
- Inizia alla radice (4). Il contatore è 0.
- Vai a sinistra sul nodo (2). Il contatore è 0.
- Andare a destra al nodo (3). Il contatore è 0 + 6 = 6.
- Trova nodo (3). Il contatore è 6 + 15 = 21.
Si potrebbe anche immaginare di eseguire questo processo al contrario: partendo da un dato nodo, inizializzare il contatore sul valore di quel nodo, quindi risalire l'albero alla radice. Ogni volta che segui un collegamento figlio destro verso l'alto, aggiungi il valore nel nodo in cui arrivi. Ad esempio, per trovare la frequenza per 3, potremmo fare quanto segue:
- Inizia dal nodo (3). Il contatore è 15.
- Vai al nodo (2). Il contatore è 15 + 6 = 21.
- Vai al nodo (1). Il contatore è 21.
Per aumentare la frequenza di un nodo (e, implicitamente, le frequenze di tutti i nodi che seguono dopo di esso), è necessario aggiornare l'insieme di nodi nell'albero che include quel nodo nella sua sottostruttura di sinistra. Per fare ciò, facciamo quanto segue: incrementa la frequenza per quel nodo, quindi inizia a camminare fino alla radice dell'albero. Ogni volta che segui un collegamento che ti porta su come figlio sinistro, incrementa la frequenza del nodo che incontri aggiungendo il valore corrente.
Ad esempio, per incrementare la frequenza di nodo 1 per cinque, vorremmo effettuare le seguenti operazioni:
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
> 1 3 5 7
[ +5] [+15] [+52] [ +0]
A partire da nodo 1, incrementare la sua frequenza per 5 per ottenere
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
> 1 3 5 7
[+10] [+15] [+52] [ +0]
Ora , andare al suo genitore:
4
[+32]
/ \
> 2 6
[ +6] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
abbiamo seguito un link figlio sinistro verso l'alto, quindi incrementiamo fr di questo nodo equency così:
4
[+32]
/ \
> 2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
Andiamo ora al suo genitore:
> 4
[+32]
/ \
2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
Quello era un collegamento figlio sinistro, in modo da incrementare questo nodo così:
4
[+37]
/ \
2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
E adesso fatto!
Il passaggio finale consiste nel convertire da questo in un albero indicizzato binario, ed è qui che possiamo fare alcune cose divertenti con numeri binari. Riscriviamo ogni indice del bucket in questo albero in binario:
100
[+37]
/ \
010 110
[+11] [+80]
/ \ / \
001 011 101 111
[+10] [+15] [+52] [ +0]
Qui, possiamo fare un'osservazione molto, molto interessante. Prendi uno qualsiasi di questi numeri binari e trova l'ultimo 1 che è stato impostato nel numero, quindi rilascia quel bit, insieme a tutti i bit che verranno dopo di esso. Si è ora a sinistra con il seguente:
(empty)
[+37]
/ \
0 1
[+11] [+80]
/ \ / \
00 01 10 11
[+10] [+15] [+52] [ +0]
Ecco un'osservazione molto, molto cool: se si trattano 0 per "sinistra" e da 1 a significare "destra", i restanti bit su ogni numero precisare esattamente come iniziare alla radice e poi scendere a quel numero. Ad esempio, il nodo 5 ha un modello binario 101. L'ultimo 1 è il bit finale, quindi lo rilasciamo per ottenere 10. In effetti, se inizi dalla radice, vai a destra (1), quindi vai a sinistra (0), finisci fino al nodo 5!
Il motivo per cui questo è significativo è che le nostre operazioni di ricerca e aggiornamento dipendono dal percorso di accesso dal nodo di backup alla radice e se stiamo seguendo i collegamenti figlio sinistro o destro. Ad esempio, durante una ricerca, ci preoccupiamo solo dei link a sinistra che seguiamo. Durante un aggiornamento, ci preoccupiamo solo dei collegamenti giusti che seguiamo. Questo albero binario indicizzato fa tutto questo in modo super efficiente usando solo i bit nell'indice.
Il trucco chiave è la seguente proprietà di questo albero binario perfetto:
dato nodo n, il nodo successivo sul percorso di accesso posteriore fino alla radice in cui andare a destra è data dalla prendendo il binario rappresentazione di n e rimozione dell'ultimo 1.
Ad esempio, dare un'occhiata al percorso di accesso per il nodo 7, che è 111.I nodi sul percorso di accesso alla radice che prendiamo che comportano seguendo un puntatore destra è alto
- nodo 7: 111
- Nodo 6: 110
- Nodo 4: 100
Tutti questi sono collegamenti giusti. Se prendiamo il percorso di accesso per il nodo 3, che è 011, e guardiamo i nodi in cui si va a destra, otteniamo
- Nodo 3: 011
- Nodo 2: 010
- (Nodo 4 : 100, che segue un link sinistro)
Questo significa che possiamo molto, calcolare molto efficiente la somma cumulativa fino ad un nodo come segue:
- Scrive il nodo n in binario.
- Impostare il contatore a 0.
- Ripetere la seguente mentre n ≠ 0:
- Aggiungere nel valore al nodo n.
- Rimuovere il 1 bit più a sinistra da n.
Allo stesso modo, pensiamo a come avremmo fatto un passo aggiornamento. Per fare ciò, vorremmo seguire il percorso di accesso alla radice, aggiornando tutti i nodi in cui abbiamo seguito un link a sinistra verso l'alto. Possiamo fare questo essenzialmente facendo l'algoritmo sopra, ma cambiando tutti gli 1 su 0 e 0 su 1.
Il passaggio finale nell'albero indicizzato binario è notare che a causa di questo inganno bit per bit, non è nemmeno necessario che l'albero sia memorizzato in modo esplicito. Possiamo semplicemente archiviare tutti i nodi in una matrice di lunghezza n, quindi utilizzare le tecniche di manipolazione bit per bit per navigare implicitamente nell'albero. In effetti, questo è esattamente ciò che fa l'albero indicizzato bit a bit: memorizza i nodi in un array, quindi utilizza questi trucchi bit a bit per simulare in modo efficiente la risalita verso l'alto in questo albero.
Spero che questo aiuti!
Wikipedia fornisce una spiegazione piuttosto succinta: http://en.wikipedia.org/wiki/Fenwick_tree – tjameson
non dice nulla circa l'algoritmo effettivamente utilizzato e nulla della correttezza dell'algoritmo. –
Non è meno corto. Aiuta a comprendere l'essenza dell'algoritmo. L'ho pubblicato per altri potenziali rispondenti. – tjameson