Por que as árvores Vermelho-Preto são tão populares?

Parece que em todo lugar que olho, as estruturas de dados estão sendo implementadas usando árvores vermelho-pretas ( std::setem C ++, SortedDictionaryem C # etc.)

Tendo acabado de cobrir (a, b), vermelho-preto e árvores AVL na minha classe de algoritmos, aqui está o que eu descobri (também perguntando por professores, olhando alguns livros e pesquisando um pouco):

• As árvores AVL têm profundidade média menor que as árvores vermelho-preto e, portanto, a busca de um valor na árvore AVL é consistentemente mais rápida.
• As árvores preto-vermelho fazem menos mudanças estruturais para se equilibrar do que as árvores AVL, o que poderia torná-las potencialmente mais rápidas para inserção / exclusão. Estou dizendo potencialmente, porque isso dependeria do custo da alteração estrutural da árvore, pois dependerá muito do tempo de execução e implementação (também pode ser completamente diferente em uma linguagem funcional quando a árvore é imutável?)

Existem muitos benchmarks online que comparam as árvores AVL e Red-black, mas o que mais me impressionou é que meu professor disse basicamente que, geralmente, você faria uma de duas coisas:

• Ou você realmente não se importa muito com o desempenho; nesse caso, a diferença de 10 a 20% entre AVL e vermelho-preto na maioria dos casos não importa.
• Ou você realmente se preocupa com o desempenho, no caso de abandonar as árvores AVL e Vermelho-preto e optar por árvores B, que podem ser aprimoradas para funcionar muito melhor (ou (a, b) -árvores, eu ' vou colocar todos em uma cesta.)

A razão disso é que uma árvore B armazena dados de forma mais compacta na memória (um nó contém muitos valores) e haverá muito menos erros de cache. Você também pode ajustar a implementação com base no caso de uso e fazer com que a ordem da árvore B dependa do tamanho do cache da CPU, etc.

O problema é que não consigo encontrar quase nenhuma fonte que analise o uso na vida real de diferentes implementações de árvores de pesquisa em hardware moderno real. Examinei muitos livros sobre algoritmos e não encontrei nada que comparasse diferentes variantes de árvores, além de mostrar que uma tem profundidade média menor que a outra (o que realmente não diz muito sobre como a árvore se comportará). em programas reais.)

Dito isto, existe uma razão específica para o uso de árvores vermelho-pretas em todos os lugares, quando, com base no que foi dito acima, as árvores B devem superá-las? (como a única referência que eu pude encontrar também mostra http://lh3lh3.users.sourceforge.net/udb.shtml , mas pode ser apenas uma questão de implementação específica). Ou é a razão pela qual todo mundo usa árvores vermelho-pretas porque elas são fáceis de implementar ou, em outras palavras, difíceis de implementar mal?

Além disso, como isso muda quando se muda para o domínio das linguagens funcionais? Parece que Clojure e Scala usam tentativas mapeadas de matriz Hash , onde Clojure usa um fator de ramificação de 32.

Para citar a resposta da pergunta “ Traversals from the root in AVL trees and Red Black Trees ”

Para alguns tipos de árvores de pesquisa binária, incluindo árvores preto-vermelho, mas não árvores AVL, as "correções" na árvore podem ser facilmente previstas no caminho e executadas durante uma única passagem de cima para baixo, tornando a segunda passagem desnecessária. Esses algoritmos de inserção são tipicamente implementados com um loop em vez de recursão e geralmente são executados um pouco mais rápido na prática do que seus equivalentes de duas passagens.

Portanto, uma inserção de árvore RedBlack pode ser implementada sem recursão, em algumas CPUs a recursão é muito cara se você exceder o cache de chamada de função (por exemplo, SPARC devido ao uso da janela Register )

(Eu vi o software rodar 10 vezes mais rápido no Sparc removendo uma chamada de função, que resultou em um caminho de código frequentemente chamado muito profundo para a janela de registro. Como você não sabe a profundidade da janela de registro sistema do seu cliente e você não sabe a que distância da pilha de chamadas se encontra no "caminho do código quente", não usar a recursão é mais previsível.)

Também não correr o risco de ficar sem pilha é um benefício.

Também estive pesquisando esse tópico recentemente, então, aqui estão minhas descobertas, mas lembre-se de que não sou especialista em estruturas de dados!

Existem alguns casos em que você não pode usar árvores B.

Um caso de destaque é std::mapdo C ++ STL. O padrão exige que insertnão invalide os iteradores existentes

Nenhum iterador ou referência é invalidado.

http://en.cppreference.com/w/cpp/container/map/insert

Isso descarta a árvore B como uma implementação porque a inserção se moveria pelos elementos existentes.

Outro caso de uso semelhante são estruturas de dados intrusivas. Ou seja, em vez de armazenar seus dados dentro do nó da árvore, você armazena ponteiros para filhos / pais dentro de sua estrutura:

// non intrusive
struct Node<T> {
    T value;
    Node<T> *left;
    Node<T> *right;
};
using WalrusList = Node<Walrus>;

// intrusive
struct Walrus {
    // Tree part
    Walrus *left;
    Walrus *right;

    // Object part
    int age;
    Food[4] stomach;
};

Você simplesmente não pode tornar uma árvore B intrusiva, porque não é uma estrutura de dados somente para ponteiro.

Árvores preto-vermelho intrusivas são usadas, por exemplo, no jemalloc para gerenciar blocos de memória livres. Essa também é uma estrutura de dados popular no kernel do Linux.

Eu também acredito que a implementação "recursiva de cauda de passagem única" não é a razão da popularidade da árvore negra vermelha como uma estrutura de dados mutável .

$\log{n}$

$O(1)$

$O(1)$

A variante descrita nas estruturas opendatas usa ponteiros pai, um passe descendente recursivo para inserção e um loop loop iterativo para reparos. As chamadas recursivas estão em posições finais e os compiladores otimizam isso para um loop (eu verifiquei isso no Rust).

$O(1)$

Bem, essa não é uma resposta autorizada, mas sempre que tenho que codificar uma árvore de pesquisa binária equilibrada, é uma árvore vermelha e preta. Existem algumas razões para isso:

1) O custo médio de inserção é constante para árvores vermelho-pretas (se você não precisar pesquisar), enquanto é logarítmico para árvores AVL. Além disso, envolve no máximo uma reestruturação complicada. Ainda é O (log N) na pior das hipóteses, mas são apenas recolorações simples.

2) Eles exigem apenas 1 bit de informações extras por nó, e você pode encontrar uma maneira de obtê-las gratuitamente.

