O que é um bom e C ++ implementação de árvore estável?

Question

Eu estou querendo saber se alguém pode recomendar um bom C ++ implementação de árvore, espero que aquele que é STL compatível, se possível.

Para o registro, eu escrevi algoritmos de árvores muitas vezes antes, e eu sei que isso pode ser divertido, mas eu quero ser pragmática e preguiçoso, se possível. Assim, uma ligação efectiva a uma solução de trabalho é o objetivo aqui.

Nota: Eu estou olhando para uma árvore genérica, não uma árvore equilibrada ou um mapa / set, a própria estrutura ea conectividade da árvore é importante neste caso, não só os dados dentro. Então cada ramo tem de ser capaz de segurar quantidades arbitrárias de dados, e cada ramo deve ser separado iterateable.

Answer 1

Eu não sei sobre suas necessidades, mas você não seria melhor fora com um gráfico (implementações por exemplo, Impulsione Graph ) Se você está interessado principalmente na estrutura e não tanto em benefícios específicos-árvore como a velocidade por meio de balanceamento? Você pode 'emular' uma árvore através de um gráfico, e talvez ele vai ser (conceitualmente) mais perto do que você está procurando.

Answer 2

Dê uma olhada este .

A biblioteca tree.hh para C ++ fornece um STL-classe como recipiente para enários árvores, modeladas sobre os dados armazenados nos nodos. Vários tipos de iterators são fornecidos (pós-fim, pré-fim, e outros). Sempre que possível os métodos de acesso são compatíveis com os STL ou alternativos algoritmos estão disponíveis.

HTH

Answer 3

Vou sugerir o uso de std :: map em vez de uma árvore.

As características de complexidade de uma árvore são:

Inserir: O (ln (n))
Remoção: O (ln (n))
Encontrar: O (ln (n))

Estas são as mesmas características dos std :: mapa garantias.
Assim como resultado a maioria das implementações de std :: mapa de uso de uma árvore (Vermelho-Preto Tree) embaixo das cobertas (embora tecnicamente isso não é necessário).

Answer 4

folks Ok, eu encontrei outra biblioteca árvore; stlplus.ntree . Mas não tentei ainda.

Answer 5

Se você não tem (chave, valor) pares, mas simplesmente chaves, usar std :: set. Que usa a mesma árvore Vermelho-Preto como std :: map.

Answer 6

Vamos supor que a pergunta é sobre equilibrada (de alguma forma, árvore preta principalmente vermelho) árvores binárias, mesmo que não é o caso.

árvores binários equilibrado, como vector, permitem gerir alguns ordenação dos elementos, sem necessidade de chave (como através da inserção de elementos em qualquer lugar no vetor), mas:

• Com óptima O (log (n)), ou melhor a complexidade para toda a modificação de um elemento (adicionar / remover no início, fim e antes e após qualquer iterador)
• com persistência de iteradores através de qualquer modificação, exceto destruição direta do elemento apontado pelo iterador.

Opcionalmente, pode-se apoiar o acesso de índice, como no vector (com um custo de uma size_t por elemento), com O (log (n)) a complexidade. Se for utilizado, iterators será aleatória.

ordem Opcionalmente pode ser aplicada por alguns func comparação, mas a persistência de iteradores permitem utilizar esquema de comparação repetível não (ex: pistas de carro arbitrárias mudar durante engarrafamento).

Na prática, árvore binária balanceada têm de interface de vetor, lista, lista de duplo ligado, mapa, multimap, deque, fila, priority_queue ... com a realização teórica óptima O (log (n)) complexidade para todas as operações de um único elemento.

este é provavelmente por isso que c stl ++ não propõe it

Os indivíduos não podem implementar árvore geral balanceada por si só, devido às dificuldades para obter correta gestão de equilibrar, especialmente durante a extração elemento.

Não existe amplamente disponíveis implementação de árvore binária equilibrada porque o estado da arte árvore rubro-negra (neste momento o melhor tipo de árvore equilibrada devido ao número fixo de reorganizações árvores caros durante remove) sabe implementação, servilmente copiado por todos os implementadores a partir do código inicial do inventor estrutura, não permite iteração persistência. É provavelmente a razão da ausência de modelo de árvore totalmente functionnal.