키 - 값 쌍 삽입 후 검색 트리의 값 증가

Question

프로그래밍 문제로 작업 중이며로드 블록으로 실행 중입니다. 임의의 정수를 다른 정수에 매핑하는 데이터 구조를 찾으려고합니다. "해시 테이블!"이라고 말하는 경향이 있습니다. 또는 "Search Tree!"라고 말하면서 실제로 이것들을 생각해 보았습니다 (더러운 구현을 시도했습니다). 그러나, 잡기가있다!

매핑에서 값을 삽입하거나 제거 할 때마다 삽입 또는 제거 된 값보다 크거나 같은 모든 값을 하나 또는 일부 임의의 오프셋만큼 증가/감소시키고 싶습니다.

다음은 예입니다. (1 7), I는 증가 할 내가 키 - 값 쌍을 추가하면 이제

Keys: (1, 6, 18, 21, 24) 
Vals: (2, 1, 3, 0, 4) 

:

내가이 맵에 내 키와 값에 사용할 정수의 두 목록을 말해봐 이상의이 초래 한 동일한 모든 값 :

Keys: (1, 6, 7, 18, 24) 
Vals: (2, 1, 0, 3, 4) 

: I는 키 - 값 쌍을 삭제하면 후속

Keys: (1, 6, 7, 18, 21, 24) 
Vals: (3, 2, 1, 4, 0, 5) 

및 (21, 0),이 결과

이것은 두 목록/배열과 각 삽입/삭제 (즉, 값을 검토하고 하나씩 변경) 한 후에 처리하는 것이 다소 쉽습니다.

그러나 나는 값의 전체 목록을 검토하고 증가/감소시키지 않고도보다 효율적으로 작업 할 수있는 방법을 찾고 있습니다. 아마도 (증가/감소해야하는) 값이 요청 될 때까지 증가/감소를 지연하는 것조차도 가능합니다.

의견이 있으십니까?

Answer 1

일부 키를 사용하여 빠른 검색을 수행하고 실제 값을 기반으로 결과를 수정해야한다면 키와 값의 두 가지 데이터 구조가 필요하다고 생각합니다.

키의 데이터 구조는 키에서 트리의 노드까지 연관 배열 (해시 테이블, 자체 균형 조정 트리 또는 건너 뛰기 목록으로 구현, 중요하지 않음)이 될 것입니다. 값.

값을위한 트리는 자체 균형 이진 검색 트리 (또는 건너 뛰기 목록, 아래 편집 참조)가 될 것입니다. 트리의 노드에는 해당 값과 함께 델타가 연관되어 있습니다. 델타는 특정 노드보다 크거나 같은 모든 노드에 적용됩니다. 즉, 노드 자체와 오른쪽 하위 트리의 모든 노드에 적용됩니다.

값을 삽입 할 때 삽입하는 값보다 크거나 같은 모든 노드의 델타를 증가시킵니다. 이 값은 전체 트리에 삽입하는 값보다 크거나 같은 모든 노드의 실제 값을 증가시킵니다. 삭제는 비슷합니다. 증분만으로는 감소로 대체됩니다.

값을 읽으려면 키 기반 구조를 사용하여 값 기반 트리에서 노드를 찾으십시오. 그런 다음 루트로 올라가서 (이를 위해 트리의 노드 부모에 대한 포인터를 유지해야 함) 값을 시작한 노드의 값보다 크거나 같은 노드에서 델타를 누적해야합니다.

일부 노드의 델타를 다시 계산해야하기 때문에 사용자가 선택한 자체 밸런싱 알고리즘으로 리 밸런싱을 수행 할 때 조심해야하지만 시간 복잡성에 영향을주지 않아야합니다.

EDIT : 건너 뛰기 목록의 경우 델타를 관리하는 것은 매우 쉽습니다. 삽입 할 위치를 찾고있을 때 비교할 링크 된 목록의 모든 노드에서 델타를 증가 시키십시오. 삽입하려는 값 (한 수준 아래로 내려가는 것을 의미 함). 삭제 된 항목을 오른쪽으로 이동하여 델타를 이동해야한다는 점을 제외하면 삭제는 비슷합니다.

특정 노드의 실제 값을 계산하려면 현재 항목에서 가능한 한 올라가서 델타를 적용하십시오 (한 항목은 다른 수준에서 한 번의 삽입 또는 삭제에서 여러 번 델타를 가질 수 있습니다. 항상 최상위 레벨의 값을 사용해야 함) 링크 된 목록의 한 노드에서 왼쪽으로 이동하여 맨 왼쪽 항목에 도달 할 때까지 프로세스를 반복하십시오.

노드에 액세스하는 방법은 링크 된 목록을 이중 연결해야한다는 것을 의미합니다.