www6698   2년 전

제가 알고리즘을 공부하면서 시간복잡도와 공간복잡도에 대해서 알게되었습니다.

그러다가 자료구조별 시.공간 복잡도에 대해서 찾아보았는데 예를들어

트리 자료구조가 있습니다. Binary Search Tree는 최악일때 상당히 느려서 사용을 안하는거 같지만

B-Tree나 AVL-Tree, Red Black-Tree 는 전부 log N 으로 시공간 복잡도가 같더라구요?

만약 어떤 알고리즘을 구현해야되는데 자료구조를 트리를써야된다! 라면 셋중 자신이 제일 구현 잘 할수 있는것으로 구현하면 되는건가요??

아니면 전부다 또 제가 모르는 장단점들이 다 있는건가요??

요약: 트리 알고리즘 중 시간복잡도가 같으면 아무거나 사용해도 무방한가요?

djm03178   2년 전

AVL이나 레드블랙 트리 같이 항상 logN을 보장하는 트리들을 균형 트리라고 합니다.

C++, Jaav 등을 비롯한 많은 상용 프로그래밍 언어들에서는 이들을 내장 라이브러리에 지원하고 있습니다. Python 3에서는 이런 구조를 지원하지 않아서 (파이썬의 대가인) jh05013 님께서는 스킵 리스트를 하나 구현해놓고 복붙해서 사용하신다고 들었습니다.

일반적인 이진 탐색 트리는 말씀하신 최악의 케이스 때문에 (그리고 그 최악의 케이스를 만들기 쉽기 때문에) 문제를 푸는 데에 있어서는 거의 실용성이 없다고 보시면 됩니다. 균형 이진 트리를 지원하지 않는 언어라면 아쉽지만 직접 구현해서라도 최악의 경우를 대비하는 수밖에 없습니다.

www6698   2년 전

음... 그럼 결론은 트리 구현할때 균형트리 종류중 아무거나 써도 무방하다는 건가요?

djm03178   2년 전

실용적으론 RB 트리를 많이 쓰는 것으로 알고 있습니다. B 트리를 이런 용도로 쓰는지는 잘 모르겠네요.

www6698   2년 전

RB트리를 구현할 정도의 실력? 이 되면 아마 어느 트리도 구현할 수 있을거 같다고 생각이 드네요.. 야밤에 답변해주셔서 감사합니다.

댓글을 작성하려면 로그인해야 합니다.