Hoy escuché una conferencia sobre fenwick trees (árboles binarios indexados) y la maestra dice que este árbol es una generalización de árboles de intervalo y segmento, pero mis implementaciones de estas tres estructuras de datos son diferentes. ¿Es verdadera esta afirmación? ¿y por qué?¿El intervalo, el segmento, los árboles fenwick son iguales?
Nunca he escuchado binary indexed trees llamado generalización de algo. Ciertamente no es una generalización de interval trees y segment trees. Te sugiero que sigas los enlaces para convencerte de esto.
que este árbol es una generalización de intervalos y segmentos árboles
Si por "este árbol" tu maestro significaba "el árbol indexado binaria", entonces él está equivocado.
pero mis implementaciones de estos tres estructuras de datos son diferentes
Por supuesto que son diferentes, su profesor nunca dijo que no debe ser. Él acaba de decir que una es una generalización de la otra (lo cual no es cierto, pero aún así). De cualquier manera, se supone que las implementaciones son diferentes.
Lo que tendría la misma aplicación es un árbol binario de indexado y un árbol de Fenwick, porque los son lo mismo.
vi el artículo del topcoder y muchas consultas en BIT son similares a los árboles de intervalos. – Luiguis
Pueden ser similares, pero eso no significa que pueda decir que una estructura de datos se deriva de otra. Un nodo en el árbol de intervalos contiene la mitad del intervalo que posee su nodo primario, mientras que un nodo en un BIT contiene un intervalo dado por la representación binaria de un número. – IVlad
La siguiente clasificación parece sensata, aunque diferentes personas mezclarán estos términos.
Fenwick árbol/árbol binario indexadoslink
En el que se utiliza una sola matriz y las operaciones en la representación binaria para almacenar sumas de prefijo (también llamados sumas acumuladas). Los elementos pueden ser miembros de un monoide.
árbol Rangolink
La familia de árboles, donde cada nodo representa un subrango de un rango determinado, por ejemplo [0, N]. Se usa para calcular operaciones asociativas en intervalos.
árbol de intervalolink
árboles en donde almacena los intervalos reales. Lo más común es tomar un punto medio, mantener los intervalos de intersección en el nodo y repetir el proceso para los intervalos a la izquierda y a la derecha del punto.
árbol Segmentolink
similar a un árbol rango donde las hojas son intervalos elementales en un espacio, posiblemente, continua en lugar de nodos discretos y más altas son las uniones de los intervalos elementales. Usado para verificar la inclusión de puntos.
Hay una diferencia entre afirmar que "A es una generalización de B" y "A es lo mismo que B". –