É possível ter essas características em uma estrutura de dados?

5

Eu estava ajudando um aluno que criou a esta tarefa. Basicamente, requer uma estrutura de dados com as seguintes características:

  • contém um conjunto de inteiros em {1, 2, ..., n}
  • n é poder de 2
  • O (log (n)) inserção, exclusão e máximo
  • O (1) para determinar se um elemento está no conjunto
  • usa apenas O (n) bits de armazenamento

Essa estrutura de dados existe mesmo?

    
por Shoe 28.01.2016 / 21:29
fonte

1 resposta

7

A pista para encontrar a estrutura de dados correta aqui é que os requisitos ( além dos requisitos de espaço e acessibilidade direta ) são os de uma árvore binária. Isso me fez pensar em como você poderia modificar uma árvore binária para que ela atendesse aos requisitos.

O que você pode fazer é serializar efetivamente em uma matriz uma passagem de pré-ordem de largura de uma árvore binária que armazena 1 ou 0 para a presença de cada item no conjunto, ou para nós não-folha a presença de qualquer um dos nós filhos. A inserção então requer que os bits O (log n) sejam definidos como 1, a exclusão requer que os bits O (log n) sejam copiados de um nó could, e o máximo é uma busca binária. O acesso direto ainda é possível porque os nós folha têm o mesmo formato que o vetor de bits, ignorando os primeiros (n-1) bits.

Exemplo: n = 8, com itens 2, 3, 4 e 6 definidos:

    1 11 1110 01110100
    ^ root: some values are in the set
      ^^ second level: values present in both first and second halves
         ^^^^ third level: quarters 1,2, and 3 have members, but the final quarter is empty
              ^^^^^^^^ leaves, essentially the same as the bit vector described in the question.
    
por 28.01.2016 / 22:59
fonte