Equilibrando uma árvore binária (AVL)

StackOverflow https://stackoverflow.com/questions/133610

Pergunta

Ok, este é mais um no reino teoria para os caras do CS ao redor.

Na década de 90 eu fiz muito bem na implementação BST de. A única coisa que eu nunca poderia ter a minha cabeça ao redor era a complexidade do algoritmo para equilibrar uma árvore binária (AVL).

Vocês podem me ajudar nisso?

Foi útil?

Solução

Uma árvore de bode expiatório tem possivelmente o algoritmo mais simples equilíbrio entre a determinação de entender. Se qualquer inserção faz com que o novo nó a ser muito profundo, ele encontra um nó em torno do qual a reequilibrar, olhando para equilíbrio de peso, em vez de equilíbrio altura. A regra para se reequilibrar na exclusão também é simples. Ele não armazena qualquer informação arcano nos gânglios. É mais complicado de provar que é correto, mas você não precisa que para entender o algoritmo ...

No entanto, ao contrário de um AVL que não é altura equilibrada em todos os momentos. Como rubro-negro cujo desequilíbrio é limitado, mas ao contrário do vermelho-preto É ajustável com um parâmetro, portanto, para a maioria dos fins práticos, parece tão equilibrada quanto você precisa que ele seja. Eu suspeito que se você ajustá-lo com muita força, porém, acaba tão ruim ou pior do que AVL para inserções de pior caso.

Resposta à pergunta edit

eu vou dar o meu caminho pessoal para árvores AVL entendimento.

Primeiro você tem que entender o que uma rotação árvore é, por isso, ignorar tudo o que você já ouviu os algoritmos AVL e entender isso. Começar em linha reta em sua cabeça que é uma rotação direita e que é uma rotação à esquerda, e que cada um faz a árvore, ou então as descrições dos métodos precisos só vai confundi-lo.

Em seguida, compreender que o truque para equilibrar árvores AVL é que cada registros de nó em que a diferença entre a altura da sua subárvores esquerda e direita. A definição de 'altura equilibrada' é que este é entre -1 e 1 inclusive para cada nó na árvore.

A seguir, entender que se você tiver adicionado ou removido de um nó, você pode ter desequilibrado a árvore. Mas você só pode ter alterado o equilíbrio de nós que são ancestrais do nó tiver adicionado ou removido. Então, o que você vai fazer é trabalhar o seu caminho de volta até a árvore, usando rotações para equilibrar todos os nós desequilibrado que você encontrar, e atualizar a sua pontuação de equilíbrio, até que a árvore é equilibrada novamente.

A parte final de compreendê-lo é olhar para cima em uma referência decente as rotações específicas usadas para reequilibrar cada nó você encontra: esta é a "técnica" do que em oposição ao alto conceito. Você só tem que se lembrar dos detalhes ao modificar o código árvore AVL ou talvez durante exames de estruturas de dados. É anos desde a última vez tinha código de árvore AVL tanto como aberto no depurador - implementações tendem a chegar a um ponto onde trabalham e, em seguida, ficar trabalhando. Então, eu realmente não me lembro. Você pode tipo de trabalho para fora em uma mesa usando algumas fichas de poker, mas é difícil ter certeza de que você realmente tem todos os casos (não há muitos). Melhor apenas para procurá-lo.

Depois, há o negócio de traduzir tudo em código.

Eu não acho que olhando para listagens de código ajuda muito com qualquer fase, exceto a última, então ignorá-los. Mesmo no melhor dos casos, onde o código está escrito claramente, ele vai olhar como uma descrição clássica do processo, mas sem os diagramas. Num caso mais típico é uma confusão de manipulação C estrutura. Então, se ater apenas aos livros.

Outras dicas

Eu não acho que é bom para postar códigos completos para equilibrar nó algoritmos aqui desde que ficar muito grande. No entanto, o artigo da Wikipedia sobre árvores vermelhas e pretas contém uma implementação completa C do algoritmo e o artigo sobre AVL árvores tem vários links para implementações de alta qualidade também.

Estas duas implementações são suficientes para a maioria dos cenários de uso geral.

Eu tenho feito alguns trabalhos com árvores AVL recentemente.

A melhor ajuda que eu era capaz de encontrar sobre a forma de equilibrá-los era através de pesquisa do Google.

Eu apenas codificado em torno este código pseudo (se você entender como fazer rotações é muito fácil de implementar). 

IF tree is right heavy
{
  IF tree's right subtree is left heavy
  {
     Perform Double Left rotation 
  }
  ELSE
  {
     Perform Single Left rotation
  }
}
ELSE IF tree is left heavy
{
  IF tree's left subtree is right heavy
  {
     Perform Double Right rotation
  }
  ELSE
  {
     Perform Single Right rotation
  }
}

Eu concordo, um programa completo não seria apropriada.

Enquanto clássica AVL e RB uso árvore de uma abordagem determinista, gostaria de sugerir a ter um olhar para " Randomized binário procurar árvores " que são menos onerosos para manter equilibrada e garantir um bom equilíbrio independentemente da distribuição estatística das chaves.

A árvore AVL é ineficiente porque você tem que fazer potencialmente muitas rotações por inserção / exclusão.

A árvore Vermelho-Preto é provavelmente uma alternativa melhor porque inserções / eliminações são muito mais eficientes. Esta estrutura garante o caminho mais longo a uma folha é não mais do que duas vezes o caminho mais curto. Assim, enquanto menos equilibrado do que uma árvore AVL, os piores casos desequilibradas são evitados.

Se a sua árvore será lido muitas vezes, e não será alterado depois que ele é criado, pode valer a pena a sobrecarga extra para uma árvore AVL totalmente equilibrada. Também a árvore Vermelho-Preto requer um bit extra de armazenamento para cada nó, que dão "cor" do nó.

Para equilibrar uma árvore I AVL só escrevi um monte de funções que eu pensei em compartilhar com todos aqui. Eu acho que essa implementação é impecável. Consultas / perguntas / críticas são naturalmente bem-vindo:

http://uploading.com/files/5883f1c7/AVL_Balance.cpp/

Sendo um novato para Stackoverflow, eu tentei postar meu código aqui, mas foi preso com maus problemas de formatação. Então, carregou o arquivo no link acima.

Felicidades.

há uma implementação completa de um auto balanceamento AVL árvore @ http: // code.google.com/p/self-balancing-avl-tree/. Ele também implementa operações concatenar e dividir o tempo logarítmica, bem como um mapa / coleções MultiMap

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top