최적 이진 검색 트리란? 최적 이진 검색트리의 뜻을 알기위해서는 먼저 이진 검색 트리의 뜻을 알아야한다. 이진 검색 트리는 말 그대로 이진 트리를 검색 목적으로 사용하는 것이다. 왼쪽에는 같거나 더 작은 값을, 오른쪽에는 더 큰 값을 저장하고 leaf 노드들 간의 depth 차이가 1보다 클 수 없다. 여기서 '최적'이란 단어까지 붙으면 최적 이진 검색트리가 된다. 최적 이진 검색 트리는 가능한 이진 검색 트리 중 key를 찾는데에 걸리는 평균 시간이 가장 짧은 이진 검색 트리를 의미한다. 탐색시간은 원하는 키를 찾기까지 필요한 비교 횟수이다. 평균 탐색시간은 한 노드에 담긴 keym이 찾고자하는 search key일 확률을 pm라고 하고, keym을 찾기까지의 비교횟수를 cm이라고 할 때 pm과 cm의..