3) Não preciso fazer isso com muita frequência; portanto, toda vez que faço, tenho que descobrir como fazer tudo de novo. As regras simples e a correspondência com 2 a 4 árvores fazem com que pareça fácil todas as vezes , mesmo que o código seja sempre complicado . Eu ainda espero que um dia o código seja simples.

4) A maneira como a árvore vermelho-preta divide o nó correspondente da árvore 2-4 e insere a chave do meio no nó pai 2-4 apenas recolorindo é super elegante. Eu simplesmente amo fazer isso.

As árvores vermelho-preto ou AVL têm uma vantagem sobre as árvores B e similares quando a chave é longa ou por algum outro motivo, mover uma chave é caro.

Criei minha própria alternativa para std::setum projeto importante, por várias razões de desempenho. Eu escolhi o AVL em vez de vermelho-preto por razões de desempenho (mas esse pequeno aprimoramento de desempenho não era a justificativa para rodar sozinho, em vez de std :: set). A "chave" ser complicada e difícil de mover foi um fator significativo. As árvores (a, b) ainda fazem sentido se você precisar de outro nível de indireção na frente das teclas? As árvores AVL e vermelho-preto podem ser reestruturadas sem mover as chaves, de modo que elas têm essa vantagem quando as chaves são caras de se mover.