Python의 표준 라이브러리-균형 이진 트리 용 모듈이 있습니까?

Python의 표준 라이브러리-균형 이진 트리 용 모듈이 있습니까?

---

Python의 표준 라이브러리에 AVL 또는 Red-Black 또는 다른 유형의 균형 이진 트리 용 모듈이 있습니까? 나는 하나를 찾으려고했지만 실패했습니다 (나는 비교적 Python을 처음 접했습니다).

---

아니요, stdlib에는 균형 잡힌 바이너리 트리가 없습니다. 그러나 귀하의 의견에 따르면 다른 옵션이있을 수 있습니다.

• O(log n)검색 목록 대신 BST를 원한다고 말합니다 . 검색이 필요한 전부이고 데이터가 이미 정렬 된 경우 bisect모듈은 목록에 대한 이진 검색 알고리즘을 제공합니다.
• Mike DeSimone은 세트와 딕셔너리를 권장했으며 목록이 알고리즘 적으로 너무 느린 이유를 설명했습니다. 집합과 사전은 O (1) 조회가있는 해시 테이블로 구현됩니다. 파이썬의 대부분의 문제에 대한 해결책은 실제로 "사전을 사용"하는 것입니다.

두 솔루션 모두 적합하지 않은 경우 타사 모듈로 이동하거나 직접 구현해야합니다.

---

내가 볼 수 있는 한 stdlib에는 이런 종류의 것이 없지만 pypi를 빠르게 살펴보면 몇 가지 대안이 나타납니다 .

• rbtree
• 피 야블
• 블리스트

---

특히 컬렉션에서 가장 작은 요소에 대한 O (1) 액세스 시간을 원하는 경우 stadndard 라이브러리에 있는 heapq 패키지 가 유용하다는 몇 가지 사례 가 있습니다.

저에게는 타이머 모음을 추적하고 있었고 일반적으로 가장 작은 시간 (먼저 실행할 시간)이 아직 준비되었는지 확인하는 데 관심이있었습니다.

---

ubalanced, AVL 및 RB 트리를 지원하는 "bintrees"라는 새 패키지가 있습니다. 여기에서 찾을 수 있습니다 .

---

Sorted Containers 프로젝트 도 확인하세요 .

이에 대한 PyCon 강연 : https://www.youtube.com/watch?v=7z2Ki44Vs4E

---

아니요,하지만 Python 용 AVL 트리 객체 (매우 오래되었습니다!)와 SourceForge에 대한 (닫힌) 프로젝트 가 있습니다-Python 용 avl-trees .

참고 URL : https://stackoverflow.com/questions/2298165/pythons-standard-library-is-there-a-module-for-balanced-binary-tree