Oggi ho ascoltato una conferenza sugli alberi di fenwick (alberi binari indicizzati) e l'insegnante dice che questo albero è una generalizzazione di alberi di intervalli e segmenti, ma le mie implementazioni di queste tre strutture di dati sono diverse. Questa affermazione è vera? e perché?Gli intervalli, i segmenti, gli alberi fenwick sono gli stessi?
Non ho mai sentito binary indexed trees chiamato una generalizzazione di nulla. Non è certamente una generalizzazione di interval trees e segment trees. Ti suggerisco di seguire i link per convincerti di questo.
di questo albero è una generalizzazione di intervallo e segmenti alberi
Se per "questo albero" tuo insegnante significava "l'albero indicizzato binario", allora si sbaglia.
ma i miei implementazioni di questa tre strutture di dati sono diversi
Naturalmente sono diversi, il vostro insegnante non ha mai detto che non dovrebbero essere. Ha appena detto che uno è una generalizzazione dell'altro (che non è vero, ma comunque). In ogni caso, le implementazioni dovrebbero essere diverse.
Cosa avrebbe lo stesso implementazione è un albero binario indicizzato e un albero Fenwick, perché quelli sono la stessa cosa.
ho visto l'articolo del topcoder e molti querys in BIT sono simili agli alberi intervallati. – Luiguis
Possono essere simili, ma ciò non significa che si possa dire che una struttura dati deriva da un'altra. Un nodo nell'albero ad intervalli contiene una metà dell'intervallo del nodo genitore, mentre un nodo in un BIT contiene un intervallo dato dalla rappresentazione binaria di un numero. – IVlad
La seguente classificazione sembra ragionevole anche se persone diverse sono destinate a mescolare questi termini.
Fenwick albero/albero binario-indicizzatolink
Quella in cui si utilizza un singolo array e operazioni sulla rappresentazione binaria per memorizzare somme prefisso (chiamati anche somme cumulative). Gli elementi possono essere membri di un monoide.
albero Catenalink
La famiglia di alberi dove ogni nodo rappresenta un sottoinsieme di un dato intervallo, dire [0, N]. Utilizzato per calcolare le operazioni associative su intervalli.
Interval alberolink
alberi dove si memorizzano intervalli effettivi. Più comunemente si prende un punto medio, si mantengono gli intervalli di intersezione sul nodo e si ripete il processo per gli intervalli a sinistra ea destra del punto.
albero Segmentolink
Simile a un albero intervallo in cui foglie sono intervalli elementari in uno spazio continuo, eventualmente, piuttosto che i nodi discreti e più alti sono i sindacati degli intervalli elementari. Utilizzato per verificare l'inclusione dei punti.
C'è una differenza tra affermare che "A è una generalizzazione di B" e "A è uguale a B." –