이진 탐색트리란? - BST (Binary Search Tree) 그림 1. 이진 탐색트리 (이미지 출처 : 위키피디아) 이진 탐색트리는 트리 구조로써 한 노드가 자신보다 작은 값을 가진 Left Child와 자신보다 큰 값을 가진 Right Child 두 노드를 가지는 구조를 말한다. 탐색 시에 값의 대소비교를 통해 자식 노드를 탐색하면서 값을 찾아내므로 탐색 횟수가 일반적인 트리구조(한쪽으로 치우쳐 있지 않은)의 깊이인 log 2의 N과 같다고 볼 수 있기 때문에 O(log N)의 시간 복잡도를 가진다. 이진 탐색 트리의 특징 1. 이진 탐색트리는 DFS로 탐색하며 값을 출력했을 경우 오름차순으로 출력된다는 특징이 있다. 2. 이미 정렬되어 있는 값을 넣는 경우, 한쪽으로 치우치게 자식이 만들어지므로..