Qual é a diferença entre uma árvore de pesquisa binária e uma pilha binária?

Estes dois parecem muito semelhantes e têm uma estrutura quase idêntica. Qual é a diferença? Quais são as complexidades de tempo para diferentes operações de cada uma?

O heap apenas garante que os elementos em níveis mais altos sejam maiores (para max-heap) ou menores (para min-heap) do que os elementos em níveis mais baixos, enquanto o BST garante a ordem (da "esquerda" para a "direita"). Se você deseja classificar elementos, vá com o BST. por Dante não é um nerd

A pilha é melhor em findMin / findMax (O (1)), enquanto a BST é boa em todas as localizações (O (logN)). A inserção é O (logN) para ambas as estruturas. Se você se preocupa apenas com o findMin / findMax (por exemplo, relacionado à prioridade), vá com o heap. Se você quiser tudo organizado, vá com o BST.

por xysun

As árvores de pesquisa binária e as pilhas binárias são estruturas de dados baseadas em árvore.

Os montes exigem que os nós tenham prioridade sobre seus filhos. Em um heap máximo, os filhos de cada nó devem ser menores que ele próprio. É o oposto para um heap mínimo:

As árvores de pesquisa binária (BST) seguem uma ordem específica (pré-encomenda, ordem e pós-ordem) entre os nós irmãos. A árvore deve ser classificada, diferentemente das pilhas:

O BST tem média de para inserção, exclusão e pesquisa. Heaps binários possuem médio para findMin / findMax e para inserção e exclusão.$O(\log n)$O ( 1 ) O ( log n )
$O(1)$$O(\log n)$

Sumário

          Type      BST (*)   Heap
Insert    average   log(n)    1
Insert    worst     log(n)    log(n) or n (***)
Find any  worst     log(n)    n
Find max  worst     1 (**)    1
Create    worst     n log(n)  n
Delete    worst     log(n)    log(n)

Todos os tempos médios nesta tabela são iguais aos piores, exceto para Inserir.

• *: em toda parte nesta resposta, BST == BST balanceado, pois o desbalanceado é uma droga assintoticamente
• **: usando uma modificação trivial explicada nesta resposta
• ***: log(n)para heap de árvore de ponteiro, npara heap de matriz dinâmica

Vantagens da pilha binária sobre uma BST

• o tempo médio de inserção em um heap binário é O(1), para o BST, é O(log(n)). Este é o recurso matador de pilhas.

  Também existem outros montes que atingem O(1)amortizados (mais fortes) como o Fibonacci Heap e, no pior dos casos, como a fila Brodal , embora possam não ser práticos por causa do desempenho não assintótico: https://stackoverflow.com/questions/30782636 / are-fibonacci-heaps-or-brodal-filas-usadas-na-prática-em qualquer lugar

• pilhas binárias podem ser implementadas com eficiência em cima de matrizes dinâmicas ou em árvores baseadas em ponteiro, e somente em árvores baseadas em ponteiro do BST. Portanto, para o heap, podemos escolher a implementação de array com mais espaço, se pudermos permitir latências de redimensionamento ocasionais.

• a criação de heap binária é o O(n)pior caso , O(n log(n))para o BST.

Vantagem do BST sobre heap binário

• procurar por elementos arbitrários é O(log(n)). Esse é o recurso matador dos BSTs.

  Para heap, O(n)geralmente é, exceto o maior elemento que é O(1).

Vantagem "falsa" do heap sobre o BST

• heap é O(1)encontrar max, BST O(log(n)).

  Esse é um equívoco comum, porque é trivial modificar uma BST para acompanhar o maior elemento e atualizá-lo sempre que esse elemento puder ser alterado: na inserção de uma troca maior, na remoção, encontre a segunda maior. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation (mencionado por Yeo ).

  Na verdade, essa é uma limitação de pilhas comparadas às BSTs: a única pesquisa eficiente é a do maior elemento.

A inserção média de heap binário é O(1)

Fontes:

• Artigo: http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf
• Slides da WSU: http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/heaps.pdf

Argumento intuitivo:

• os níveis das árvores inferiores têm exponencialmente mais elementos do que os níveis superiores; portanto, é quase certo que novos elementos vão para o fundo
• a inserção da pilha começa na parte inferior , a BST deve começar na parte superior

Em uma pilha binária, aumentar o valor em um determinado índice também é O(1)pelo mesmo motivo. Mas se você quiser fazer isso, é provável que queira manter um índice extra atualizado nas operações de heap https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease- operação-chave-para-min-heap-com-prioridade-fila- por exemplo, para Dijkstra. Possível sem custo adicional.

