Tại sao không có lớp Tree <T> trong .NET?

Question

Thư viện lớp cơ sở trong .NET có một số cấu trúc dữ liệu tuyệt vời cho các bộ sưu tập (Danh sách, Hàng đợi, Ngăn xếp, Từ điển), nhưng đủ kỳ quặc nó không chứa bất kỳ cấu trúc dữ liệu nào cho cây nhị phân. Đây là một cấu trúc hữu ích khủng khiếp cho các thuật toán nhất định, chẳng hạn như các thuật toán tận dụng các đường dẫn truyền tải khác nhau. Tôi đang tìm một cách thực hiện miễn phí, được viết chính xác.

Tôi chỉ đơn giản là mù, và không tìm thấy nó ... là nó chôn cất ở đâu đó trong BCL? Nếu không, ai đó có thể giới thiệu một thư viện C# /. NET mã nguồn mở hoặc miễn phí cho cây nhị phân không? Tốt nhất là sử dụng Generics.

EDIT: Để làm rõ những gì tôi đang tìm kiếm. Tôi không quan tâm đến các bộ sưu tập từ điển theo thứ tự mà nội bộ sử dụng một cái cây. Tôi thực sự quan tâm đến một cây nhị phân - một cái để lộ cấu trúc của nó để bạn có thể làm những việc như trích xuất các subtrees, hoặc thực hiện các bước sau sửa lỗi trên các nút. Lý tưởng như vậy một lớp học có thể được mở rộng để cung cấp các hành vi của cây đặc biệt (ví dụ: Red/Black, AVL, Balanced, vv).

Answer 1

Bạn nói đúng, không có gì trong BCL. Tôi nghi ngờ điều này là bởi vì việc chọn sử dụng một cây thường là một chi tiết thực hiện và nếu không một cách độc đáo để truy cập dữ liệu. Tức là, bạn không nói, "phần tử tìm kiếm nhị phân # 37"; thay vào đó, bạn nói, "lấy cho tôi nguyên tố # 37".

Nhưng bạn đã xem C5 chưa? Đó là siêu tiện dụng và họ có một số triển khai cây (1, 2, 3).

Answer 2

Không, không có bất kỳ loại nào "Tree<T>" giống như trong BCL (điều gì đó luôn làm tôi bối rối) nhưng here is a good article sẽ hướng dẫn bạn thực hiện của riêng bạn trong C#.

Tôi đoán bạn có thể làm cho lập luận rằng cấu trúc dữ liệu dựa trên cây thường ít được sử dụng trong các loại ứng dụng .NET thường được sử dụng cho (ứng dụng kinh doanh, ứng dụng di chuyển dữ liệu, v.v.). Tuy nhiên, tôi đồng ý với bạn, thật lạ lùng là BCL không có triển khai gì cả.

Answer 3

Có một số TreeNode bạn có thể sử dụng. Nó không phải là chung chung và ẩn đi trong các hình thức cửa sổ và được sử dụng với các kiểm soát treeview, nhưng bạn có thể sử dụng nó ở nơi khác là tốt.

Answer 4

Tôi tin rằng SortedDictionary là bản ghi chèn (n), các đặc tính truy xuất mà bạn mong đợi từ Cơ cấu dữ liệu cây.

http://msdn.microsoft.com/en-us/library/f7fta44c(VS.80).aspx

Answer 5

SortedSet<T> được thực hiện như một cây tìm kiếm nhị phân ^ref. SortedDictionary<TKey, TValue> nội bộ sử dụng số SortedSet<T> để nó cũng là cây tìm kiếm nhị phân ^ref.

Answer 6

Bạn muốn thực hiện điều gì như vậy?

Cây nhị phân? Đỏ đen? Cây Radix? B-tree? R-tree? R * -tree?

Cây có nhiều mẫu hơn cấu trúc dữ liệu và chúng có xu hướng được sử dụng ở nơi hiệu suất quan trọng (vì vậy chi tiết triển khai cũng có thể quan trọng). Nếu BCL bao gồm một số loại của một lớp cây, bạn chỉ sẽ phải cuộn của riêng bạn anyway

Answer 7

Bạn có thể định nghĩa của riêng bạn:

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

Hoặc unkeyed:

public class MyTree<V> : HashSet<MyTree<V>> 
{ 
    public V Value { get; set; } 
} 

Answer 8

Loạt bài này các bài viết rất hữu ích cho tôi khi tôi phải viết riêng của tôi, đặc biệt là phần 3 và 4.

An Extensive Examination of Data Structures