삽입, 삭제, 액세스 및 병합이 적어도 O(log n) 인지도 데이터 구조가 있습니까?빠른 병합을 허용하는 맵 데이터 구조가 있습니까?
대부분의 self-balancing binary trees 같은 AVL trees 및 red-black trees 이러한 속성의 대부분을 가지고 있지만, 나는 그들이 O(n log n) 병합을 믿습니다. 병합 속도가 빠른 데이터 구조가 있습니까?
편집 : 주변을 둘러 보았습니다.이 같은 것을 찾을 수 없습니다. 그러한 데이터 구조가 없다면 왜 이것이 가능하지 않은지에 대한 통찰력이 필요합니다.
나는 스플레이 트리를 살펴볼 것입니다. 아마 길을 따라 합병 비용을 지불하게 될 것이지만, 다른 나무를 주입하고 나중에 비용을 줄여야합니다.
비교가 정의 된 임의의 키 유형에 대해 트리가 필요하거나 고정 크기 이진 표현 (int, long, float, double, ..이있는 유형에서만 작동하는 경우에는 정상입니다. .)? 후자의 경우, 이진 기수 (binary radix) 트리는 매우 효율적인 병합을하는 데이터 구조입니다 (운이 좋다면 O (1), 최악의 경우는 O (N)).
데이터 구조에 대한 자세한 내용은 Chris Okasaki 및 Andrew Gill의 Fast Mergeable Integer Maps을 참조하십시오.
스칼라 컬렉션 라이브러리에는 ints 및 longs에 대한 구현이 포함되어 있습니다. 다른 모든 java 기본 유형은 int 또는 longs로 변환 될 수 있습니다. Double에 java.lang.Double.doubleToLongBits를 사용한다.
멋지다, 나는 그것을 사용할지도 모른다. .. 나는 단지 파괴적인 독서의 생각을 좋아하지 않는다. – Zifre
@Zifre : 읽기는 실제로 파괴적이지 않습니다. 무엇이든이 일반적으로 나무의 구조를 개선하고 * 외부의 표현을 바꾸지 않습니다. –
스플레이 트리의 상수 요소는 매우 나쁩니다. 드물게 병합하면 병합에 대한 최악의 경우 실행 시간이 "열등한"상태가 될 수 있습니다. – Dave