파이썬에서 바이너리 검색 트리가 내장되어 있습니까?

는 거기에 어떤 자체 균형 이진 검색 트리 (RED-BLACK, AVL 또는 다른 사람) 내장 유형 파이썬 2.7 파이썬 3.x를에?파이썬에서 바이너리 검색 트리가 내장되어 있습니까?

Java의 TreeMap 또는 TreeSet과 같은 것을 찾고 있습니다.

이러한 내장 기능이없는 경우 왜 그 기능이 생략 되었습니까? 그러한 도구를 포함하지 않는 특별한 이유가 있습니까?

2013-07-25 Chirila Alexandru

표준 라이브러리에는 아무 것도 없습니다. 포함되지 않은 이유는 대답이 불가능합니다. 귀하의 질문의 나머지 부분은 주제 밖의 외부 리소스에 대한 요청입니다. –

http://stackoverflow.com/questions/2298165/pyestons-standard-library-is-there-a-module-for-balanced-binary-tree의 유사 항목 –

필자가 아는 한 특별한 이유는 없습니다. 그 이유는 너무 많은 응용 프로그램의 경우 고도로 조정 된 dict 및 set 구현 (해시 테이블)이 잘 작동한다는 것입니다. 그들은 대부분의 경우에 충분합니다. 밸런스드 바이너리 검색 트리의 성능 특성 (추가 순서가 아닌 키 기반의 순차적 트래버스와 같은)이 필요한 상황이 분명히 있지만 타사 패키지를 사용하는 사람들이 만족하는 길은 충분히 멀리 떨어져 있습니다 그럴 경우.

나는 PyPI에서 bintrees 패키지를 사용해 좋은 경험을했습니다. 이것은 순수 Python과 Cython으로 작성된 확장으로 불균형, AVL 및 적색 - 검정 이진 트리를 구현합니다.

나머지 이유는 본질적으로 역사적인 사고라고 생각합니다. bintree를 작성한 사람이 stdlib에 포함시키기 위해 로비를하고 유지 보수 및 릴리스에 부과 된 제약 사항을 기꺼이 참아 주었다면 아마 들어갔을 것입니다. (Cython 종속성이 문제를 일으킬 수 있지만, .)

알고리즘 복잡도 : 해시 테이블의

(dicts 또는 세트 등), 삽입 및 조회 O를 (1), 균형 트리에 대해 이러한 동안 O (로그 (N)). 순차적으로 키를 순회하는 것은 트리에서는 O (n)이지만 해시 테이블을 사용하여 동일한 작업을 수행하려면 먼저 키를 정렬해야하므로 O (n * log (n))입니다. 어떤 종류의 데이터 구조를 사용할 것인지를 결정할 때는 어떤 연산을 사용할 것인지 생각하고 응용 프로그램에서 가장 합리적인 절충안을 선택해야합니다.

출처

2013-07-25 12:10:19 babbageclunk

이것은 많은 의미가 있습니다. 아마도'dict'과'set'은 실제로 이진 검색 트리이거나, 아마도 훨씬 더 효율적인 것으로 추측됩니다. 나는 이들이 정확히 어떻게 구현되는지 연구 할 것이다. –

@ChirilaAlexandru :'dict'과'set'은 해쉬 테이블입니다. –

@wilberforce : 나는 'blist'에게 stdlib에 착륙하는 더 좋은 기회를 줄 것입니다. 나는 그것이 실제로 어느 시점에서 고려되었다고 생각하지만, 나는 세부 사항을 상기하지 않는다. –

표준 라이브러리에는 나무가 없습니다. 파이썬은 내부 (객체, 클래스 및 모듈은 모두 dicts를 기반으로 함)에 대한 해시 테이블 인 사전을 많이 사용합니다. 따라서 dicts는 크게 최적화되었습니다. 따라서 검색 트리에 대한 요구가 훨씬 줄어 듭니다. 또한 이러한 나무를 효율적으로 사용하려면 확장 유형으로 구현해야합니다.

출처

2013-07-25 12:08:52 hivert

파이썬에서 바이너리 검색 트리가 내장되어 있습니까?

답변

관련 문제