Por que o std :: map é implementado como uma árvore vermelho-preta?

193

Por que é std::mapimplementado como uma árvore vermelho-preta ?

Existem várias árvores de pesquisa binária equilibrada (BSTs) por aí. Quais foram as desvantagens do design na escolha de uma árvore vermelho-preta?

c++ dictionary data-structures stl binary-search-tree Denis Gorodetskiy
fonte
26
Embora todas as implementações que eu vi use uma árvore RB, observe que isso ainda depende da implementação.
Thomas
3
@Thomas. É dependente da implementação; então, por que é que toda implementação usa RB-trees?
Denis Gorodetskiy
1
Eu realmente gostaria de saber se algum implementador de STL pensou em usar uma Skip List.
Matthieu M.
2
O mapa e o conjunto do C ++ são, na verdade, o mapa e o conjunto ordenados. Eles não são implementados usando funções de hash. Cada consulta levaria O(logn)e não O(1), mas os valores serão sempre classificados. A partir de C ++ 11 (eu acho), existem unordered_mape unordered_setque são implementados usando funções hash e enquanto eles não são ordenados, a maioria das consultas e operações são possíveis O(1)(em média)
SomethingSomething
@ Thomas que é verdade, mas não tão interessante na prática. O padrão oferece garantias de complexidade com um algoritmo específico ou conjunto de algoritmos em mente.
Justin Meiners

Respostas:

125

Provavelmente, os dois algoritmos de árvore de auto balanceamento mais comuns são as árvores Vermelho-Preto e AVL . Para equilibrar a árvore após uma inserção / atualização, ambos os algoritmos usam a noção de rotações em que os nós da árvore são rotacionados para executar o reequilíbrio.

Enquanto nos dois algoritmos as operações de inserção / exclusão são O (log n), no caso de reequilíbrio de árvore Vermelho-Preto, a rotação é uma operação O (1) , enquanto que com AVL essa é uma operação O (log n) , Árvore Vermelho-Preto é mais eficiente nesse aspecto do estágio de reequilíbrio e um dos possíveis motivos pelos quais é mais comum.

Árvores Red-Black são usadas na maioria das bibliotecas de coleções, incluindo as ofertas de Java e Microsoft .NET Framework.

Chris Taylor
fonte
54
você faz parecer que árvores preto-vermelho podem fazer modificações em O (1), o que não é verdade. as modificações das árvores são O (log n) para as árvores vermelho-preto e AVL. isso faz com que seja discutido se a parte de equilíbrio da modificação da árvore é O (1) ou O (log n) porque a operação principal já é O (log n). mesmo depois de todo o trabalho um pouco extra que as árvores AVL realizam, resulta em uma árvore mais equilibrada, o que leva a pesquisas um pouco mais rápidas. portanto, é uma troca perfeitamente válida e não torna as árvores AVL inferiores às árvores vermelho-pretas.
Necromancer
35
Você precisa olhar além da complexidade para o tempo de execução real para ver a diferença - as árvores AVL geralmente têm um tempo de execução total mais baixo quando há muito mais pesquisas do que inserções / exclusões. As árvores RB têm um tempo de execução total mais baixo quando há muito mais inserções / exclusões. A proporção exata em que a interrupção ocorre depende, é claro, de muitos detalhes de implementação, hardware e uso exato, mas como os autores da biblioteca precisam oferecer suporte a uma ampla variedade de padrões de uso, eles precisam adivinhar. O AVL também é um pouco mais difícil de implementar, portanto, você pode querer um benefício comprovado para usá-lo.
21711 Steve Joplin
6
A árvore RB não é uma "implementação padrão". Cada implementador escolhe uma implementação. Até onde sabemos, todos eles escolheram árvores RB, portanto, presumivelmente, isso é para desempenho ou para facilidade de implementação / manutenção. Como eu disse, o ponto de interrupção do desempenho pode não significar que eles acham que há mais inserções / exclusões do que pesquisas, apenas que a proporção entre os dois está acima do nível em que eles acham que o RB provavelmente supera o AVL.
21711 Steve Jobs (
9
@ Denis: infelizmente, a única maneira de obter números é fazer uma lista de std::map implementações, rastrear os desenvolvedores e perguntar-lhes quais critérios eles usaram para tomar a decisão, então isso continua sendo especulação.
Steve Jessop
4
Falta de tudo isso o custo, por nó, para armazenar as informações auxiliares necessárias para tomar decisões de equilíbrio. As árvores Vermelho-Preto requerem 1 bit para representar a cor. As árvores AVL requerem pelo menos 2 bits (para representar -1, 0 ou 1).
precisa saber é o seguinte
46

Realmente depende do uso. A árvore AVL geralmente tem mais rotações de reequilíbrio. Portanto, se seu aplicativo não possui muitas operações de inserção e exclusão, mas pesa bastante na pesquisa, a árvore AVL provavelmente é uma boa escolha.

std::map usa árvore Red-Black, pois obtém uma compensação razoável entre a velocidade de inserção / exclusão de nó e pesquisa.

webbertiger
fonte
1
Você tem certeza sobre isso??? Pessoalmente, acho que a árvore Vermelho-Preto é uma ou mais complexa, nunca mais simples. A única coisa, é na árvore Rd-Black, o reequilíbrio ocorre com menos frequência que o AVL.
Eric Ouellet
1
@Eric Teoricamente, a árvore R / B e a árvore AVL têm complexidade O (log n)) para inserção e exclusão. Mas uma grande parte do custo da operação é a rotação, que é diferente entre essas duas árvores. Por favor, consulte discuss.fogcreek.com/joelonsoftware/… Citação: "o balanceamento de uma árvore AVL pode exigir rotações O (log n), enquanto uma árvore vermelha e preta leva no máximo duas rotações para equilibrá-la (embora possa ser necessário examine os nós O (log n) para decidir onde as rotações são necessárias) ". Editou meus comentários de acordo.
webbertiger
26

