Java Collections API에 Tree가 구현되지 않는 이유

호기심에서 벗어나 최근에 내 프로그램 중 하나에 트리를 사용해야했지만 이진 트리를 직접 만들어야했지만 Collections API에 기본 값이없는 이유는 무엇입니까? 트리 (또는 심지어 바이너리 트리) 구현?Java Collections API에 Tree가 구현되지 않는 이유

컬렉션 API에 포함시키지 않기로 결정한 이유가 분명하다고 생각합니다.

출처

2011-12-27 Rajesh Pantula

참으로 흥미 롭습니다. – Eugene

TreeSet과 TreeMap은 이진 트리로 백업되는 두 개의 모음입니다. –

바이너리 트리에 대해서만 말하지 않고 왜 일반화 된 트리 구현, 트리 인테 페이스를 가지고 있지 않습니까? –

java.util.TreeMap은 빨강 및 검정 트리 구현입니다.

출처

2011-12-27 06:51:41 Scorpion

TreeMap은 존재하지만 TreeMap은 트리 구조의 좀 더 구체적인 형태입니다. 우리가 List와 Set에 대해 가지고있는 것과 같은 트리 구현. Collections API의 제작자가 일반화 된 형태의 트리를 제공하지 않기로 결정한 이유는 무엇입니까? 그들은 inteface 트리 과 그 구현을 BinaryTree, AVLTree, RedBlackTree로 제공 할 수 있습니까? –

나는 Artem Zh.의 대답에 동의한다. 트리는 엔티티의 "콜렉션"을 보유하는 데이터 구조의 특정 형태 일뿐입니다. – Scorpion

이론적으로 IMHO는 컬렉션 유형이 아니며 단지 구현 유형입니다. 즉, Set (정렬되지 않은 항목 집합), List (정렬 된 항목 집합), Map (두 집합 사이의 관계가있는 항목 집합) 등의 추상 컬렉션이 있으며 해당 구현이 있습니다. array, list (예 : ArrayList 및 LinkedList), HashSet 등, 그들 모두는 그들 자신의 장단점을 가지고있다. 따라서 Tree는 배열보다 빠른 검색을 제공하지만 인덱스를 통한 액세스는 제공하지 않는 구현 중 하나 일뿐입니다 (예 : 목록).

현재, Java의 TreeMap ("Red-Black 트리 기반 NavigableMap 구현") 및 TreeSet ("TreeMap을 기반으로 한 NavigableSet 구현") 클래스가 있습니다.

출처

2011-12-27 06:55:51 Wizart

. 컬렉션은 데이터 구조에 의해 정의되지 않지만 삽입, 삭제 및 조회와 관련된 성능에 대한 약속이 있습니다. 구현의 세부 사항은 관련이 없으므로 사용 요건이 무엇인지에 따라 컨테이너를 선택하십시오. 예를 들어, 요소가 항상 정렬되고 조회가 O (log n)이어야하는 컨테이너가 필요하면 Set 또는 SortedMap이 필요합니다. 구현이 성능 보증을 어떻게 이행하는지는 중요하지 않습니다. –

나는 동의하지 않는다. 컬렉션은 계약에 의해 정의됩니다. 'Set'은 순서의 보장을하지 않기 때문에 색인 된 액세스가 없지만 중복을 보장하지는 않습니다. 'List'는 순서를 보장하지만 중복을 허용합니다. 'Map'은 요소들 사이의 관계를 포함합니다. 트리를 사용하여 이들 중 일부 (전부?)를 구현할 수 있다는 사실은 부적합합니다. 예를 들어'List '를 사용하여'Set'(예 :'LinkedHashSet')을 구현할 수 있습니다. 트리를 구현하는 방법은 여러 가지가 있습니다. – Tonio

내가 컬렉션 API에 포함시키지 않기로 한 이유가 분명하다고 생각합니다.

나는 이유는 아무도 사용 사례의 넓은 범위를 커버하기에 충분한 양

일반 목적이다 나무에 대한 좋은 API와 함께 올 것을이라고 생각하고,
유용 전반적인 성능 오버 헤드를 보완하기에 충분합니다.

(그리고 당신은 중지합니까 어디? 트리? 이진 트리? N 진 나무? DAG? 그래프?)

어느 아파치 코 몬즈 컬렉션 또는 Google 컬렉션 (일명 구아바)는이 있음을 주목할 필요가있다 트리 API. 그러나이 주제에 대한 활성 구아바 문제가 있습니다 - http://code.google.com/p/guava-libraries/issues/detail?id=174 - 분명히 적어도 일부는 사람들이 당신의 견해에 동의합니다. 버전 15.0로

UPDATE

는 구아바는 이제 TreeTraverser 및 BinaryTreeTraverser 클래스의 형태로 나무 지원한다. 그러나 이것은 당신이 기대하는 바가 아닐 수도 있습니다. 실제로 이러한 클래스는 실제로 트리 데이터 구조를 구현하지 않습니다. 대신 generic 형식 매개 변수에서이 작업을 수행해야합니다. 게다가, Traverser 클래스는 노드 유형의 API에 대한 가정을 피하기도합니다. 그들은 추상 클래스가되고 트리를 조사하는 연산을 구현하기 위해 구체적인 traverser 부속 유형을 요구함으로써 이것을 수행합니다. 예 : 노드의 자식을 가져옵니다.

FWIW, TreeMap 및 TreeSet는 "나무 API에"아니다. 이들은 Map 및 Set API의 트리 기반 구현입니다. tree-ness는 공개 API에 완전히 숨겨져있어이 두 클래스를 범용 트리로 사용하기에 적합하지 않습니다.

출처

2011-12-27 07:25:10

Java Collections API에 Tree가 구현되지 않는 이유

답변

관련 문제