# 이진 탐색 트리 (Binary Search Tree - BST)

• 이진 트리의 조건을 만족한다.
• 부모 노드를 기준으로 왼쪽 자식 노드는 작은 값, 오른쪽 자식 노드는 큰 값을 가진다.
• 동시에 부모 노드를 기준으로 왼쪽 서브트리 전체의 각 값이 기준 부모 노드보다 작아야 한다.
• 위와 마찬가지로 오른쪽 서브트리 전체의 값이 부모 노드보다 작아야 한다.

아래의 < 그림 1 >을 참고하여, 위 사항들을 되짚어 보자.

< 그림 1 >

이진 탐색 트리는,

• 평균적으로 시간 복잡도가 O(log n)이다.
• 치우친 경우(skewed), O(n)이 될 수 있다. 그래서 균형이 중요하다.