¿Hay un árbol de búsqueda binaria incorporado en .NET 4.0?

Question

¿Hay un árbol de búsqueda binaria incorporado en .NET 4.0, o necesito crear este tipo de datos abstractos desde cero?

Editar

Esto es sobre el árbol de búsqueda binaria específica, y no "árboles" Resumen de tipos de datos en general.

Answer 1

Creo que la clase SortedSet<T> en System.Collections.Generic es lo que estás buscando.

De this CodeProject article:

Se lleva a cabo usando un árbol rojo-negro auto-equilibrio que da una complejidad desempeño de O (log n) para insertar, eliminar y buscar. Se utiliza para mantener los elementos en forma ordenada, para obtener el subconjunto de elementos en un rango particular , o para obtener la Min Max o elemento del conjunto.

El código fuente https://github.com/dotnet/corefx/blob/master/src/System.Collections/src/System/Collections/Generic/SortedSet.cs

Answer 2

No estoy seguro de qué quiere decir exactamente con 'árbol', pero puede hacer búsquedas binarias en la clase List.

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 respuesta es: No.

Existen implementaciones disponibles sin embargo. Echar un vistazo al siguiente enlace:

Binary Tree in C#

Answer 4

La biblioteca de colecciones C5 (ver http://www.itu.dk/research/c5/) incluye TreeDictionary<> clases con los árboles binarios de color rojo-negro equilibradas. Nota: Todavía no he usado esta biblioteca, ya que el trabajo que hago no necesita nada más que las colecciones .NET estándar.

Answer 5

Gracias a herzmeister der welten, ahora sé que hay! ¡Lo intenté y realmente funcionó!

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# equilibrada árbol binario AVL se puede encontrar @http://code.google.com/p/self-balancing-avl-tree/ .it también implementa concatenar logarítmica y las operaciones de división

Answer 7

No, .NET no contiene un Binary Search Tree. Contiene un Red-Black Tree que es un tipo especializado de árbol de búsqueda binaria en el que cada nodo está pintado de rojo o negro y hay ciertas reglas que utilizan estos colores que mantienen el árbol equilibrado y permite al árbol garantizar O (logn) tiempos de búsqueda . Un árbol de búsqueda binaria estándar no puede garantizar estos tiempos de búsqueda.

La clase se llama SortedSet<T> y se introdujo en .NET 4.0. Puedes ver su código fuente here.Aquí está un ejemplo de su 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

Cinco años después hice la pregunta me di cuenta de que efectivamente existe una construida en búsqueda binaria Árbol en .NET 4.0. Probablemente se agregó más adelante y funciona como se esperaba. Se autoequilibra (atraviesa) después de cada inserción, lo que disminuye el rendimiento al agregar una gran variedad de elementos.

La Clase SortedDictionary<TKey, TValue> tiene las siguientes observaciones:

La clase genérica SortedDictionary es un árbol binario de búsqueda con O (log n) de recuperación, donde n es el número de elementos en el diccionario. A este respecto, es similar a la clase genérica SortedList. Las dos clases tienen modelos de objetos similares, y ambos tienen recuperación O (log n).