나는이 : 그것은 지금인덱싱 된 데이터 구조에서 제거하고 동시에 이동하는 것을 피할 수 있습니까?
0 => a
1 => x
2 => A
...
1356 => w
1357 => o
로, 내가 쉽게 POS (555)가 색인되어 있기 때문에, 즉, 어떤 선형 검색이 필요하지 않습니다를 얻을 수 있습니다.
이제 333 위치를 제거하면 다음 번에 get(555)이라고 호출하면 이전 요소 인 556이 제거 된 이후에 새로운 555가 될 것이므로 위의 모든 요소가 이동해야합니다.
목록이 커지면 이동이 비쌉니다.
이동하지 않고 제거하고 모든 항목을 올바르게 색인화하는 방법이 있습니까?
가장 먼저 떠오르는 것은 이중 연결된 목록이지만 인덱싱되지 않습니다.
변화를 줄이기 위해 데이터 구조의 이상한 조합이 필요하지만 여전히 색인이 있습니까?
실제로는 오더 통계 트리라고하는 수정 된 2 진 트리를 사용하여 각각 시간 O (log n)의 임의 액세스와 시프트를 지원할 수 있습니다. 이것은 각 노드가 왼쪽 및 오른쪽 하위 트리에 노드 수를 저장하는 균형 이진 트리입니다 (예 : 요소가 정렬되지 않은 경우에도 빨간색/검은 색 트리 또는 AVL 트리처럼 균형을 이룬 트리). 수정 된 BST 검색 알고리즘을 사용하면 시간 O (log n)의 트리에서 k 번째 요소를 찾을 수 있습니다. 그 노드를 얻은 후에는 O (log n) 시간에 삭제하거나 O (log n) 시간 직전에 노드를 삽입 할 수 있습니다.
CLRS와 같은 많은 입문 알고리즘 교과서에서는 이러한 작업을 세부적으로 수행하는 방법을 설명합니다.
희망이 도움이됩니다.
Java에서 그러한 구현이 있습니까? 필자가 원하는 데이터 구조는 외부 API 측면에서 매우 간단하지만 설명하는 내부 세부 정보는 복잡합니다. 그러므로 구현 어딘가에 큰 도움이 될 것입니다! –
내가 알고있는 한, 표준 자바 API에는 없다. 나는 내 머리 꼭대기에서 자바 구현을 모른다. 아마 인터넷 검색으로 시작 하겠지. 희망을 찾으십시오! – templatetypedef
데이터 구조에 필요한 것은 무엇입니까? 간단한 방법은 O (sqrt (N)) 성능을 허용하지만 (세그먼트 트리의 선을 따라) 밸런싱 된 이진 트리를 사용하면 O (log N)을 허용하지만 대부분의 k 요소의 k 배열로 크기 N 배열을 나눕니다. 성능은 다소 복잡합니다. – Nuclearman
그건 재미 있어요. 당신은 대답에 여러 배열 방법으로 침입에 대해 자세히 설명해 주시겠습니까? 감사! –
'TreeMap'은 당신의 요구를 만족시키지 못합니까? –