728x90
반응형
- 각 노드의 검색 빈도가 주어질 때, 검색 비용의 기댓값이 가장 작은 이진 검색 트리
예시)
입력이 5,4,6,3,2,8,7 순일 경우
균형적인 트리
입력이 1,2,3,4,5 순일 경우
불균형적인 트리
위처럼 1,2,3,4,5 순으로 입력이 있을 경우
입력이 있을때마다 트리를 최적화하여 아래와 같이 만든다.
이리하여 이진 탐색 트리 중에서 평균 검색 시간이 가장 낮은 효율적인 트리가 된다.
참고 출처
RememberCook 9월 28일 정식 출시!
두번째 게임인 RememberCook이 출시되었습니다. 귀여운 캐릭터들이 나오는 간단한 게임이며 플레이어의 공간인지능력을 테스트하는 게임입니다. 아래 링크를 통해 다운 받으실 수 있으니 많은 관��
chipmunk-plump-plump.tistory.com
반응형
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| BFS - 너비 우선 탐색 (C#으로 길 찾기 구현) (0) | 2021.01.22 |
|---|---|
| AStar Algorithm (에이스타 알고리즘) (2) | 2020.12.07 |
| binary search tree (이진 탐색 트리) (9) | 2020.05.11 |
| Heap Sort (힙 정렬) (2) | 2020.04.20 |
| Merge Sort (병합정렬) (0) | 2020.04.20 |
