C'è un albero di ricerca binario integrato in .NET 4.0?

Question

C'è un albero di ricerca binario integrato in. NET 4.0, o devo creare questo tipo di dati astratto da zero?

Modifica

Questo è circa l'albero binario di ricerca specifico, e non astratta dei tipi di dati "alberi" in generale.

Answer 1

Penso che la classe SortedSet<T> in System.Collections.Generic sia ciò che stai cercando.

Da this CodeProject article:

E 'implementato utilizzando un auto-bilanciamento rosso-nero albero che dà una complessità prestazioni di O (log n) per inserire, eliminare, e consultare. E 'utilizzato per mantenere i elementi in modo ordinato, per ottenere il sottoinsieme di elementi in un particolare gamma, oppure per ottenere il Min o Max elemento dell'insieme.

codice sorgente https://github.com/dotnet/corefx/blob/master/src/System.Collections/src/System/Collections/Generic/SortedSet.cs

Answer 2

Non sono sicuro di cosa si intenda esattamente con "albero", ma è possibile eseguire ricerche binarie nella classe Elenco.

public int BinarySearch(T item); 
public int BinarySearch(T item, IComparer<T> comparer); 
public int BinarySearch(int index, int count, T item, IComparer<T> comparer); 

Answer 3

La risposta è: No.

Ci sono implementazioni disponibili però. Date un'occhiata al seguente link:

Binary Tree in C#

Answer 4

La biblioteca collezioni C5 (vedi http://www.itu.dk/research/c5/) include TreeDictionary<> classi con alberi binari rosso-neri equilibrati. Nota: non ho ancora usato questa libreria, poiché il lavoro che faccio non ha bisogno di più delle collezioni .NET standard.

Answer 5

Grazie a herzmeister der Welten, io ora so che ci sono! L'ho provato e ha funzionato davvero!

namespace Tree 
{ 
    public partial class Form1 : Form 
    { 
     private SortedSet<int> binTree = new SortedSet<int>(); 

     public Form1() 
     { 
      InitializeComponent(); 
     } 

     private void Insert(int no) 
     { 
      binTree.Add(no); 
     } 

     private void Print() 
     { 
      foreach (int i in binTree) 
      { 
       Console.WriteLine("\t{0}", i); 
      } 
     } 

     private void btnAdd_Click(object sender, EventArgs e) 
     { 
      Insert(Int32.Parse(tbxValue.Text)); 
      tbxValue.Text = ""; 
     } 

     private void btnPrint_Click(object sender, EventArgs e) 
     { 
      Print(); 
     } 
    } 
} 

Answer 6

un C# equilibrata AVL albero binario può essere trovato @http://code.google.com/p/self-balancing-avl-tree/ .it implementa anche concatenare logaritmica e le operazioni di dividere

Answer 7

No, NET non contiene un Binary Search Tree. Contiene un Red-Black Tree che è un tipo specializzato di albero di ricerca binaria in cui ogni nodo è dipinto in rosso o nero e ci sono alcune regole che usano questi colori che mantengono l'albero bilanciato e consente all'albero di garantire i tempi di ricerca O (logn) . Un albero di ricerca binaria standard non può garantire questi tempi di ricerca.

La classe è denominata SortedSet<T> ed è stata introdotta in .NET 4.0. Puoi guardare il suo codice sorgente here.Ecco un esempio di esso è uso:

// Created sorted set of strings. 
var set = new SortedSet<string>(); 

// Add three elements. 
set.Add("net"); 
set.Add("net"); // Duplicate elements are ignored. 
set.Add("dot"); 
set.Add("rehan"); 

// Remove an element. 
set.Remove("rehan"); 

// Print elements in set. 
foreach (var value in set) 
{ 
    Console.WriteLine(value); 
} 

// Output is in alphabetical order: 
// dot 
// net 

Answer 8

Cinque anni dopo ho chiesto la domanda che mi sono reso conto che c'è davvero un costruito in Binary Search Tree in .NET 4.0. Probabilmente è stato aggiunto in seguito e funziona come previsto. Si autostabilancia (attraversa) dopo ogni inserimento che riduce le prestazioni all'aggiunta di una vasta gamma di articoli.

La classe SortedDictionary<TKey, TValue> ha le seguenti osservazioni:

La classe generica SortedDictionary è un albero binario di ricerca con O (log n) di recupero, dove n è il numero di elementi nel dizionario. In questo senso, è simile alla classe generica SortedList. Le due classi hanno modelli di oggetti simili ed entrambi hanno il recupero di O (log n).