Есть ли в .NET 4.0 встроенное дерево бинарного поиска?

Question

Есть ли в .NET 4.0 встроенное дерево двоичного поиска или мне нужно создать этот абстрактный тип данных с нуля?

Редактировать

Это касается дерева двоичного поискав частности, а не абстрактный тип данных "деревья" в целом.

Answer 1

Я думаю, класс SortedSet<T> в System.Collections.Generic - это то, что вы ищете.

Из этой статьи CodeProject :

Это реализовано с использованием Самобалансирующееся красно-черное дерево дает сложность исполнения O (log n) для вставки, удаления и уважать. Он используется для сохранения элементы в отсортированном порядке, чтобы получить подмножество элементов в конкретном диапазон, или получить Мин или Макс элемент множества.

Исходный код https://github.com/dotnet/corefx/blob/master/src/System.Collections/src/System/Collections/Generic/SortedSet.cs

Answer 2

Через пять лет после того, как я задал вопрос, я понял, что в .NET 4.0 действительно есть встроенное дерево двоичного поиска. Возможно, он был добавлен позже и работает, как и ожидалось. Он автоматически балансирует (обходит) после каждой вставки, что снижает производительность при добавлении большого диапазона элементов.

Класс SortedDictionary<TKey, TValue> имеет следующие замечания:

Универсальный класс SortedDictionary представляет собой двоичное дерево поиска с поиском O (log n), где n - количество элементов в словаре. В этом отношении он похож на универсальный класс SortedList. Два класса имеют похожие объектные модели, и оба имеют O (log n) извлечения.

Answer 3

Нет, .NET не содержит Двоичное дерево поиска .Он содержит Красно-черное дерево , которое является специализированным видом дерева двоичного поиска, в котором каждый узел окрашен в красный или черный цвет, и существуют определенные правила, использующие эти цвета, которые поддерживают дерево сбалансированным и позволяют деревугарантия O (logn) время поиска.Стандартное двоичное дерево поиска не может гарантировать это время поиска.

Класс называется SortedSet<T> и был представлен в .NET 4.0.Вы можете посмотреть его исходный код здесь .Вот пример его использования:

// 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 4

можно найти сбалансированное двоичное дерево AVL в C # @ http://code.google.com/p/self-balancing-avl-tree/. В нем также реализованы логарифмические операции конкатенации и разделения

Answer 5

Библиотека коллекций C5 (см. http://www.itu.dk/research/c5/) включает в себя TreeDictionary<> классы с сбалансированными красно-черными двоичными деревьями. Примечание. Чистые коллекции.

Answer 6

Ответ: Нет.

Хотя есть доступные реализации. Взгляните на следующую ссылку:

Двоичное дерево в C #

Answer 7

Спасибо herzmeister der welten , теперь я знаю, что есть!Я попробовал, и это действительно сработало!

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 8

Я не уверен, что именно вы имеете в виду под «деревом», но вы можете выполнять бинарный поиск в классе 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 );