.NET 4.0에 기본 제공 이진 검색 트리가 있습니까?

.NET 4.0에 기본 제공 이진 검색 트리가 있습니까?

---

.NET 4.0에 기본 제공 이진 검색 트리가 있습니까? 아니면이 추상 데이터 형식을 처음부터 작성해야합니까?

편집하다

이것은 이진 검색 트리에 관한 것이며 일반적으로 추상 데이터 유형 "트리"가 아닙니다.

---

나는 생각 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

---

질문을 한 지 5 년이 지난 후 저는 .NET 4.0에 실제로 내장 된 이진 검색 트리가 있다는 것을 깨달았습니다. 나중에 추가되었으며 예상대로 작동합니다. 각 삽입 후 자체 균형을 유지 (이동)하여 광범위한 항목을 추가 할 때 성능을 저하시킵니다.

SortedDictionary<TKey, TValue>클래스는 다음과 같은 발언이 있습니다 :

SortedDictionary 일반 클래스는 O (log n) 검색이 포함 된 이진 검색 트리입니다. 여기서 n은 사전의 요소 수입니다. 이 점에서 SortedList 제네릭 클래스와 유사합니다. 두 클래스는 유사한 객체 모델을 가지고 있으며 둘 다 O (log n) 검색을 가지고 있습니다.

---

C # 균형 AVL 이진 트리는 http://code.google.com/p/self-balancing-avl-tree/ 에서 찾을 수 있습니다. 또한 로그 연결 및 분할 작업을 구현합니다.

---

아니요, .NET에는 이진 검색 트리가 포함되어 있지 않습니다 . 여기에는 각 노드가 빨간색 또는 검은 색으로 칠해진 특수한 종류의 이진 검색 트리 인 Red-Black Tree 가 포함되어 있으며 이러한 색상을 사용하여 트리의 균형을 유지하고 트리가 O (로그) 검색 을 보장 할 수 있도록하는 특정 규칙이 있습니다. 타임스. 표준 이진 검색 트리는 이러한 검색 시간을 보장 할 수 없습니다.

이 클래스는 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

---

C5 컬렉션 라이브러리 ( http://www.itu.dk/research/c5/ 참조 )에는 TreeDictionary<>균형 잡힌 레드-블랙 바이너리 트리가있는 클래스가 포함되어 있습니다. 참고 :이 라이브러리를 아직 사용하지 않았습니다. 내가하는 작업에는 표준 .NET 컬렉션 이상이 필요하지 않습니다.

---

대답은 '아니오.

그래도 사용 가능한 구현이 있습니다. 다음 링크를 살펴보십시오.

C #의 이진 트리

---

'트리'가 정확히 무엇을 의미하는지 잘 모르겠지만 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 );

---

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();
        }
    }
}

참고 URL : https://stackoverflow.com/questions/3262947/is-there-a-built-in-binary-search-tree-in-net-4-0