Estou aprendendo Haskell e, como exercício, estou criando árvores binárias. Tendo feito uma árvore binária regular, quero adaptá-la para se auto balancear. Então:
- Qual é o mais eficiente?
- Qual é a mais fácil de implementar?
- Qual é o mais usado?
Mas crucialmente, o que você recomenda?
Suponho que isso pertence aqui porque está aberto ao debate.
haskell
functional-programming
data-structures
binary-tree
dan_waterworth
fonte
fonte
Respostas:
Eu recomendaria que você iniciasse com uma árvore vermelho-preta ou uma árvore AVL .
A árvore vermelho-preta é mais rápida para inserir, mas a árvore AVL tem uma leve margem para pesquisas. A árvore AVL é provavelmente um pouco mais fácil de implementar, mas não muito com base na minha própria experiência.
A árvore AVL garante que a árvore seja equilibrada após cada inserção ou exclusão (nenhuma subárvore possui um fator de equilíbrio maior que 1 / -1, enquanto a árvore Vermelho-preta garante que a árvore esteja razoavelmente equilibrada a qualquer momento.
fonte
Eu consideraria uma alternativa se você estiver bem com estruturas de dados aleatórios : Skip Lists .
Do ponto de vista de alto nível, é uma estrutura em árvore, exceto que não é implementada como uma árvore, mas como uma lista com várias camadas de links.
Você receberá inserções / pesquisas / exclusões O (log N) e não precisará lidar com todos esses casos complicados de reequilíbrio.
Porém, nunca pensei em implementá-los em uma linguagem funcional, e a página da Wikipédia não mostra nenhuma, portanto pode não ser fácil (devido à imutabilidade)
fonte
Se você deseja iniciar uma estrutura relativamente fácil (tanto as árvores AVL quanto as vermelhas e pretas são complicadas), uma opção é um treap - nomeado como uma combinação de "tree" e "heap".
Cada nó obtém um valor de "prioridade", geralmente atribuído aleatoriamente à medida que o nó é criado. Os nós são posicionados na árvore para que a ordem das chaves seja respeitada e para que a ordem de pilha de valores de prioridade seja respeitada. Ordenação de pilha significa que ambos os filhos de um pai têm prioridades mais baixas que o pai.
EDIT excluído "dentro dos valores-chave" acima - a prioridade e a ordem das chaves se aplicam juntas, portanto a prioridade é significativa mesmo para chaves exclusivas.
É uma combinação interessante. Se as chaves são únicas e as prioridades são únicas, existe uma estrutura em árvore exclusiva para qualquer conjunto de nós. Mesmo assim, inserções e exclusões são eficientes. Estritamente falando, a árvore pode ser desequilibrada ao ponto de efetivamente ser uma lista vinculada, mas isso é extremamente improvável (como nas árvores binárias padrão), inclusive em casos normais, como chaves inseridas em ordem (ao contrário das árvores binárias padrão).
fonte
Vagas e difíceis de responder. As complexidades computacionais são todas bem definidas. Se é isso que você quer dizer com eficiência, não há debate real. De fato, todos os bons algoritmos vêm com provas e fatores de complexidade.
Se você quer dizer "tempo de execução" ou "uso de memória", precisará comparar as implementações reais. Então, idioma, tempo de execução, sistema operacional e outros fatores entram em jogo, dificultando a resposta da pergunta.
Vagas e difíceis de responder. Alguns algoritmos podem parecer complexos para você, mas triviais para mim.
Vagas e difíceis de responder. Primeiro, há o "por quem?" parte disso? Apenas Haskell? E o C ou C ++? Segundo, há o problema de software proprietário em que não temos acesso à fonte para fazer uma pesquisa.
Corrigir. Como seus outros critérios não são muito úteis, é isso que você obterá.
Você pode obter fonte para um grande número de algoritmos em árvore. Se você quiser aprender alguma coisa, pode simplesmente implementar todas as que encontrar. Em vez de pedir uma "recomendação", basta coletar todos os algoritmos que encontrar.
Aqui está a lista:
http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
Existem seis populares definidos. Comece com aqueles.
fonte
Se você está interessado em árvores Splay, há uma versão mais simples daquelas que, acredito, foram descritas pela primeira vez em um artigo de Allen e Munroe. Ele não possui as mesmas garantias de desempenho, mas evita complicações ao lidar com o reequilíbrio "zig-zig" vs. "zig-zag".
Basicamente, ao pesquisar (incluindo pesquisas de um ponto ou nó de inserção a ser excluído), o nó encontrado é girado diretamente em direção à raiz, de baixo para cima (por exemplo, quando uma função de pesquisa recursiva sai). Em cada etapa, você seleciona uma única rotação para a esquerda ou direita, dependendo de o filho que você deseja dar outro passo em direção à raiz ser o filho certo ou o filho esquerdo (se me lembro corretamente das instruções de rotação, respectivamente).
Assim como as árvores Splay, a idéia é que os itens acessados recentemente estejam sempre perto da raiz da árvore, para acessar rapidamente novamente. Sendo mais simples, essas árvores Allen-Munroe de rotação para raiz (o que eu as chamo - não sabem o nome oficial) podem ser mais rápidas, mas elas não têm a mesma garantia de desempenho amortizada.
Uma coisa: como essa estrutura de dados, por definição, sofre mutação, mesmo para operações de busca, provavelmente precisará ser implementada monadicamente. IOW talvez não seja uma boa opção para programação funcional.
fonte
Uma árvore equilibrada muito simples é uma árvore AA . Sua invariante é mais simples e, portanto, mais fácil de implementar. Devido à sua simplicidade, seu desempenho ainda é bom.
Como exercício avançado, você pode tentar usar GADTs para implementar uma das variantes de árvores balanceadas cuja invariante é imposta pelo tipo de sistema de tipos.
fonte