Optimal Binary Search Tree
-
Optimal Binary Search Tree자료구조 2019. 9. 5. 15:35
어떠한 자료를 트리를 사용해 저장할때 많이 검색되는 단어가 leaf쪽에 있으면 검색 비용이 높음 따라서 검색 빈도에 따라 비용을 최소화 할 수 있는 트리를 구현 어떤 트리가 있을때 이 트리가 Optimal이면 양쪽의 subtree도 optimal이라는 아이디어로 접근 시간복잡도는 O(n^2) 점화식: https://gsmesie692.tistory.com/116 최적 이진 탐색 트리 (Optimal Binary Search Tree) 이전 포스팅에서 설명했던 이진 탐색 트리 (BST) 의 활용 예를 보자. 설명할 때는 보통 이해하기 쉽게 노드에 들어있는 데이터를 숫자로 가정하지만, 실제로 쓰일 때는 문자열이라던가 더 다양한 데이터가 들어갈.. gsmesie692.tistory.com