Referência de inserção de biblioteca padrão da GCC C ++ em hardware real

Fiz um teste comparativo das inserções C ++ std::set( Red-black tree BST ) e std::priority_queue( dynamic array heap ) para ver se eu estava certo sobre os tempos de inserção, e foi isso que obtive:

• código de referência
• roteiro
• dados de plotagem
• testado no Ubuntu 19.04, GCC 8.3.0 em um laptop Lenovo ThinkPad P51 com CPU: CPU Intel Core i7-7820HQ (4 núcleos / 8 threads, base de 2,90 GHz, cache de 8 MB), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB , 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512 GB, 3.000 MB / s)

Tão claramente:

• o tempo de inserção da pilha é basicamente constante.

  Podemos ver claramente os pontos de redimensionamento da matriz dinâmica. Como estamos calculando a média de cada 10k inserções para poder ver qualquer coisa acima do ruído do sistema , esses picos são de fato cerca de 10k vezes maiores do que os mostrados!

  O gráfico ampliado exclui essencialmente apenas os pontos de redimensionamento da matriz e mostra que quase todas as inserções ficam abaixo de 25 nanossegundos.

• O BST é logarítmico. Todas as inserções são muito mais lentas que a inserção de pilha média.

• Análise detalhada de BST vs hashmap em: https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119

Referência de inserção de biblioteca padrão GCC C ++ na gem5

gem5 é um simulador de sistema completo e, portanto, fornece um relógio infinitamente preciso com m5 dumpstats. Então, tentei usá-lo para estimar tempos para inserções individuais.

Interpretação:

• o heap ainda é constante, mas agora vemos com mais detalhes que existem algumas linhas e cada linha superior é mais esparsa.

  Isso deve corresponder às latências de acesso à memória para inserções cada vez mais altas.

• TODO Eu realmente não consigo interpretar completamente o BST, pois ele não parece tão logarítmico e um pouco mais constante.

  Com esse detalhe maior, no entanto, podemos ver também algumas linhas distintas, mas não tenho certeza do que elas representam: eu esperaria que a linha inferior fosse mais fina, pois inserimos a parte inferior superior?

Comparado com esta configuração do Buildroot em uma CPU HPI aarch64 .

O BST não pode ser implementado com eficiência em uma matriz

As operações de heap precisam apenas subir ou descer um único galho de árvore, de modo O(log(n))que as trocas de pior caso, em O(1)média.

Manter um BST equilibrado requer rotações em árvore, o que pode alterar o elemento superior para outro e exigiria a movimentação de toda a matriz ( O(n)).

As pilhas podem ser implementadas eficientemente em uma matriz

Os índices pai e filho podem ser calculados a partir do índice atual, como mostrado aqui .

Não há operações de balanceamento como o BST.

Excluir min é a operação mais preocupante, pois precisa ser descendente. Mas isso sempre pode ser feito "percolando" um único ramo da pilha, conforme explicado aqui . Isso leva a um pior caso de O (log (n)), pois o heap é sempre bem equilibrado.

Se você estiver inserindo um único nó para cada um que remover, perderá a vantagem da inserção média assintótica O (1) fornecida pelos montões, pois a exclusão dominaria e você também pode usar uma BST. No entanto, o Dijkstra atualiza os nós várias vezes para cada remoção, por isso estamos bem.

Heaps de matriz dinâmica x heap de árvore de ponteiro

As pilhas podem ser implementadas com eficiência em cima das pilhas de ponteiros: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

A implementação do array dinâmico é mais eficiente em espaço. Suponha que cada elemento de heap contenha apenas um ponteiro para um struct:

• a implementação em árvore deve armazenar três ponteiros para cada elemento: pai, filho esquerdo e filho direito. Portanto, o uso da memória é sempre 4n(3 ponteiros de árvore + 1 structponteiro).

  Os BSTs em árvore também precisariam de mais informações sobre o equilíbrio, por exemplo, preto-vermelho-ness.

• a implementação do array dinâmico pode ter tamanho 2nlogo após uma duplicação. Então, em média, será 1.5n.

Por outro lado, o heap da árvore tem a melhor inserção de pior caso, porque copiar o array dinâmico de backup para dobrar seu tamanho é o O(n)pior caso, enquanto o heap da árvore faz novas alocações pequenas para cada nó.

Ainda assim, a duplicação da matriz de apoio é O(1)amortizada, reduzindo-se a uma consideração de latência máxima. Mencionado aqui .

Filosofia

