C++ STL 클래스 std :: map은 이진 트리를 사용하여 O (log (n)) 검색을 구현합니다. 그러나 나무를 사용하면 iterator가 어떻게 작동하는지 즉시 알 수 없습니다. ++ 연산자는 실제로 트리 구조에서 무엇을 의미합니까? "다음 요소"의 개념은 배열에서 명백한 구현을 가지고 있지만, 저에게는 나무가 그렇게 분명하지 않습니다. 트리 이터레이터를 어떻게 구현합니까?std :: map iterator는 어떻게 작동합니까?
inorder traversal (아마도 다른 노드에서도 작동합니다.) 노드에 부모 포인터가있는 경우 비회원 순회를 수행 할 수 있습니다. iterator에 두 개의 포인터를 저장하는 것이 가능해야합니다. 현재 위치를 표시해야하며 아마도 연구를 수행하지 않을 것입니다. 알아낼 수 있도록 "이전"포인터와 같은 것이 필요합니다. 현재 이동 방향 (즉, 왼쪽 하위 트리에 들어가야할까요, 아니면 그냥 돌아 왔습니까?).
"이전" "부모"와 같은 노드가 입력되었습니다. 왼쪽 하위 트리에서 돌아 오는 경우 "left", 오른쪽 하위 트리에서 돌아 오는 경우 "right", 반환 된 마지막 노드가 우리 자신의 것이면 "self"입니다.
현재 요소가 아닌 현재 요소가 아닌지도의 모든 요소 집합을 고려하십시오. "다음 요소"는 해당 집합의 다른 모든 요소보다 적은 요소 집합의 요소입니다.
지도를 사용하려면 키가 있어야합니다. 그리고 그 열쇠는 "미만"작업을 구현해야합니다. 이는 찾기, 추가, 제거, 증가 및 감소 조작이 효율적 이도록 맵이 형성되는 f}을 결정합니다.
일반적으로지도는 내부적으로 어떤 종류의 나무를 사용합니다.
원본을 처음 시작할 때 볼 수 있습니다. http://www.sgi.com/tech/stl/stl_map.h – amit
일반적인 [자체 균형 이진 검색 트리] (http : // en.wikipedia.org/wiki/Red%E2%80%93black_tree). 올바른 노드를 찾거나 트리를 위아래로 이동하여 주어진 노드에서 다음 큰 노드로 이동하는 알고리즘을 쉽게 볼 수 있습니다. 때로는 여러 번 점프해야하지만 트리의 높이가 요소 수의 대수이므로 상수 시간이 상각됩니다. –
위키피디아의이 기사는 귀하의 질문에 대한 답변입니다 : [Tree traversal] (http://en.wikipedia.org/wiki/Tree_traversal). 기본적으로 "next"요소는 사용하는 트래버스 유형에 따라 다를 수 있습니다. 'std :: map'의 경우, 트리는 순서대로 (가장 작은 요소부터 가장 큰 요소까지) 순회됩니다. –