빨강 검정 트리 및 다중 맵

많은 컴파일러에서 Set, Map 및 Multimap과 같은 표준 데이터 구조는 배후에서 빨강 - 검정 트리를 사용하고 multimap은 여러 개의 중복 키를 저장합니다.빨강 검정 트리 및 다중 맵

나는 인용 이하에 대한 질문이 있습니다

"결합하는 레드 - 블랙 트리를 저장 키를 고유와 한 DataValue에 각 키"

사실 문 위에 ?
이것이 사실이라면, 어떻게 red-black-tree를 사용하여 multimap을 구현할 수 있습니까? (C++ STL 에서처럼)?

2012-11-23 deepmax

Wintellect의 Power Collections http://powercollections.codeplex.com/에서 MultiDictionary, OrderedMultiDictionary 및 OrderedMultiDictionary에서 사용하는 내부 RedBlack 클래스를 살펴 보았습니까? 그건 그렇고. 닷넷의 SortedDictionary는 레드 블랙 트리 (SortedSet)를 사용하여 구현됩니다. 여기에서 소스 코드를 찾을 수 있습니다. http://referencesource.microsoft.com/netframework.aspx –

1) 아니요, 사실이 아닙니다.

2) 키를 여러 값으로 매핑하기 위해 단일 검정 빨강 트리를 수정하는 것은 간단합니다. 두 번째 데이터 구조를 사용하고 key -> collection을 매핑하면됩니다.

예를 들어 문자열을 int로 매핑하는 대신 문자열에서 int 벡터로 매핑 할 수 있습니다. 또는 int의 연결된 목록에 대한 문자열입니다. 또는 단일 매핑 RBT에 대한 문자열입니다. 곧 :).

Revisiting # 1 : 기술적으로는 여전히 키를 단일 값으로 매핑하는 것이고 값은 직접 매핑 된 유형이 아닙니다. "DataValue"라고 생각하는 것에 따라, 그렇습니다. 진술은 사실입니다.

또한 보조 데이터 구조는 실제로 필요하지 않습니다. 그냥 순회를 단순화합니다. 근본적으로 중복을 수용하기 위해, 부모/왼쪽과 부모/오른쪽 사이의 관계보다 엄격한/작지 않은 관계 대신에, 한면에 동등한 것이 포함됩니다. 예를 들어

 5 
    3  7 
3

출처

2012-11-23 08:12:28 Corbin

그러나 C++에서 '멀티 맵'은 중복 된 쌍을 저장할 수 있습니다. 예를 들어 <1,"First">을 세 번 삽입하면 '멀티 맵 (multimap) '은 같은 세 쌍을 가지고 있습니다. – deepmax

정확합니다. 다중 맵은 다중 값을 저장할 수있는 각 노드에 데이터 구조를 저장합니다. 이진 트리는 대부분 * 키 *에 관한 것이지 * 값 *에 대한 것이 아닙니다. – Philipp

그냥 의견을 쓰고 있었지만, 그래, 필립은 그것을 맞았다 :). – Corbin

당신은 노드의 양쪽에 아이들이 부모가 아닌도 이하도 큰 키를 포함 할 수 있습니다. 균형을 잃을 수 있기 때문에 양쪽에서 평등을 허용해야합니다. 즉, n 개의 등호로 이루어진 트리는 높이가 n이됩니다.

출처

2012-11-23 08:34:29 tmyklebu

빨강 검정 트리 및 다중 맵

답변

관련 문제