AVL Trees e o mundo REAL

14

na escola, aprendemos como podemos equilibrar uma árvore AVL em uma inserção ou exclusão.

Como esse tipo de conhecimento realmente será útil no mundo real? Alguém pode dar um exemplo de quando esse tipo de conhecimento seria útil?

Pelo que tenho visto, no local de trabalho esses detalhes quase nunca surgem ...

Eu posso ver como o conhecimento detalhado sobre algoritmos e algumas estruturas de dados pode ser importante, mas não detalhes como rotações de árvore AVL (e conceitos detalhados similares).

obrigado!

    
por rrazd 02.07.2011 / 20:00
fonte

3 respostas

13

O estudo de árvores AVL pode ser útil pelas seguintes razões:

  • É uma ótima prática para raciocinar sobre dados abstratos. Você não precisa pensar em uma árvore em particular, você tem que considerar todas as possibilidades. A prática com esse tipo de raciocínio também pode ajudar em casos mais simples.

  • É uma ótima prática para entender predicados e contratos. Garantir que uma árvore seja equilibrada e as ferramentas que você usa para provar que cada operação preserva o equilíbrio podem, por exemplo, ser aplicadas a preocupações de segurança e a códigos paralelos.

  • Ele permite que você escreva suas próprias variantes ou crie até mesmo novos tipos de estruturas de dados.

  • Você pode precisar implementar uma árvore AVL para uma nova biblioteca ou plataforma.

Você pode debater os méritos específicos de aprender cada tipo de algoritmo de ordenação ou cada tipo de árvore balanceada. Não importa realmente quais são os que você acaba aprendendo, mas deve ter certeza de obter uma cobertura completa dos tópicos mais importantes.

Se você quiser ver o quão importante é saber algoritmos no mundo real, leia " Como matar uma grande idéia! ", um artigo na Inc sobre a queda do Friendster e como a menor aplicação de princípios fundamentais para melhorar a eficiência poderia tê-los ajudado.

    
por 02.07.2011 / 20:45
fonte
5

Além dos pontos Macneils ...

Árvores vermelho-preto são talvez mais diretamente úteis porque existem operações eficientes úteis que não são amplamente suportadas em implementações de bibliotecas padrão, como o C ++ std::map (pelo menos AFAIK). Árvores vermelhas e pretas podem suportar "dividir" (cortar uma árvore em duas, uma contendo chaves menores que uma chave especificada, e uma contendo chaves maiores) e "juntar" (o contrário, combinando uma árvore de grandes chaves com uma árvore pequena chaves) podem ser feitas no tempo O (log n), mas se elas forem suportadas em bibliotecas de contêiner padrão, parece ser uma coisa bem oculta.

No entanto, estruturas de dados "aumentadas" são comuns. Um exemplo simples é adicionar informações de tamanho da subárvore aos nós em praticamente qualquer estrutura de dados de árvore para suportar o subscrição O (log n). Exemplos mais sofisticados incluem árvores de intervalo.

Uma vez que você tenha a ideia de aumentar as estruturas de dados, há muitas variações que podem ser úteis para aplicativos específicos - e muito poucas estão disponíveis pré-configuradas como uma biblioteca. Estruturas de dados de biblioteca padrão existentes (por exemplo, como std::map ) não podem ser aumentadas antes de copiar o código-fonte e modificá-lo diretamente - você não pode aumentá-las usando parâmetros de modelo.

É claro que para desenvolver uma estrutura de dados aumentada, você precisa entender a estrutura de dados subjacente não aumentada.

As árvores AVL podem ser mais rápidas do que as árvores vermelhas e pretas se você fizer muito mais pesquisas do que inserções / exclusões (e desde que não precise dessas operações de divisão / junção), portanto, dependendo do aplicativo, elas podem ser muito boa base para aumentar.

    
por 03.07.2011 / 02:20
fonte
5

Não

Não é realmente útil no mundo real ...

exceto para fazer você pensar .

O mundo real tem problemas muito mais difíceis , muitos dos quais não já têm soluções bem conhecidas.

    
por 03.07.2011 / 05:30
fonte