Quando as árvores binárias são melhores que as hashtables em aplicativos do mundo real?

Atualmente, estou analisando minhas estruturas de dados e algoritmos básicos, parte disso é a Árvore Binária. Eu entendo os algoritmos e como implementar uma árvore de pesquisa binária e tal. Faço isso como é inteligente que possamos fazer pesquisas em tempo O (log n).

No entanto, estou tendo dificuldade em encontrar um exemplo de quando usaria uma árvore binária, em que uma tabela de hash não faria o mesmo / melhor trabalho. Fiz algumas pesquisas e descobri que ele é usado para gráficos 3D, algo sobre quais itens devem ser exibidos. No entanto, tenho dificuldade em me relacionar com isso.

Alguém pode me dar um exemplo de onde seria melhor usar uma árvore binária sobre uma tabela de hash?

As tabelas de hash só podem dizer se um elemento está presente ou não.

Aqui estão algumas coisas que você pode fazer com uma árvore binária que você não pode fazer com uma tabela de hash.

• percurso ordenado da árvore
• encontre o próximo elemento mais próximo
• encontre todos os elementos menores ou maiores que um determinado valor

Veja este artigo da wikipedia sobre árvores Kd para obter um exemplo de uma estrutura de dados do mundo real que utiliza as propriedades especiais de árvores binárias. http://en.wikipedia.org/wiki/K-d_tree

Um domínio de aplicativo em que as árvores binárias são melhores ou mais facilmente ajustáveis ​​do que certas alternativas são as estruturas de dados persistentes (geralmente usadas em programação (puramente) funcional).

Uma estrutura de dados persistente é uma estrutura de dados que preserva a versão anterior de si mesma quando é modificada. (As estruturas de dados que não possuem essa propriedade são chamadas efêmeras .) Um benefício desse tipo de estrutura de dados é que ele permite o compartilhamento de partes da estrutura de dados - já que é garantido que a estrutura em si não muda, é seguro compartilhá-la. livremente entre outras estruturas de dados e até threads, sem se preocupar com a alteração. Outro benefício subjetivo é que essas estruturas de dados são mais fáceis de raciocinar.

Conceitualmente, você pode ter um tipo de dados imutável que é uma lista de números, por exemplo, . Em seguida, você pode introduzir um novo valor que adicione dois números à frente desta lista: . O que aconteceu com ? Nada - , ainda. Será que copiar esses três elementos e colocá-lo em sua própria lista, então? Idealmente, não - os valores na lista pertencem a , também:$L_1 = \{3,4,5\}$$L_2 = cons(1,cons(2,L_1)) = \{1,2,3,4,5\}$$L_1$$L_1 = \{3,4,5\}$$L_2$$L_1$$L_2$

$\overbrace{ 1, 2, \underbrace{3,4,5}_{L_1} }^{L_2}$

Existem estruturas de dados que são mais adequadas para implementar listas persistentes como a acima. Na mesma linha, as árvores binárias são mais adequadas para implementar estruturas de dados persistentes com certas propriedades do que outras estruturas ou estratégias de dados. E o compartilhamento estrutural mostrado no exemplo com as duas listas é transferido para árvores binárias - você pode imaginar que várias versões de uma árvore podem compartilhar subárvores que elas têm em comum.

Como eu disse, algumas estruturas de dados são mais fáceis de alterar para serem persistentes. Você menciona a tabela de hash, que geralmente é (se não necessariamente) uma estrutura de dados efêmera. Parece menos óbvio como é possível ajustar uma estratégia de implementação comum para que uma tabela de hash seja persistente. Considere que uma tabela de hash geralmente é implementada com uma matriz (especificamente, matrizes que são implementadas como uma parte contínua da memória). As matrizes são boas, pois fornecem acesso aleatório aos elementos, o que é uma propriedade importante, pois você deseja idealmente ter$O(1)$acesso médio aos elementos na tabela de hash. Mas as matrizes não são tão boas quando se trata de criar estruturas de dados persistentes. O essencial é que, embora você possa criar um tipo de dados imutável de matriz, pela natureza das matrizes, corre o risco de fazer muitas cópias - se o tipo de lista acima mencionado tiver sido implementado com matrizes, você arriscará criar matriz totalmente nova com cinco elementos, em vez de compartilhar parte dela. E se você quiser modificar algo no meio da matriz? A resposta mais óbvia - e aparentemente inevitável - é copiar novamente .

Estruturas de dados persistentes não evitam a cópia, em geral. Mas certas estruturas de dados tornam a cópia menos frequente. Essa é uma propriedade desejável quando você exige que uma estrutura de dados seja imutável.

Uma árvore binária tem muitos aplicativos, especialmente se incluirmos todas as árvores binárias e não apenas as árvores de pesquisa binária. Os montes são implementados como árvores binárias, nas quais o elemento mais alto é um valor mínimo ou máximo de todos os elementos, o que é muito útil para um cenário que exige uma fila de prioridade.

Os hashmaps são muito eficientes em um tipo de operação definida, onde se está simplesmente verificando a existência de um elemento. Mas eles são mais fracos quando se trata de executar operações de verificação inexistentes em dados ordenados ou classificados. Além disso, embora fosse possível com os ajustes dos algoritmos de hash, as árvores binárias parecem suportar melhor a noção de pesquisas parciais de chave. Por exemplo, pode-se tentar usar uma árvore binária de strings para responder quais palavras começam com "an". A concessão de um trie seria uma melhor estrutura de dados para esse tipo de cenário.