AVL이나 레드블랙 트리 같이 항상 logN을 보장하는 트리들을 균형 트리라고 합니다.
C++, Jaav 등을 비롯한 많은 상용 프로그래밍 언어들에서는 이들을 내장 라이브러리에 지원하고 있습니다. Python 3에서는 이런 구조를 지원하지 않아서 (파이썬의 대가인) jh05013 님께서는 스킵 리스트를 하나 구현해놓고 복붙해서 사용하신다고 들었습니다.
일반적인 이진 탐색 트리는 말씀하신 최악의 케이스 때문에 (그리고 그 최악의 케이스를 만들기 쉽기 때문에) 문제를 푸는 데에 있어서는 거의 실용성이 없다고 보시면 됩니다. 균형 이진 트리를 지원하지 않는 언어라면 아쉽지만 직접 구현해서라도 최악의 경우를 대비하는 수밖에 없습니다.
www6698 5년 전
제가 알고리즘을 공부하면서 시간복잡도와 공간복잡도에 대해서 알게되었습니다.
그러다가 자료구조별 시.공간 복잡도에 대해서 찾아보았는데 예를들어
트리 자료구조가 있습니다. Binary Search Tree는 최악일때 상당히 느려서 사용을 안하는거 같지만
B-Tree나 AVL-Tree, Red Black-Tree 는 전부 log N 으로 시공간 복잡도가 같더라구요?
만약 어떤 알고리즘을 구현해야되는데 자료구조를 트리를써야된다! 라면 셋중 자신이 제일 구현 잘 할수 있는것으로 구현하면 되는건가요??
아니면 전부다 또 제가 모르는 장단점들이 다 있는건가요??
요약: 트리 알고리즘 중 시간복잡도가 같으면 아무거나 사용해도 무방한가요?