지도의 트리에 대한 최적의 데이터 구조는 무엇입니까

Question

데이터 구조는 기본적으로지도의 트리입니다. 각 노드의지도에는 부모 요소의 요소가 포함되어 있습니다. 지도. 여기에서지도는 키와 값을 가진 프로그래밍 맵을 의미합니다 (STL의지도 또는 Python의 dict).

root = {'car':1, 'boat':2} 

어린이 2는 각각

child1 = {'car':1, 'boat':2, 'jet':35} 
child2 = {'car':1, 'boat':2, 'scooter':-5} 

내 검색이 다음 노드에서 수행됩니다 부모의지도에 요소를 추가 :

예를 들어, 루트 노드가있을 수 있습니다. 예를 들어 child1 [ 'jet']은 35를 반환하지만 root [ 'jet']는 발견되지 않은 오류를 반환합니다.

이 공간을 가능한 한 효율적으로 만들고 싶습니다. 즉, 각 노드에서 결과 맵의 전체 복사본을 저장하고 싶지는 않지만, 조회는 여전히 O (로그 N) 일 것입니다. N은 존재합니다. 노드에서의 전체 요소 수이며 전체 트리는 아닙니다.

아마도 내가 사용할 수있는 스마트 해시 함수가 있다고 생각했지만 아무 것도 생각할 수 없었습니다.

순진한 방법은 새로 추가 된 항목을 각 노드의 맵에 저장 한 다음 아무것도 발견되지 않으면 트리 위로 이동하는 것입니다. 나는 그것이 나무 깊이에 달려 있기 때문에 이것을 좋아하지 않는다.

Answer 1

해시 맵을 비교하는 함수를 만드는 방법과 일치하는지 여부를 true 또는 false로 반환하는 방법은 키와 값 쌍의 순서가 약간 까다로울 수 있습니다.

그런 다음 새 노드 (맵)를 트리에 추가 할 때마다이 함수를 사용하십시오. 트리의 모든 기존 노드를 확인하고 해시 맵이 이미있는 경우 해당 노드를 가리 키도록하십시오.

이렇게하면 해시 맵을 비교하는 데 많은 처리가 필요할 수 있지만 대부분의 공간을 절약 할 수 있습니다.

희망이 도움이됩니다.

편집 :지도에서 유니언을 수행하고 결과가 비교할 수있는 길이가 동일한 지 확인할 수 있습니다.

Answer 2

나는 당신이 'jet'을 찾고 그게 child1의 전체 목록을 얻을 것입니다.

기본 데이터는 나무입니다. 해당 레벨의 모든 데이터에 대한 참조를 유지합니다 (예 : 'jet':35 및 상위에 대한 포인터).

참조는 다른 해시 구조를 통해 이루어지며, 키 ('jet')에 대한 포인터로 매핑됩니다. 트리.

map['jet'] => {'jet':35, parent:root} 

나는 이해가 안

map['jet'] => {'car':1, 'boat':2, 'jet':35}