여러 소스에서 std :: map이 적색 - 검은 색 트리를 사용하여 구현되었음을 알 수 있습니다. 이러한 유형의 데이터 구조는 특정 순서로 요소를 보유하지 않고 BST 속성과 높이 균형 요구 사항 만 유지한다는 것이 내 이해입니다.std :: map의 순서는 어떻게 이루어 집니까?
그래서 map :: begin은 일정한 시간이며 어떻게 순서가 지정된 시퀀스를 반복 할 수 있습니까?
std::map은 내부적으로 BST를 유지한다는 전제에서 시작됩니다 (표준에서 엄격하게 요구되는 것은 아니지만 대부분의 라이브러리는 빨간색 - 검은 색 트리와 유사 함).
BST에서 가장 작은 요소를 찾으려면 O (log (N)) 인 리프에 도달 할 때까지 왼쪽 분기를 따라 가야합니다. 그러나 일정한 시간에 "begin()"반복자를 전달하려는 경우에는 내부적으로 가장 작은 요소를 추적하는 것이 매우 간단합니다. 삽입으로 인해 가장 작은 요소가 변경 될 때마다 업데이트합니다. 그것은 물론 메모리 오버 헤드이지만, 그것은 절충점입니다.
루트 노드를 의도적으로 불균형으로 유지하는 것과 같이 가장 작은 요소를 선택하는 다른 방법이있을 수 있습니다. 어느 쪽이든, 그렇게하기가 어렵지 않습니다.
"순서화 된"시퀀스를 반복하려면 단순히 트리의 순회 트래버스를 수행해야합니다. 가장 왼쪽의 리프 노드부터 시작하여 (위로), (오른쪽으로), (위로, 위로), (오른쪽으로) ... 등등 .. 간단한 규칙 집합이며 구현하기 쉽습니다. 바로 see a quick implementation of a simple BST inorder iterator 내가 잠시 뒤로 썼다. In-order traversal을 수행함에 따라 가장 작은 순서에서 가장 큰 순서로 모든 노드를 올바른 순서로 방문합니다. 즉, "배열"이 정렬된다는 환상을 주지만 실제로는 정렬 된 것처럼 보이게하는 탐색입니다.
감사합니다. 정렬 된 순서를 생성하는 인 오더 트래버 설 조각이 누락되었습니다. –
@SteveM 사이드 노트에서'std :: map'과 같은 컨테이너는 반복을 잘 처리하지 못합니다. 트리 탐색의 논리와 항상 메모리에서 뛰어 다니기 때문에 실제로는 성능이 떨어집니다. 따라서, "주로 룩업 (look-ups), 가끔씩 명령 된 횡단 (traversal)"또는 값 범위를 찾는 것과 같은 것들을 고려하십시오. 빠른 traversal을 위해 일반적으로 정렬 된'std :: vector'를 유지하는 것이 좋습니다. [내 다이어그램] (http://stackoverflow.com/questions/471432/in-which-scenario-do-i-use-a-particular-stl-container/22671607#22671607)에 언급되어 있습니다. –
빨강 - 검정 트리의 균형 조정 속성을 사용하면 트리의 어느 위치 에나 O (로그 N) 비용으로 노드를 삽입 할 수 있습니다. 일반적인 std::map 구현의 경우 컨테이너는 트리를 정렬 된 상태로 유지하고 새 노드를 삽입 할 때마다이를 올바른 위치에 삽입하여 트리를 정렬 한 다음 트리의 균형을 다시 조정하여 red-black 속성을 유지합니다.
아니요, 검은 색 나무는 본질적으로 분류되지 않습니다.
RB 트리는 2 진 검색 트리입니다. 이진 탐색 트리는 요소를 특정 순서로 저장하지는 않지만 항상 인바운드 탐색을 수행 할 수 있습니다. map : : begin이 어떻게 일정한 시간을 보장하는지 모르겠다. 이것은 항상 가장 작은 요소 (보통 O (log (n)) 일 것이다)에 대한 경로를 기억하고 있다고 가정한다.
http://stackoverflow.com/a/7648812/3651800 –
@Matt Courbrough 그 말로 std :: map은 빨간색 - 검은 색 트리를 사용하여 얻는 방법이 아니라 정렬 된 것으로 보장됩니다. –
귀하의 질문에 대한 오해가 있었을 수도 있지만 그 대답은 주문에 사용 된 비교 기능을 설명합니다. –