6
Tôi đang tìm một cấu trúc dữ liệu tốt để xây dựng các lớp tương đương trên các nút của cây. Trong một cấu trúc lý tưởng, các hoạt động sau phải nhanh (O (1)/O (n) khi thích hợp) và dễ dàng (không có đoạn mã bí ẩn):Cấu trúc dữ liệu tốt để xây dựng các lớp tương đương trên các nút của cây là gì?
- (A) Đi bộ từ gốc; trên mỗi nút -> chuyển đổi con liệt kê tất cả các phiên bản tương đương của nút con
- (B) Hợp nhất hai lớp tương đương
- (C) Tạo nút mới từ danh sách các nút hiện có (trẻ em) và các dữ liệu khác
- (D) Tìm bất kỳ nút nào có cấu trúc tương đương với nút (nghĩa là chúng có cùng số lượng con, con tương ứng thuộc cùng một lớp tương đương, và "dữ liệu khác" của chúng bằng nhau) để các nút mới (hoặc mới được sửa đổi) có thể được đưa vào lớp tương đương phù hợp (thông qua hợp nhất)
Cho đến nay tôi đã xem xét (một số có thể được sử dụng kết hợp):
- Một parfait, nơi trẻ em tham chiếu đến bộ sưu tập các nút thay vì các nút. (A) là nhanh, (B) yêu cầu đi bộ cây và cập nhật các nút để trỏ đến bộ sưu tập đã hợp nhất, (C) yêu cầu tìm bộ sưu tập chứa mỗi con của nút mới, (D) yêu cầu đi bộ cây
- Duy trì một băm của các nút theo đặc điểm của chúng. Điều này làm cho (D) nhanh hơn nhiều nhưng (B) chậm hơn (vì băm sẽ phải được cập nhật khi các lớp tương đương được sáp nhập)
- Ghép các nút lại với nhau thành một danh sách liên kết vòng tròn. (A) là nhanh, (B) sẽ được nhanh chóng, nhưng thực tế là "sáp nhập" một phần của một danh sách tròn với chính nó thực sự chia danh sách (C) sẽ được nhanh chóng, (D) sẽ yêu cầu đi bộ cây
- Giống như ở trên, nhưng với một con trỏ "lên" bổ sung trong mỗi nút, có thể được sử dụng để tìm một thành viên kinh điển của danh sách vòng tròn.
Tôi có thiếu lựa chọn ngọt ngào không?
Thẻ phải là thuật toán chứ không phải thuật toán. – ashawley