레드 - 블랙 트리가 이상적인 데이터 구조입니까?

Question

나는 처리 할 항목 (큰 rationalals)의 컬렉션을 가지고. 각각의 경우 처리는 컬렉션에서 가장 작은 항목을 제거하고 작업을 수행 한 다음 0-2 개의 새 항목을 추가하는 것으로 구성됩니다 (항상 제거 된 항목보다 큽니다). 컬렉션은 하나의 항목으로 초기화되며 비어있을 때까지 작업이 계속됩니다. 나는 어떤 크기의 콜렉션이 도달 할 지 확신하지 못하지만, 1M-100M 항목에서 기대할 수 있습니다. 가장 작은 것 이외의 항목을 찾을 필요가 없습니다.

현재 가장 작은 항목에 대한 포인터를 유지하기 위해 조정될 수있는 빨강 - 검정 트리를 사용할 계획입니다. 그러나 전에 사용했던 적이 없으며 사용 패턴이 그 특성에 잘 맞는지 확실하지 않습니다.

1) 왼쪽 + 무작위 삽입에서 삭제 패턴이 성능에 영향을 미칠 수 있습니까? 예 : 무작위 삭제보다 훨씬 더 많은 회전 수가 필요합니다. 아니면이 패턴을 사용하여 O (log n) 작업을 삭제하고 삽입 할 수 있습니까?

2) 다른 데이터 구조가 삭제 패턴으로 인해 또는 더 작은 항목을 찾을 필요가 있다는 사실을 이용하여 더 나은 성능을 제공합니까?

업데이트 : 기꺼이 내가 물었습니다. 바이너리 힙은 분명히이 경우를위한 더 나은 해결책이며, 약속 된대로 구현하기가 쉽습니다.

우고

Answer 1

binary heap은 원하는대로 더 좋습니다. 가장 작은 요소와 삽입 위치를 찾는 것만으로도 구현하기 쉽고 빠릅니다. 가장 작은 요소를 찾는 것은 O (1)이고, 그것을 제거하는 것은 O (log N)이며, 삽입 또한 O (log N)입니다.

Answer 2

힙 당신에게 O (1) O (로그 n) 제거를 줄 것이다 O 삽입 (로그 n), 및 쉽게 정도가 레드 - 블랙 트리보다 구현하는 것입니다

Answer 3

필요한 경우 더 복잡한 데이터 구조를 만드는 방법을 알고있는 것이 좋습니다. 그러나 일반적으로 최선의 방법은 가능한 한 간단하게 시작하는 것입니다. 필요한 경우 더 복잡한 것을 사용해야합니다.

자기 균형 나무를 구현 한 유일한 시간은 내 나무가 실제로는 (10,000 개가 넘는) 커질 것이라는 것을 알게되었을 때였고 그 데이터는 분출 된 분출물로 나올 것입니다. 즉, 일반 이진 트리를 사용했다면 거의 연결된 목록으로 끝났을 것입니다.

데이터가 임의 순서로 입력되는 경우 실제로는 분산 알고리즘을 신경 쓰지 않아야합니다.