Mengapa tidak ada kelas Pohon <T> di .NET?

89

Pustaka kelas dasar di .NET memiliki beberapa struktur data yang sangat baik untuk koleksi (Daftar, Antrean, Tumpukan, Kamus), tetapi anehnya tidak berisi struktur data apa pun untuk pohon biner. Ini adalah struktur yang sangat berguna untuk algoritme tertentu, seperti algoritme yang memanfaatkan jalur traversal yang berbeda. Saya mencari implementasi gratis yang ditulis dengan benar.

Apakah saya hanya buta, dan tidak menemukannya ... apakah itu terkubur di suatu tempat di BCL? Jika tidak, dapatkah seseorang merekomendasikan pustaka C # / .NET gratis atau sumber terbuka untuk pohon biner? Lebih disukai yang menggunakan obat generik.

EDIT: Untuk memperjelas apa yang saya cari. Saya tidak tertarik dengan koleksi kamus yang dipesan secara internal menggunakan pohon. Saya sebenarnya tertarik dengan pohon biner - yang memperlihatkan strukturnya sehingga Anda dapat melakukan hal-hal seperti mengekstrak subpohon, atau melakukan traversal pasca-perbaikan pada node. Idealnya kelas seperti itu dapat diperluas untuk menyediakan perilaku pohon khusus (mis. Merah / Hitam, AVL, Seimbang, dll).

c# .net data-structures LBushkin
sumber
Sepakat. Saya kadang-kadang memiliki kebutuhan untuk menemukan (dalam waktu O (Log N)) dua node yang mengikat nilai (ketika nilai tidak ditemukan dalam koleksi). Misalnya kumpulan (pohon) berisi 13 dan 17 (antara lain) dan saya mencari yang terbesar kurang dari dan paling tidak lebih besar dari 16. Pohon bisa melakukan ini, tetapi Kamus, daftar yang diurutkan, dan tabel hash mengambil O (N) .
Les

Jawaban:

31

Anda benar, tidak ada apa-apa di BCL. Saya menduga ini karena pilihan apakah akan menggunakan pohon biasanya merupakan detail implementasi dan sebaliknya merupakan cara yang tidak konvensional untuk mengakses data. Artinya, Anda tidak mengatakan, "binary-search-for element # 37"; sebagai gantinya, Anda berkata, "berikan aku elemen # 37".

Tapi apakah Anda sudah melihat C5 ? Ini sangat berguna dan mereka memiliki beberapa implementasi pohon ( 1 , 2 , 3 ).

John Feminella
sumber
3
C5 mendukung pohon Merah Hitam bukan B-Tree. Itu adalah perbedaan yang harus disadari orang. B-Tree lebih optimal untuk pohon berbasis disk atau pohon berbasis memori besar. Lebih banyak node disimpan di lokasi yang sama sehingga Anda mendapatkan kinerja cache prosesor yang lebih baik dan lebih cepat membaca tulis ke disk.
AnthonyLambert
69

Anda bisa menentukan sendiri:

public class MyTree<K, V> : Dictionary<K, MyTree<K, V>>
{
    public V Value { get; set; }
}

Atau tidak terkunci:

public class MyTree<V> : HashSet<MyTree<V>>
{
    public V Value { get; set; }
}
Jason
sumber
Namun ini mengharuskan Anda untuk mengetahui berapa banyak level pohon yang akan Anda tangani pada waktu kompilasi, apakah saya salah?
Veverke
1
Tidak, kompilator C # mendukung sintaks ini.
Jason
3
Berhati-hatilah bahwa elemen tidak tertata dengan cara ini
Sebastian
@Veverke Mungkin Anda berpikir tentang template C ++. .NET generik adalah jenis runtime.
Tom Blodget
Saya penasaran. Bagaimana Anda menggunakan ini? Praktis? Ada sampel?
Syaiful Nizam Yahya
39

Apa yang Anda inginkan dari penerapan seperti itu?

Pohon biner? Merah hitam? Pohon radix? B-tree? R-pohon? R * -pohon?

Pohon lebih merupakan pola daripada struktur data, dan mereka cenderung digunakan jika kinerja penting (jadi detail implementasi mungkin juga penting). Jika BCL menyertakan semacam kelas pohon, Anda hanya perlu menggulungnya sendiri

Alun Harford
sumber
1
Jawaban terbaik untuk bagian "mengapa" dari pertanyaan itu.
Joel Coehoorn
Dan itu hanya pohon pencarian. Ada juga pohon ekspresi, pohon keputusan, ...
Henk Holterman
Memang, detail implementasi itu penting. Dalam kasus saya, saya ingin menerapkan beberapa algoritme yang akan melakukan traversal berbeda (infix, postfix) pada kumpulan data yang terorganisir sebagai bagian dari rangkaian transformasi. Struktur pohon adalah cara paling elegan untuk memecahkan masalah saya.
LBushkin
12
Di alam semesta paralel seseorang mengajukan pertanyaan: "Mengapa tidak ada jenis daftar dalam .Net?", Dan mereka mendapatkan jawaban: "Apa yang Anda inginkan dari implementasi seperti itu? Array? Daftar tertaut? Antrean? A kamus?" Saya pikir ini adalah jawaban non sequitur.
rymdsmurf
12

SortedSet<T>diimplementasikan sebagai pohon pencarian biner ref . SortedDictionary<TKey, TValue>secara internal memanfaatkan SortedSet<T>jadi itu juga merupakan pohon pencarian biner ref .

Matt Brunell
sumber
5
Sayangnya ini hanyalah implementasi dari peta dan daftar yang diurutkan. Tidak ada yang berguna untuk digunakan kembali sebagai pohon biner - struktur pohon ini hanyalah sebuah detail implementasi dari koleksi. Saya sebenarnya mencari kelas yang mengekspos struktur pohon.
LBushkin
9

Tidak, tidak ada Tree<T>tipe "-like" di BCL (sesuatu yang selalu membuat saya bingung juga) tapi berikut adalah artikel bagus yang akan memandu Anda melalui penerapan Anda sendiri di C #.

Saya kira Anda dapat membuat argumen bahwa struktur data berbasis pohon kurang umum digunakan dalam jenis aplikasi yang biasanya digunakan .NET (aplikasi bisnis, aplikasi pemindahan data, dll.). Tetap saja, saya setuju dengan Anda, aneh bahwa BCL tidak memiliki implementasi sama sekali.

Andrew Hare
sumber
-5

Ada TreeNode yang dapat Anda gunakan. Ini tidak umum dan tersembunyi dalam bentuk windows dan digunakan dengan kontrol treeview, tetapi Anda juga dapat menggunakannya di tempat lain.

Joel Coehoorn
sumber
Ya, tapi itu hanya memiliki properti Tag dari System.Object ype. Tidak ada parameter <T> Generik
Henk Holterman
3
Saya selalu merasa aneh melakukan hal seperti itu. Ini kurang terlihat dengan contoh spesifik Anda, tetapi jika orang secara rutin mengubah tujuan kelas dari, katakanlah, dependensi, ini dapat mengakibatkan ketergantungan yang sulit dijelaskan dan dapat membuat Anda mendapat masalah jika kelas yang diubah tujuannya berubah dengan cara yang tidak terduga. versi ketergantungan.
Paul Morie
4
Apa untungnya menggunakannya? Node pohon biasanya tidak memiliki fungsionalitas yang relevan di dalamnya. Itu hanya menyimpan referensi ke anak dan akhirnya orang tua. Tidak ada alasan untuk menyalahgunakan kelas System.Windows.Forms untuk itu! Tulis saja sendiri - dalam satu menit atau kurang.
pengguna492238