Optimal Binary Search Tree

자료구조 2019. 9. 5. 15:35

어떠한 자료를 트리를 사용해 저장할때

많이 검색되는 단어가 leaf쪽에 있으면 검색 비용이 높음

따라서 검색 빈도에 따라 비용을 최소화 할 수 있는 트리를 구현

어떤 트리가 있을때 이 트리가 Optimal이면 양쪽의 subtree도 optimal이라는 아이디어로 접근

시간복잡도는 O(n^2)

점화식:

최적 이진 탐색 트리 (Optimal Binary Search Tree)

이전 포스팅에서 설명했던 이진 탐색 트리 (BST) 의 활용 예를 보자. 설명할 때는 보통 이해하기 쉽게 노드에 들어있는 데이터를 숫자로 가정하지만, 실제로 쓰일 때는 문자열이라던가 더 다양한 데이터가 들어갈..

gsmesie692.tistory.com

무제 무제