Quando escolher a árvore RB, árvore B ou árvore AVL?

Como um programador, quando devo considerar o uso de uma árvore RB, árvore B ou uma árvore AVL? Quais são os pontos-chave que precisam ser considerados antes de decidir sobre a escolha?

Alguém pode explicar com um cenário para cada estrutura de árvore porque ela é escolhida em vez de outras com referência aos pontos-chave?

Tome isso com uma pitada de sal:

Árvore B quando você está gerenciando mais de milhares de itens e os pagina de um disco ou de algum meio de armazenamento lento.

Árvore RB quando você está fazendo inserções, exclusões e recuperações bastante frequentes na árvore.

Árvore AVL quando suas inserções e exclusões são infrequentes em relação às suas recuperações.

Acho que as árvores B + são uma boa estrutura de dados de contêiner ordenada de uso geral, mesmo na memória principal. Mesmo quando a memória virtual não é um problema, a compatibilidade com o cache geralmente é, e as árvores B + são particularmente boas para acesso sequencial - o mesmo desempenho assintótico de uma lista vinculada, mas com a compatibilidade com o cache próxima de um array simples. Tudo isso e O (log n) pesquisar, inserir e excluir.

Árvores B + têm problemas, entretanto - como os itens se movendo dentro dos nós quando você insere / deleta, invalidando ponteiros para esses itens. Eu tenho uma biblioteca de contêiner que faz a "manutenção do cursor" - os cursores se anexam ao nó folha que eles fazem referência atualmente em uma lista vinculada, para que possam ser corrigidos ou invalidados automaticamente. Como raramente há mais de um ou dois cursores, funciona bem - mas é um pouco mais de trabalho do mesmo jeito.

Outra coisa é que a árvore B + é essencialmente apenas isso. Eu acho que você pode remover ou recriar os nós não-folha dependendo se você precisa deles ou não, mas com nós de árvore binários você obtém muito mais flexibilidade. Uma árvore binária pode ser convertida em uma lista vinculada e vice-versa sem copiar os nós - basta alterar os ponteiros e lembrar que agora a trata como uma estrutura de dados diferente. Entre outras coisas, isso significa que você obtém uma fusão O (n) bastante fácil de árvores - converte ambas as árvores em listas, mescla-as e depois converte-as novamente em uma árvore.

Outra coisa é a alocação e liberação de memória. Em uma árvore binária, isso pode ser separado dos algoritmos - o usuário pode criar um nó e, em seguida, chamar o algoritmo de inserção, e as exclusões podem extrair nós (separá-los da árvore, mas não liberar a memória). Em uma árvore B ou B +, isso obviamente não funciona - os dados viverão em um nó de vários itens. Escrever métodos de inserção que "planejam" a operação sem modificar os nós até que saibam quantos novos nós são necessários e que podem ser alocados é um desafio.

Preto vermelho vs. AVL? Não tenho certeza se isso faz alguma diferença. Minha própria biblioteca tem uma classe de "ferramenta" baseada em políticas para manipular nós, com métodos para listas duplamente vinculadas, árvores binárias simples, árvores splay, árvores vermelhas e pretas e treaps, incluindo várias conversões. Alguns desses métodos só foram implementados porque eu estava entediado em um momento ou outro. Não tenho certeza se testei os métodos de treap. A razão pela qual escolhi árvores vermelhas e pretas em vez de AVL é porque eu pessoalmente entendo melhor os algoritmos - o que não significa que eles são mais simples, é apenas um acaso da história que estou mais familiarizado com eles.

Uma última coisa - originalmente desenvolvi meus contêineres de árvore B + como um experimento. É um daqueles experimentos que nunca terminam realmente, mas não é algo que encorajaria outros a repetir. Se tudo o que você precisa é um contêiner ordenado, a melhor resposta é usar aquele que sua biblioteca existente oferece - por exemplo, std :: map etc em C ++. Minha biblioteca evoluiu ao longo dos anos, demorou um pouco para torná-la estável e, recentemente, descobri que ela é tecnicamente não portátil (depende de um pouco de comportamento indefinido WRT offsetof).

Na memória, a B-Tree tem a vantagem quando o número de itens é superior a 32000 ... Veja speedtest.pdf de stx-btree .

Ao escolher as estruturas de dados, você está trocando fatores como

• velocidade de recuperação v velocidade de atualização
• quão bem a estrutura lida com as operações do pior caso, por exemplo, inserção de registros que chegam em uma ordem classificada
• espaço desperdiçado

Eu começaria lendo os artigos da Wikipedia referenciados por Robert Harvey.

Pragmaticamente, ao trabalhar em linguagens como Java, o programador médio tende a usar as classes de coleção fornecidas. Se, em uma atividade de ajuste de desempenho, alguém descobrir que o desempenho da coleção é problemático, pode-se buscar implementações alternativas. Raramente é a primeira coisa que um desenvolvimento liderado por negócios deve considerar. É extremamente raro que seja necessário implementar tais estruturas de dados manualmente, geralmente há bibliotecas que podem ser usadas.