TreeMap에 대한 이해

Question

이것은 트리 맵에 관한 noobie 질문입니다. Java API 및 기타 설명서를 읽었지만 이것이 작동하는 방식에 대해서는 아직 명확하지 않습니다.

제 생각에 자바 (또는 다른 언어)의 트리는 일종의 가계도입니다. 당신이 말을 한 곳 :

Layer 1        OldestGuy  
Layer 2  OldGuy1  Oldguy2   OldGuy3  OldGuy4   OldGuy5 
Layer 3 Guy1 Guy2 Guy3 Guy4 Guy5 Guy6........ etc 

레이어 1의 1 개 값 (즉, 중앙 노드)가 이후의 각 계층의 값 (또는 녀석)의 임의의 양이있을 수 거기에서, 그리고

은 "지점"의 일부 (예를 들어 OldestGuy -> OldGuy1 -> Guy1이 될 수 있습니다.) & Guy2 ... 동시에 다른 지점은 OldestGuy -> OldGuy4입니다.

이 마음으로 나는 노력하고 있습니다. 특정 연결을 만들고있는 동안 특정 브랜치의 특정 위치에있는 TreeMap에 값을 추가하지만, 나는 점점 커지는 것처럼 보이는 것은 HashMap과 같은 결과이다.

(이것은 무엇을 내가 원하는 것은 동일) 여러 가지 다른 값 것) 키 (또는 레이어 (?와 트리 맵보다 더 많은 일을 .... 필요 보인다

모든 제안/설명이 될 것이다 환상적입니다. 마치 내가이 나무로 심각하게 짖는듯한 느낌이 들기 때문에.

Google의 googles .jar (예 : 가계도)를 사용하여이 작업을 수행 한 예를 보았지만이 문제를 이해하려고합니다. TreeMap과 Tree 간에는 많은 충돌이 있으며 데이터를 저장하는 방법은 무엇입니까?

Answer 1

TreeMap은 백그라운드에서 붉은 검정색 트리를 사용하는 Map의 구현 일뿐입니다. 트리의 세부 정보는 사용자에게 노출되지 않으므로 임의의 위치에 요소를 저장할 수 없습니다.

다른 말로하면 TreeMap은 범용 트리 데이터 구조가 아닙니다. 그게 당신이 실제로 원하는 스택 오버플로 질문을보십시오 : Java tree data-structure?.

Answer 2

Java TreeMap은 O (log n) 조회 및 삽입을 얻기 위해 내부 데이터 구조로 트리를 사용하지만 해당 트리 구조는 인터페이스에 표시하지 않습니다. 예를 들어, 트리 노드와 모든 자손을 가져 오거나이를 사용하는 가계도를 나타내는 방법은 없습니다.

Answer 3

TreeMap은 Map 또는 기타를 통해 구현 된 트리가 아닌 Map입니다 (트리를 통해 구현 됨).

Answer 4

나는 두 가지 다른 것을 혼동하고 있다고 생각합니다. TreeMap은 빨강 - 검정 트리으로 구현됩니다.
자바 당 문서 :

Red-Black 트리 기반 NavigableMap 구현. 지도는 해당 키의 자연 순서에 따라 순으로 정렬되거나 사용되는 생성자에 따라지도 작성시 비교 자 으로 제공됩니다.

이 구현은 containsKey, get, put 및 remove 작업에 대해 보장 된 log (n) 시간 비용을 제공합니다. 알고리즘은 Cormen, Leiserson 및 Rivest의 알고리즘 소개 에있는 알고리즘을 개로 수정 한 것입니다.

그래서 본질적으로 당신은 당신이 자연 순서를 사용하여 키를 주문하거나 Comparator가 직접 인터페이스를 구현하는 트리 맵을 남겨 두어야 하나 열쇠의 예측 가능한 순서를 갖고 싶어합니다. 다시, 자바 독에서 :
순서는, 트리 맵에 의해 유지되는 것을

주 어떤 정렬지도, 소트 맵 인 경우 및 명시 적 비교가 제공되는지 여부, equals와 일관성 해야합니다 같은 지도 인터페이스를 올바르게 구현해야합니다. Map 인터페이스가 equals 연산으로 정의되었지만 정렬 된 맵은 compareTo (또는 비교) 을 사용하여 모든 키 비교를 수행하기 때문에 이와 유사합니다. 자세한 내용은 의 equals와 일치하는 정확한 정의를 참조하십시오. 이 메쏘드에 의해 같은 것으로 간주되는 두 개의 키는 정렬 된 맵의 관점에서 동일하다. 정렬 된지도의 동작은 순서가 equals와 일치하지 않더라도 잘 정의 된 입니다. 은 Map 인터페이스의 일반 계약에 복종하지 않습니다. 당신은 제가 말씀 드린 방법 (즉 자연 순서) 또는 다른 방법으로 당신의 키를 배치 할 경우

지금, 그것은 분명하지 않다 (즉, 삽입하기 위해 또는 뭔가 다른?).
예를 들어, 광고 주문을 선호하는 경우 LinkedHashMap이 귀하의 경우에 더 좋을 수 있습니다.
그 밖의 다른 경우에는 그것을 지정하십시오 :].

Answer 5

public class TreeMap<K,V> 
extends AbstractMap<K,V> 
implements NavigableMap<K,V>, Cloneable, Serializable 

• 트리 맵은 키를 저장하는 해시 사용하지 않습니다. 그것의 사용 레드 - 블랙 트리 (자기 균형 이진 검색 트리.).
• TreeMap은 키의 자연 순서에 따라 정렬됩니다. 트리 맵은 항상 모든 요소가으로 정렬됩니다.
• 트리 맵 작업은 트리 데이터 구조을 기반으로합니다.
• 트리 맵 동기화되지 않음 따라서 스레드 안전하지 않음입니다.
• Java에서 트리 맵 null 키 허용, null null 값 허용.

트리 맵 작업은 트리 데이터 구조를 기반으로합니다.

• 각 노드에는 PARENT, LEFT 및 RIGHT라는 3 개의 참조가 있습니다.
• 왼쪽 요소는 항상 상위 요소보다 작습니다.
• 오른쪽 요소는 항상 더 강하거나 부모 요소와 동일합니다.