임의의 요소를 선택하기위한 데이터 구조?

Question

두 작업을 효율적으로 지원하는 데이터 구조를 아는 사람이 있습니까?

1. 데이터 구조에 값을 삽입하십시오.
2. 균일하게 임의의 확률로 데이터 구조에서 항목을 큐 해제하고 반환합니다.

이것은 입문 확률 클래스에서 항상 등장하는 정식 "구슬 가방"과 유사합니다. 가방에 임의의 구슬을 넣을 수 있으므로 구슬을 효율적으로 무작위로 제거 할 수 있습니다.

내가 가진 최선의 해결책은 다음과 같습니다 - 요소를 저장하기 위해 자기 균형 이진 검색 트리 (AVL, AA, 빨강/검정 등)를 사용하십시오. 이것은 O (lg n) 삽입 시간을줍니다. 무작위 요소를 제거하려면 무작위 색인 i를 선택한 다음 트리에서 i 번째 요소를 찾아 제거합니다. 적절하게 구조를 보완했다면, 이것은 O (lg n) 시간에도 실행되도록 만들 수 있습니다.

이 런타임은 나쁘지는 않지만 삽입이 O (1)이고 대기열에 대해 O (lg n) 일 가능성이 있다면 궁금합니다. 또는 아마도 에서 실행되는 뭔가가 O (1) 삽입 및 삭제 해시 함수를 사용하여? 아니면 더 큰 상각 된 경계?

누군가가 이것을 점진적으로 빠르게 만드는 방법에 대한 아이디어가 있습니까?

Answer 1

예. 벡터를 사용하십시오.

삽입하려면 간단히 끝 부분에 놓고 크기를 증가 시키십시오. 제거하려면 요소를 임의로 선택하고 내용을 끝 값으로 바꾼 다음 끝 값을 끕니다 (즉, 끝 값을 반환하고 벡터의 크기를 줄입니다).

두 연산은 모두 O (1)로 상각됩니다.