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

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

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

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

8 51
c# .net binary-tree

8 ответов:

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

С эта статья CodeProject:

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

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

46

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

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

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

18

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

класс называется a 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
7

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

6

ответ: Нет.

есть в наличии, хотя реализации. Взгляните на следующую ссылку:

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

3

библиотека коллекций C5 (см. http://www.itu.dk/research/c5/) включает TreeDictionary<> классы со сбалансированными красно-черными бинарными деревьями. Примечание: Я еще не использовал эту библиотеку, так как работа, которую я делаю, не требует ничего больше, чем стандартные коллекции .NET.

3

Я не уверен, что именно Вы имеете в виду с "дерево", но вы можете сделать двоичный поиск в классе списка.

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 );
2

спасибо 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();
        }
    }
}
2