As árvores AVL têm uma altura máxima de 1,44 logn, enquanto as árvores RB têm um máximo de 2logn. Inserir um elemento em um AVL pode implicar um reequilíbrio em um ponto da árvore. O reequilíbrio termina a inserção. Após a inserção de uma nova folha, a atualização dos antepassados ​​dessa folha deve ser feita até a raiz ou até um ponto em que as duas subárvores tenham a mesma profundidade. A probabilidade de ter de atualizar k nós é 1/3 ^ k. O reequilíbrio é O (1). A remoção de um elemento pode implicar mais de um reequilíbrio (até metade da profundidade da árvore).

As árvores RB são árvores B da ordem 4, representadas como árvores de pesquisa binária. Um nó de 4 na árvore B resulta em dois níveis no BST equivalente. Na pior das hipóteses, todos os nós da árvore são 2 nós, com apenas uma cadeia de 3 nós em uma folha. Essa folha estará a uma distância de 2logn da raiz.

Descendo da raiz até o ponto de inserção, é necessário alterar 4 nós em 2 nós, para garantir que qualquer inserção não sature uma folha. Voltando à inserção, todos esses nós precisam ser analisados ​​para garantir que eles representem corretamente 4 nós. Isso também pode ser feito descendo na árvore. O custo global será o mesmo. Nao tem almoço gratis! A remoção de um elemento da árvore é da mesma ordem.

Todas essas árvores exigem que os nós carreguem informações sobre altura, peso, cor etc. Somente as árvores Splay estão livres de tais informações adicionais. Mas a maioria das pessoas tem medo das árvores espalhadas, por causa da ramificação de sua estrutura!

Finalmente, as árvores também podem transportar informações de peso nos nós, permitindo o equilíbrio de peso. Vários esquemas podem ser aplicados. Deve-se reequilibrar quando uma subárvore contém mais de 3 vezes o número de elementos da outra subárvore. O reequilíbrio é feito novamente através de uma rotação única ou dupla. Isso significa o pior caso de 2.4logn. Pode-se sair com 2 vezes em vez de 3, uma proporção muito melhor, mas pode significar deixar um pouco menos de 1% das subárvores desequilibradas aqui e ali. Complicado!

Que tipo de árvore é a melhor? AVL com certeza. Eles são os mais simples de codificar e têm a pior altura mais próxima do logon. Para uma árvore de 1000000 elementos, um AVL terá no máximo a altura 29, um RB 40 e um peso equilibrado 36 ou 50, dependendo da proporção.

Existem muitas outras variáveis: aleatoriedade, proporção de acréscimos, exclusões, pesquisas, etc.

user847376
fonte
2
Boa resposta. Mas se os AVLs são os melhores, por que a biblioteca padrão implementa std :: map como uma árvore RB?
Denis Gorodetskiy
13
Discordo que as árvores AVL são inquestionavelmente as melhores. Embora tenham uma baixa estatura, eles exigem (no total) mais trabalho para realizar o reequilíbrio do que as árvores vermelhas / pretas (O (log n) trabalho de reequilíbrio versus O (1) trabalho de reequilíbrio amortizado). Espalhar árvores pode ser muito, muito melhor e sua afirmação de que as pessoas têm medo delas é infundada. Não existe um "melhor" esquema universal de balanceamento de árvores por aí.
templatetypedef
Resposta quase perfeita. Por que você disse que o AVL é o melhor? Isso está simplesmente errado e é por isso que a implementação mais geral usa a árvore Vermelho-Preto. Você precisa ter uma proporção muito maior de leitura sobre manipulação para escolher AVL. Além disso, o AVL tem um pouco menos espaço de memória que o RB.
Eric Ouellet
Concordo que o AVL tende a ser melhor na maioria dos casos, porque geralmente as árvores são pesquisadas com mais frequência do que são inseridas. Por que a árvore RB é tão amplamente considerada melhor quando é a que possui uma pequena vantagem no caso de gravação principalmente e, mais importante, uma ligeira desvantagem no caso de leitura principal? Acredita-se realmente que você irá inserir mais do que encontrará?
doug65536
25

