내부적으로 STRING (정수 등)의지도는 어떻게 저장됩니까? 그것들은 어떻게 정렬되고 균형 잡혀 있습니까?

Question

STL의 Map 컨테이너는 내부적으로 자체 조정 트리 인 Red-Black 트리라는 것을 알고 있습니다.

지도에서 가장 낮은 요소는 트리의 맨 위에 있습니다. 따라서, 'anything'에 대한 정수의지도에 대해, 가장 낮은 정수는 맨 위에있는 식으로 계속됩니다. 항상 균형을 유지합니다. 그래서 정수와 그와 연관된 값을 검색하는 동안 log n 복잡성을 얻습니다.

그러나 문자열을 '무언가'로 매핑하는 경우 어떻게 균형을 조정하고 주문합니까? 어떤 끈이 나무 꼭대기에 있을까요? 그것은 ASCII 값 또는 뭔가 일치합니까?

이 코드는 절름발이 일지 모르지만 필자는 코드에서 log n의 복잡성을 고수해야하므로이를 알아야합니다.

Answer 1

지도에서 가장 낮은 요소는 트리의 맨 위에 있습니다.

아니요. 가장 작은 요소는 가장 왼쪽 노드에 있으며, null이 될 때까지 왼쪽 자식 포인터를 따라 이동합니다. 문자열의 경우 가장 작은 요소는 삽입 한 다른 모든 문자열을 항상 "미만"으로 비교 한 요소입니다. 기본 비교는 사전 편집입니다.

균형 조정은 as usual으로 진행되며, 포인터 스왑을 사용합니다. 루트에서 임의의 리프까지의 경로는 길이에 관계없이 Θ (lg n)의 길이를 갖습니다.

(규격에 부합하는 C++ 라이브러리는 다른 구조를 사용할 수 있지만 이것은 여전히 ​​일반적이다 map의 원래 STL의 구현을 가정한다.)