Bạn sử dụng cấu trúc/thư viện java nào cho Tree

Tôi có một Hệ thống phân cấp khu vực (nghĩ rằng Nhà nước, Quận, Taluk, v.v.) mà tôi cần phải đại diện bằng cách sử dụng một cây. Tôi thấy một vài triển khai của một cây trong phạm vi công cộng NHƯNG không chắc chắn chúng tốt như thế nào và chúng được duy trì tốt như thế nào. Bộ sưu tập Apache không có một trong những NOR làm các bộ sưu tập google. Tôi tự hỏi liệu có ai trong số các bạn có thể chỉ cho tôi việc thực hiện một cây trong Java (với Generics) không.Bạn sử dụng cấu trúc/thư viện java nào cho Tree

Cảm ơn bạn,

Cập nhật Tôi đang tìm kiếm một datastructure Tree, tốt nhất là thực hiện sử dụng Generics: cũng được thử nghiệm.

Nguồn

2010-07-12 anjanb

Tôi cảm thấy cho bạn, không ai thực sự trả lời câu hỏi của bạn. –

Thực hiện một cây bằng cách sử dụng Generics là khá đơn giản, tại sao không cho nó một thử mình? Nếu bạn không thoải mái với Generics, bạn có thể thử khai báo một cây có chứa các phần tử thực hiện một giao diện, sau đó chỉ cần có tất cả các phần tử vùng khác nhau của bạn thực hiện giao diện đó.

Nguồn

2010-07-12 16:40:02 TMN

Tôi đã triển khai cây nhiều lần trong C/C++ từ lâu. Nếu có thứ gì đó tôi có thể tái sử dụng, tôi muốn sử dụng một cái gì đó đã được kiểm tra và kiểm tra thời gian! – anjanb

Cây cơ bản dễ thực hiện. Nhưng các cây nghiêm trọng đòi hỏi một số tái cân bằng (ví dụ như cây đỏ-đen.) Những người cần thời gian để có được quyền và hiệu quả. Ví dụ, từ những gì tôi nhớ, có 7 trường hợp quay khác nhau cho RB-cây. –

Nếu bạn cân bằng lại cây RB thì bạn quan tâm đến đặc tính sắp xếp của cây, không phải là phẩm chất cấu trúc (bố mẹ, con cái). Nếu đó là trường hợp, sau đó Java hoàn toàn có TreeSet mà thực hiện chính xác điều đó, kiểm tra các thư viện. Nếu bạn muốn có một "Cấu trúc cây" để theo dõi các mối quan hệ cha/con so với việc thực hiện là tầm thường và phản đối của bạn không có ý nghĩa. –

Bạn có nghĩa là Tiện ích cây hoặc cây có cấu trúc dữ liệu không? Nếu bạn đang nói về một widget cây, thì Swing có một sự thực thi.

JTree

Nguồn

2010-07-12 16:41:11 Roman

cảm ơn. Tôi có nghĩa là một cơ sở hạ tầng cây. – anjanb

Những gì bạn đang mô tả là nhiều hơn nữa như một Document Object Model (DOM). Thông thường khi mọi người đề cập đến cấu trúc dữ liệu "Cây", họ đang nói về cây nhị phân cân bằng (giống như cây đỏ đen, chắc chắn tồn tại trong thư viện bộ sưu tập Java). Nhưng những loại cây này chỉ dành cho việc chèn và tra cứu nhanh. Tuy nhiên, phần lớn thời gian, khi mọi người sử dụng DOM, họ đang đọc hoặc viết XML, nhưng không có lý do gì bạn không thể sử dụng DOM cho dữ liệu phân cấp tùy ý của riêng bạn. Thậm chí nếu bạn không bao giờ tồn tại nó với XML.

Nguồn

2010-07-12 16:46:28 benjismith

DOM. DOM đắt bao nhiêu khi bạn KHÔNG sử dụng nó cho XML? – anjanb

Tôi không thực sự biết, nhưng tôi có thể suy đoán về một vài điều ...Lý do DOM được coi là một kỹ thuật phân tích cú pháp XML tốn kém là bạn phải phân tích cú pháp toàn bộ tệp XML và giữ nó trong bộ nhớ, thay vì quét qua XML và kích hoạt các sự kiện SAX. Nhưng trong trường hợp của bạn, bạn cần toàn bộ tài liệu trong bộ nhớ dù sao đi nữa, vì vậy tôi sẽ không nghĩ rằng việc triển khai DOM sẽ đắt hơn nhiều so với bất kỳ cấu trúc dữ liệu tùy chỉnh nào mà bạn có thể tự cuộn. (Và tất nhiên, bạn sẽ không phải trả chi phí I/O.) Sau đó, một lần nữa, bạn sẽ phải sống với ngữ nghĩa cụ thể của XML trong mô hình cây của riêng bạn. – benjismith

Có điều gì đó như thế này http://www.java-tips.org/java-se-tips/java.lang/red-black-tree-implementation-in-java.html hoạt động không?

Ngoài ra, cách bắt đầu với nguồn java.util.TreeMap từ OpenJDK? http://download.java.net/openjdk/jdk7/

Nguồn

2010-07-12 22:20:00

Những triển khai này dành cho cây nhị phân. Mỗi tiểu bang chỉ có thể có hai quận và mỗi huyện chỉ có hai taluk? Nếu có, thì những thứ đó có thể hiệu quả. Nếu bạn cần phải chứa nhiều hơn hai trường hợp của mỗi cấp trong hệ thống phân cấp, mặc dù (và tôi đoán bạn làm), sau đó bạn sẽ muốn cuộn của riêng bạn. Tôi đã làm điều này một vài tuần trước cho một số phân tích cú pháp XML tôi đã làm, và nó chỉ mất cho tôi một vài giờ để làm cho nó được thiết kế, thử nghiệm, viết và tài liệu. Tôi không thể chia sẻ mã (nó trong C# anyway), nhưng tôi có thể chia sẻ các thiết kế nếu bạn không muốn làm việc lên một cái gì đó của riêng bạn. – TMN

Đây là ví dụ về cây RB bật lên đầu tiên trong google nếu bạn tìm kiếm thực thi Java của cây RB. Nhưng không có kiểm tra đơn vị vv, và nó không đầy đủ: hoạt động loại bỏ không được thực hiện, và tôi có thể thấy lý do tại sao (do độ phức tạp của nó đối với cây RB). –

Khám phá DefaultMutableTreeNode. Nó không phải là chung chung, nhưng nếu không có vẻ phù hợp với hóa đơn. Mặc dù nó nằm trong gói javax.swing, nó không phụ thuộc vào bất kỳ lớp AWT hoặc Swing nào. Trên thực tế, mã nguồn thực sự có nhận xét // ISSUE: this class depends on nothing in AWT -- move to java.util?

Nguồn

2010-10-14 12:25:28 Mark

Bạn sử dụng cấu trúc/thư viện java nào cho Tree

Trả lời

Các vấn đề liên quan