Định dạng dữ liệu tốt nhất để chọn các yếu tố ngẫu nhiên là gì?

Có cấu trúc dữ liệu nào hỗ trợ hiệu quả cho hai thao tác không?

1. Thêm một giá trị vào cấu trúc dữ liệu.
2. Dequeue và trả về một mục nhập cấu trúc dữ liệu với xác suất ngẫu nhiên thống nhất. Điều này tương tự như ví dụ "túi bi" cổ điển thường được sử dụng trong các bài giảng xác suất cơ bản. Bạn có thể đặt bất kỳ số lượng viên bi nào vào túi và sau đó lấy chúng một cách ngẫu nhiên một cách hiệu quả. Giải pháp tốt nhất tôi có thể nghĩ đến là lưu trữ các phần tử trong cây tìm kiếm nhị phân tự cân bằng (AVL, AA, đỏ/đen, v.v.). Điều này dẫn đến thời gian chèn là O(lg n). Để loại bỏ một phần tử ngẫu nhiên, chọn một chỉ số ngẫu nhiên i, sau đó xác định vị trí và loại bỏ phần tử thứ i của cây. Nếu bạn tăng cấu trúc đúng cách, bạn cũng có thể làm cho cấu trúc này chạy trong thời gian O(lg n). Thời gian chạy này không tệ, nhưng tôi tự hỏi liệu có thể cải thiện nó hay không - có lẽ là O(1) để chèn và O(lg n) để xếp hàng như trong ví dụ này? Hoặc có thể thứ gì đó sử dụng hàm băm để thực hiện thao tác chèn và xóa trong thời gian O(1) dự kiến? Có lẽ một ràng buộc khấu hao mạnh hơn? Có ai có bất kỳ đề xuất nào để làm cho điều này nhanh hơn không?