Quais são as diferenças entre árvores de segmento, árvores de intervalo, árvores indexadas binárias e árvores de alcance?

200

Quais são as diferenças entre árvores de segmento, árvores de intervalo, árvores indexadas binárias e árvores de alcance em termos de:

  • Ideia / definição-chave
  • Formulários
  • Desempenho / ordem em dimensões maiores / consumo de espaço

Por favor, não dê apenas definições.

Aditya
fonte
12
Não é uma duplicata. Essa questão é se as árvores fenwick são generalização do intervalo entre árvores e minha pergunta é mais específica e diferente.
Aditya
7
Não foi respondido em stackoverflow.com/questions/2795989/… , a resposta apenas fornece uma definição.
Aditya
12
Como é amplo demais? "Quais são algumas diferenças entre x e y?" é o mais claro e focado possível. Esta é uma pergunta muito boa.
IVlad
16
E não há uma boa resposta para isso disponível em qualquer lugar. Uma boa resposta vai ser ótimo para a comunidade
Aditya
22
A maioria dessas estruturas de dados (exceto as árvores Fenwick) é revisada neste pdf: "Árvores de pesquisa por intervalo, segmento, intervalo e prioridade" (por DT Lee). Ou você pode lê-lo como um capítulo deste livro: "Manual de estruturas e aplicativos de dados" .
Evgeny Kluev 04/07/2013

Respostas:

319

Todas essas estruturas de dados são usadas para resolver problemas diferentes:

  • A árvore de segmentos armazena intervalos e otimizada para consultas sobre " qual desses intervalos contém um determinado ponto ".
  • A árvore de intervalo também armazena os intervalos, mas otimizada para " quais desses intervalos se sobrepõem a um determinado intervalo consultas ". Também pode ser usado para consultas de pontos - semelhante à árvore de segmentos.
  • A árvore de intervalos armazena pontos e é otimizada para " quais pontos se enquadram em um determinado intervalo consultas ".
  • A árvore indexada binária armazena a contagem de itens por índice e otimizada para " quantos itens existem entre as consultas do índice m e n ".

Desempenho / consumo de espaço para uma dimensão:

  • Árvore de segmentos - tempo de pré-processamento O (n logn), tempo de consulta O (k + logn), espaço O (n logn)
  • Árvore de intervalo - tempo de pré-processamento O (n logn), tempo de consulta O (k + logn), espaço O (n)
  • Árvore de intervalo - tempo de pré-processamento O (n logn), tempo de consulta O (k + logn), espaço O (n)
  • Árvore indexada binária - tempo de pré-processamento O (n logn), tempo de consulta O (logn), espaço O (n)

(k é o número de resultados relatados).

Todas as estruturas de dados podem ser dinâmicas, no sentido de que o cenário de uso inclui alterações e consultas de dados:

  • Árvore de segmentos - o intervalo pode ser adicionado / excluído no tempo O (logn) (veja aqui )
  • Árvore de intervalo - o intervalo pode ser adicionado / excluído no tempo O (logn)
  • Árvore de alcance - novos pontos podem ser adicionados / excluídos no tempo O (logn) (veja aqui )
  • Árvore indexada binária - a contagem de itens por índice pode ser aumentada no tempo O (logn)

Dimensões mais altas (d> 1):

  • Árvore de segmentos - O (n (logn) ^ d) tempo de pré-processamento, O (k + (logn) ^ d) tempo de consulta, O (n (logn) ^ (d-1)) espaço
  • Árvore de intervalo - tempo de pré-processamento O (n logn), tempo O (k + (logn) ^ d) de consulta, espaço O (n logn)
  • Árvore de intervalo - O (n (logn) ^ d) tempo de pré-processamento, O (k + (logn) ^ d) tempo de consulta, O (n (logn) ^ (d-1))) espaço
  • Árvore indexada binária - O (n (logn) ^ d) tempo de pré-processamento, O ((logn) ^ d) tempo de consulta, O (n (logn) ^ d) espaço
Lior Kogan
fonte
12
Eu realmente tenho a impressão de que segmenta árvores <árvores de intervalo disso. Existe algum motivo para preferir uma árvore de segmentos? Por exemplo, simplicidade de implementação?
Jrandom_hacker
7
@j_random_hacker: os algoritmos baseados em árvores de segmentos têm vantagens em algumas variantes de alta dimensão mais complexas da consulta de intervalos. Por exemplo, localizando quais segmentos de linha paralelos que não são eixo interceptam uma janela 2D.
Lior Kogan
5
Obrigado, eu estaria interessado em qualquer elaboração que você pudesse dar sobre isso.
Jrandom_hacker
3
@j_random_hacker, as árvores de segmentos têm outro uso interessante: RMQs (intervalo de consultas mínimas) no tempo O (log N) em que N é o tamanho geral do intervalo.
ars-longa-vita-brevis
1
Por que as árvores de segmentos são espaço O (n log n)? Eles armazenam N folhas + N / 2 + N / 4 + ... + N / 2 ^ (log N), e essa soma é O (N) se não me engano. Também a resposta @ icc97 também informa o espaço O (N).
Ant
24

Não que eu possa acrescentar algo à resposta de Lior , mas parece que isso poderia ter uma boa mesa.

Uma dimensão

k é o número de resultados relatados

|              | Segment       | Interval   | Range          | Indexed   |
|--------------|--------------:|-----------:|---------------:|----------:|
|Preprocessing |        n logn |     n logn |         n logn |    n logn |
|Query         |        k+logn |     k+logn |         k+logn |      logn |
|Space         |        n logn |          n |              n |         n |
|              |               |            |                |           |
|Insert/Delete |          logn |       logn |           logn |      logn |

Dimensões superiores

d > 1

|              | Segment       | Interval   | Range          | Indexed   |
|--------------|--------------:|-----------:|---------------:|----------:|
|Preprocessing |     n(logn)^d |     n logn |      n(logn)^d | n(logn)^d |
|Query         |    k+(logn)^d | k+(logn)^d |     k+(logn)^d |  (logn)^d |
|Space         | n(logn)^(d-1) |     n logn | n(logn)^(d-1)) | n(logn)^d |

Essas tabelas são criadas no Markdown formatado no Github - veja este Gist se você deseja que as tabelas sejam formatadas corretamente.

icc97
fonte
2
O que você quer dizer com resultados relatados?
Pratik Singhal
Os algoritmos de pesquisa @ ps06756 geralmente têm um tempo de execução de log (n) em que n é o tamanho da entrada, mas pode produzir resultados lineares em n que não podem ser feitos em tempo logarítmico (não é possível gerar n números no tempo de log (n)) .
oerpli
1
A árvore de segmentos não deveria ter O(n logn) spacena primeira tabela?
21418 Danny_ds