Por que não há classe Tree <T> no .NET?

A biblioteca de classes base em .NET tem algumas estruturas de dados excelentes para coleções (Lista, Fila, Pilha, Dicionário), mas estranhamente ela não contém nenhuma estrutura de dados para árvores binárias. Essa é uma estrutura extremamente útil para certos algoritmos, como aqueles que tiram proveito de diferentes caminhos de passagem. Estou procurando uma implementação gratuita escrita corretamente.

Estou simplesmente cego e não o encontro ... está enterrado algures no BCL? Se não, alguém pode recomendar uma biblioteca C # / .net gratuita ou de código aberto para árvores binárias? De preferência um que use genéricos.

EDIT: Para esclarecer o que estou procurando. Não estou interessado em coleções de dicionário ordenadas que usam internamente uma árvore. Na verdade, estou interessado em uma árvore binária - uma que expõe sua estrutura para que você possa fazer coisas como extrair subárvores ou realizar travessia pós-correção nos nós. Idealmente, essa classe poderia ser estendida para fornecer os comportamentos de árvores especializadas (ou seja, vermelho / preto, AVL, balanceado, etc).

Você está certo, não há nada no BCL. Suspeito que isso seja porque a escolha de usar uma árvore normalmente é um detalhe de implementação e, caso contrário, é uma forma não convencional de acessar dados. Ou seja, você não diz "binary-search-for element # 37"; em vez disso, você diz "pegue o elemento 37".

Mas você já deu uma olhada no C5 ? É muito prático e tem várias implementações de árvore ( 1 , 2 , 3 ).

Você pode definir o seu próprio:

public class MyTree<K, V> : Dictionary<K, MyTree<K, V>>
{
    public V Value { get; set; }
}

Ou sem chave:

public class MyTree<V> : HashSet<MyTree<V>>
{
    public V Value { get; set; }
}

O que você gostaria de tal implementação?

Árvore binária? Vermelho preto? Árvore Radix? Árvore B? R-tree? R * -tree?

Uma árvore é mais um padrão do que uma estrutura de dados, e eles tendem a ser usados ​​onde o desempenho é importante (portanto, os detalhes de implementação provavelmente também importam). Se o BCL incluiu algum tipo de classe de árvore, você só teria que lançar a sua própria de qualquer maneira

Acredito que, SortedDictionarycomo a inserção log (n), as características de recuperação que você esperaria de uma estrutura de dados em árvore.

http://msdn.microsoft.com/en-us/library/f7fta44c(VS.80).aspx

SortedSet<T>é implementado como uma árvore de pesquisa binária ^ref . SortedDictionary<TKey, TValue>faz uso interno de SortedSet<T>uma árvore de pesquisa binária ^ref .

Não, não existe nenhum Tree<T>tipo " parecido com" no BCL (algo que sempre me intrigou), mas aqui está um bom artigo que o ajudará a implementar o seu próprio tipo em C #.

Eu acho que você poderia argumentar que as estruturas de dados baseadas em árvore são menos comumente usadas no tipo de aplicativo para o qual o .NET é normalmente usado (aplicativos de negócios, aplicativos de movimentação de dados, etc.). Mesmo assim, concordo com você, é estranho que o BCL não tenha nenhuma implementação.

Esta série de artigos foi útil para mim quando tive que escrever o meu próprio, especialmente as partes 3 e 4.

Um Exame Extensivo de Estruturas de Dados

Há um TreeNode que você pode usar. Não é genérico e está escondido nos formulários do Windows e é usado com o controle de visualização em árvore, mas você também pode usá-lo em outro lugar.