Có tên cho bộ sưu tập cấu trúc dữ liệu mảng được sắp xếp này không?

Question

Có tên cho cấu trúc dữ liệu sau không? Có giấy tờ và trích dẫn nào không?

Một cách to implement một hiệu quả bộ trừu tượng dữ liệu loại là phải có một bộ sưu tập của mảng được sắp xếp, trong đó mỗi mảng có một độc đáo power-of-2 kích thước.

Ví dụ: một tập hợp gồm 13 phần tử {1, 2, ..., 13} có thể được biểu diễn bằng tập hợp các mảng được sắp xếp này: {[5], [2, 3, 9, 13], [1 , 4, 6, 7, 8, 10, 11, 12]}.

Nói chung, các mảng trong bộ sưu tập có kích thước tương ứng với 1 bit trong biểu diễn nhị phân của kích thước của tập hợp. Cấu trúc dữ liệu là hiệu quả vì chèn có thể được thực hiện trong khấu hao O (1) thời gian, và tìm kiếm có thể được thực hiện trong O ((log n)) thời gian (đó là tốt hơn so với tìm kiếm tuyến tính). Ngoài ra, nó chỉ sử dụng O (log n) không gian trên cao cho con trỏ, không giống như cây nhị phân cân đối và B-cây mà sử dụng O (n) thêm không gian cho con trỏ. Do đó, hầu hết không gian được sử dụng cho dữ liệu tải trọng.

Tôi đã xem số list of data structures của Wikipedia nhưng không tìm thấy kết quả phù hợp. Đúng là cuốn sách Giới thiệu về thuật toán ("CLRS") mô tả cấu trúc dữ liệu này như một bài tập về nhà trong phần "Phân tích phân bổ", nhưng vì đó là một câu hỏi chứ không phải là một ví dụ, cuốn sách không nói nhiều về nó.

Answer 1

Một ý tưởng tương tự có từ ít nhất đến số original publication on binomial heaps của Jean Vuillemin trong ấn bản CACM tháng 4 năm 1978. Tôi mong chờ bài báo giới thiệu cấu trúc dữ liệu này để trích dẫn hoặc được trích dẫn bởi Vuillemin, nhưng không có giấy tờ nào trong danh sách "tài liệu tham khảo" và "được trích dẫn bởi" trông đầy hứa hẹn.

Nếu tôi là bạn, tôi sẽ yêu cầu cstheory và sau đó viết thư cho CLRS, nhưng với giới hạn dưới và thiếu xóa, tôi không mong đợi bất cứ điều gì để bật trừ khi cộng đồng succinct data structure đã quan tâm tại một số điểm.

Có điều gì đặc biệt bạn muốn biết không?