이진 탐색 트리
2019.10.21
이진 탐색트리란? 이진 탐색트리는 다음과 같은 속성이 있는 자료 구조이다. 각 노드에 값이 있고, 각 노드마다 최대 두 개의 자식을 갖는다. 왼쪽 자식은 부모보다 키 값이 작고, 오른쪽 자식은 부모보다 키 값이 크다. 이진 탐색트리 예시 {8,3,10,1,6,14,4,7,13} 이 노드를 기준으로, 루트 8 의 왼쪽 서브트리는 3부터 그 이하의 노드들로 이루어진 트리이고, 루트 8 의 오른쪽 서브트리는 10부터 그 밑에있는 노드들로 이루어진 트리이다. 이진 탐색 트리는 유일하지 않다. 예를 들어 {1, 2, 3, 4}에 대한 이진 탐색 트리는 이런식으로 두가지 이상으로 표현 가능하다. 만약 어떤 키 값이 자주 접근될 지 모른다면, 균형잡힌 오른쪽 트리가 유리할 것이고, 만약 1 값이 가장 자주 접근된다면..