• As BSTs mantêm uma propriedade global entre um pai e todos os descendentes (esquerda menor, direita maior).

  O nó superior de uma BST é o elemento do meio, que requer conhecimento global para manter (sabendo quantos elementos menores e maiores existem).

  Essa propriedade global é mais cara de manter (log n insert), mas fornece pesquisas mais poderosas (log n search).

• As pilhas mantêm uma propriedade local entre pais e filhos diretos (pai> filhos).

  A nota principal de um heap é o grande elemento, que requer apenas o conhecimento local para manter (conhecer seu pai).

Lista duplamente vinculada

Uma lista duplamente vinculada pode ser vista como subconjunto da pilha em que o primeiro item tem maior prioridade, então vamos compará-los aqui também:

• inserção:
  • posição:
    • lista duplamente vinculada: o item inserido deve ser o primeiro ou o último, pois só temos ponteiros para esses elementos.
    • pilha binária: o item inserido pode terminar em qualquer posição. Menos restritivo que a lista vinculada.
  • Tempo:
    • lista duplamente vinculada: na O(1)pior das hipóteses, pois temos ponteiros para os itens e a atualização é realmente simples
    • pilha binária: O(1)média, pior que a lista vinculada. Troca por ter uma posição de inserção mais geral.
• pesquisa: O(n)para ambos

Um caso de uso para isso é quando a chave do heap é o carimbo de data / hora atual: nesse caso, novas entradas sempre irão para o início da lista. Assim, podemos até esquecer o registro de data e hora exato e manter a posição na lista como a prioridade.

Isso pode ser usado para implementar um cache LRU . Assim como em aplicativos de heap como o Dijkstra , você deseja manter um hashmap adicional da chave no nó correspondente da lista, para descobrir qual nó atualizar rapidamente.

Comparação de diferentes BST Balanceados

Embora a inserção assintótica e os tempos de localização de todas as estruturas de dados classificadas como "BSTs balanceadas" que eu vi até agora sejam os mesmos, BBSTs diferentes têm compensações diferentes. Ainda não estudei completamente isso, mas seria bom resumir essas trocas aqui:

• Árvore vermelho-preta . Parece ser o BBST mais usado a partir de 2019, por exemplo, é o usado pela implementação do GCC 8.3.0 C ++
• Árvore AVL . Parece ser um pouco mais equilibrado do que o BST, portanto, seria melhor encontrar a latência, ao custo de descobertas um pouco mais caras. O Wiki resume: "As árvores AVL são frequentemente comparadas com as árvores vermelho-preto porque ambas suportam o mesmo conjunto de operações e demoram [o mesmo] tempo para as operações básicas. Para aplicativos de pesquisa intensiva, as árvores AVL são mais rápidas que as árvores vermelho-preto porque elas são mais estritamente balanceadas.Como as árvores vermelho-pretas, as árvores AVL são balanceadas em altura.Em geral, ambas não são balanceadas em peso nem mu para qualquer mu <1/2; ou seja, os nós irmãos podem ter um enorme números diferentes de descendentes ".
• WAVL . O artigo original menciona vantagens dessa versão em termos de limites nas operações de reequilíbrio e rotação.

Veja também

Pergunta semelhante no CS: Qual é a diferença entre uma árvore de pesquisa binária e uma pilha binária?

Com a estrutura de dados, é preciso distinguir os níveis de preocupação.

1. As estruturas de dados abstratas (objetos armazenados, suas operações) nesta pergunta são diferentes. Um implementa uma fila de prioridade, o outro um conjunto. Uma fila de prioridade não está interessada em encontrar um elemento arbitrário, apenas aquele com a maior prioridade.

2. A implementação concreta das estruturas. Aqui, à primeira vista, ambas são árvores (binárias), com diferentes propriedades estruturais. Tanto a ordem relativa das chaves quanto as possíveis estruturas globais diferem. (Um pouco impreciso, as BSTchaves são ordenadas da esquerda para a direita, em uma pilha são ordenadas de cima para baixo.) Como o IPlant observa corretamente, uma pilha também deve estar "concluída".

3. Há uma diferença final na implementação de baixo nível . Uma árvore de pesquisa binária (não balanceada) possui uma implementação padrão usando ponteiros. Uma pilha binária, pelo contrário, tem uma implementação eficiente usando uma matriz (precisamente por causa da estrutura restrita).

Além das respostas anteriores, o heap deve ter a propriedade de estrutura de heap; a árvore deve estar cheia e a camada mais inferior, que nem sempre pode estar cheia, deve ser preenchida da esquerda para a direita, sem espaços.