As respostas anteriores tratam apenas de alternativas em árvore e o preto vermelho provavelmente permanece apenas por razões históricas.

Por que não uma tabela de hash?

Um tipo requer apenas que o <operador (comparação) seja usado como uma chave em uma árvore. No entanto, as tabelas de hash exigem que cada tipo de chave tenha uma hashfunção definida. Manter os requisitos de tipo no mínimo é muito importante para a programação genérica, para que você possa usá-lo com uma grande variedade de tipos e algoritmos.

Projetar uma boa tabela de hash requer um conhecimento íntimo do contexto em que ela será usada. Ele deve usar endereçamento aberto ou encadeamento vinculado? Quais níveis de carga ele deve aceitar antes de redimensionar? Deve usar um hash caro que evita colisões, ou um que seja áspero e rápido?

Como o STL não pode prever qual é a melhor opção para o seu aplicativo, o padrão precisa ser mais flexível. Árvores "simplesmente funcionam" e escalam bem.

(O C ++ 11 adicionou tabelas de hash com unordered_map. Você pode ver na documentação necessária para definir políticas para configurar muitas dessas opções.)

E as outras árvores?

As árvores Red Black oferecem pesquisa rápida e são auto balanceadas, diferentemente das BSTs. Outro usuário apontou suas vantagens sobre a árvore AVL auto-balanceada.

Alexander Stepanov (o criador do STL) disse que usaria uma árvore B * em vez de uma árvore Vermelho-Preto se ele escrevesse std::mapnovamente, porque é mais amigável para os caches de memória modernos.

Uma das maiores mudanças desde então tem sido o crescimento de caches. As falhas de cache são muito caras, portanto a localidade de referência é muito mais importante agora. Estruturas de dados baseadas em nós, com baixa localidade de referência, fazem muito menos sentido. Se eu estivesse projetando o STL hoje, teria um conjunto diferente de contêineres. Por exemplo, uma árvore B * na memória é uma escolha muito melhor do que uma árvore vermelho-preta para implementar um contêiner associativo. - Alexander Stepanov

Os mapas devem sempre usar árvores?

Outra possível implementação de mapas seria um vetor classificado (classificação por inserção) e pesquisa binária. Isso funcionaria bem para contêineres que não são modificados com frequência, mas são consultados com frequência. Costumo fazer isso em C como qsorte bsearchsão incorporados.

Eu preciso mesmo usar o mapa?

Considerações de cache significa que raramente faz sentido usar std::listou std::dequemaisstd:vector mesmo para aquelas situações que aprendemos na escola (como remover um elemento do meio da lista). Aplicando esse mesmo raciocínio, o uso de um loop for na pesquisa linear de uma lista geralmente é mais eficiente e mais limpo do que construir um mapa para algumas pesquisas.

É claro que escolher um contêiner legível geralmente é mais importante que o desempenho.

Justin Meiners
fonte
3

Atualização 14/06/2017: webbertiger edite sua resposta depois que comentei. Devo salientar que a resposta agora é muito melhor aos meus olhos. Mas mantive minha resposta como informações adicionais ...

Devido ao fato de eu achar que a primeira resposta está errada (correção: não mais as duas) e a terceira afirmação errada. Sinto que tive que esclarecer as coisas ...

As 2 árvores mais populares são AVL e Red Black (RB). A principal diferença está na utilização:

  • AVL: Melhor se a taxa de consulta (leitura) for maior que a manipulação (modificação). A pegada de memória é um pouco menor que a RB (devido ao bit necessário para colorir).
  • RB: Melhor nos casos gerais em que existe um equilíbrio entre consulta (leitura) e manipulação (modificação) ou mais modificações sobre consulta. Uma pegada de memória um pouco maior devido ao armazenamento da bandeira vermelha e preta.

A principal diferença vem da coloração. Você tem menos ações de reequilíbrio na árvore RB do que o AVL, porque as cores permitem às vezes pular ou encurtar as ações de reequilíbrio que têm um custo relativamente alto. Por causa da coloração, a árvore RB também possui um nível mais alto de nós, pois pode aceitar nós vermelhos entre os pretos (com a possibilidade de ~ 2x mais níveis), tornando a pesquisa (leitura) um pouco menos eficiente ... mas porque é uma constante (2x), permanece em O (log n).

Se você considera o desempenho atingido para uma modificação de uma árvore (significativa) versus o desempenho atingido pela consulta de uma árvore (quase insignificante), torna-se natural preferir RB sobre AVL para um caso geral.

Eric Ouellet
fonte
2

É apenas a escolha da sua implementação - elas podem ser implementadas como qualquer árvore equilibrada. As várias opções são todas comparáveis ​​com pequenas diferenças. Portanto, qualquer um é tão bom quanto qualquer outro.

necromante
fonte