Árvore vermelha preta sobre árvore AVL

As árvores AVL e Red black são auto-equilibradas, exceto as cores vermelha e preta nos nós. Qual é a principal razão para escolher Red black trees em vez de árvores AVL? Quais são as aplicações de Red black trees?

Qual é a principal razão para escolher Red black trees em vez de árvores AVL?

As árvores red-black e as árvores AVL são as árvores de pesquisa binárias balanceadas mais comumente usadas e oferecem suporte para inserção, exclusão e consulta garantida O(logN) time. No entanto, existem os seguintes pontos de comparação entre os dois:

• As árvores AVL são mais rigidamente balanceadas e, portanto, fornecem pesquisas mais rápidas. Portanto, para uma tarefa de pesquisa intensiva, use uma árvore AVL.
• Para tarefas intensivas de inserção, use uma árvore Red-Black.
• As árvores AVL armazenam o fator de equilíbrio em cada nó. Isso ocupa O(N)espaço extra. Porém, se sabemos que as chaves que serão inseridas na árvore sempre serão maiores que zero, podemos usar o bit de sinal das chaves para armazenar as informações de cor de uma árvore vermelho-preto. Assim, em tais casos, a árvore vermelho-preto não ocupa espaço extra.

Quais são as aplicações de Red black tree?

Árvores vermelho-pretas são de uso mais geral. Eles se saem relativamente bem em adicionar, remover e pesquisar, mas as árvores AVL têm pesquisas mais rápidas ao custo de adicionar / remover mais lentamente. A árvore vermelho-preto é usada no seguinte:

• Java: java.util.TreeMap,java.util.TreeSet
• C ++ STL (na maioria das implementações): map, multimap, multiset
• Kernel do Linux: planejador completamente justo, linux / rbtree.h

Tente ler isto artigo

Ele oferece alguns bons insights sobre diferenças, semelhanças, desempenho, etc.

Aqui está uma citação do artigo:

Árvores RB são, assim como árvores AVL, auto-equilibrantes. Ambos fornecem desempenho de inserção e pesquisa O (log n).

A diferença é que as RB-Trees garantem O (1) rotações por operação de pastilha. Isso é o que realmente custa o desempenho em implementações reais.

Simplificadas, as RB-Trees ganham essa vantagem por serem conceitualmente 2-3 árvores sem carregar a sobrecarga de estruturas de nós dinâmicas. Fisicamente, as árvores RB são implementadas como árvores binárias, as bandeiras vermelhas / pretas simulam 2-3 comportamento

Pelo que entendi, as árvores AVL e as árvores RB não estão muito distantes em termos de desempenho. Uma árvore RB é simplesmente uma variante de uma árvore B e o balanceamento é implementado de forma diferente de uma árvore AVL.

Nossa compreensão das diferenças de desempenho melhorou ao longo dos anos e agora o principal motivo para usar árvores vermelhas e pretas sobre AVL seria não ter acesso a uma boa implementação de AVL, uma vez que são um pouco menos comuns, talvez porque não são cobertos pelo CLRS.

Ambas as árvores são agora consideradas formas de árvores equilibradas, mas as vermelho-pretas são consistentemente mais lentas em cerca de 20% nos testes do mundo real . Ou até 30-40% mais lento quando os dados sequenciais são inseridos .

Portanto, as pessoas que estudaram árvores vermelho-pretas, mas não árvores AVL, tendem a escolher árvores vermelho-pretas. Os principais usos para árvores vermelho-pretas são detalhados na entrada da Wikipedia para eles .

Outras respostas aqui resumem bem os prós e contras das árvores RB e AVL, mas achei essa diferença particularmente interessante:

Árvores AVL não suportam custo de atualização amortizado constante [mas árvores vermelhas e pretas sim]

Fonte: Mehlhorn & Sanders (2008) (seção 7.4)

Assim, enquanto ambas as árvores RB e AVL garantem O (log (N)) tempo de pior caso para pesquisa, inserção e exclusão, restaurar a propriedade AVL / RB após inserir ou excluir um nó pode ser feito em O (1) tempo amortizado para árvores vermelho-pretas.

Os programadores geralmente não gostam de alocar memória dinamicamente. O problema com a árvore avl é que para "n" elementos você precisa de pelo menos log2 (log2 (n)) ... (height-> log2 (n)) bits para armazenar a altura da árvore! Portanto, quando você está lidando com dados enormes, não pode ter certeza de quantos bits alocar para armazenar a altura em cada nó.

Por exemplo, se você usar 4 bytes int (32 bits) para armazenar a altura. A altura máxima pode ser: 2 ^ 32 e, portanto, o número máximo de elementos que você pode armazenar na árvore é 2 ^ (2 ^ 32) - (parece ser muito grande, mas nesta era de dados nada é muito grande, eu acho). Portanto, se você ultrapassar esse limite, terá que alocar dinamicamente mais espaço para armazenar a altura.

Esta é uma resposta sugerida por um professor da minha universidade que me pareceu razoável! Espero que eu faça sentido.

Edições: As árvores AVL são mais equilibradas em comparação com Red Black Trees, mas podem causar mais rotações durante a inserção e exclusão. Portanto, se o seu aplicativo envolve muitas inserções e exclusões frequentes, então as árvores Red Black devem ser preferidas. E se as inserções e exclusões são menos frequentes e a pesquisa é a operação mais frequente, então a árvore AVL deve ser preferida em vez da árvore Red Black. --Fonte GEEKSFORGEEKS.ORG

O reequilíbrio da árvore AVL deve atender à propriedade abaixo. (Referência Wiki - Árvore AVL )

Em uma árvore AVL, as alturas das duas subárvores filhas de qualquer nó diferem em no máximo um; se a qualquer momento eles diferirem em mais de um, o rebalanceamento é feito para restaurar essa propriedade.

Portanto, isso implica que a altura geral da árvore AVL não pode enlouquecer, ou seja, as pesquisas serão melhores com Árvores AVL. E uma vez que operações adicionais (rotações) devem ser feitas para não deixar a altura enlouquecer, as operações de modificação da árvore podem ser um pouco caras.