[핵심 답변]
이진탐색트리(Binary Search Tree; BST)는 정렬된 tree입니다. 어느 node를 선택하든 해당 node의 left subtree에는 그 node의 값보다 작은 값들을 지닌 node들로만 이루어져 있고, node의 right subtree에는 그 node의 값보다 큰 값들을 지닌 node들로만 이루어져 있는 binary tree입니다.
검색과 저장, 삭제의 시간복잡도는 모두 이고, worst case는 한쪽으로 치우친 tree가 됐을 때 입니다.
[ 면접 
TIP]
TIP]BST는 저장과 동시에 정렬을 하는 자료구조입니다. 따라서 새로운 데이터를 저장할 때 일정한 규칙에 따라 저장을 하게 됩니다. Heap을 공부했었을 때와 마찬가지로, 저장하는 방식을 그림으로 설명할 수 있으면 좋습니다.
이진탐색트리가 되기 위한 조건이 무엇인지, 시간복잡도, worst case, worst case가 발생하지 않게 하기 위해서는 어떻게 해야하는지를 대답할 수 있으면 됩니다.
BST는 자주 나오면서 꽤 어려운 자료구조이기 때문에 충분한 학습을 하고 면접을 보러 가시길 바랍니다.
BST
BST 조건
1.
root node의 값보다 작은 값은 left subtree에, 큰 값은 right subtree에 있다.
2.
subtree도 1번 조건을 만족한다.(Recursive)
search
[꼬꼬무 문답]
Q. 이진트리(Binary tree)는 어떤 자료구조 인가요?
Q. BST의 worst case 시간복잡도는 입니다. 어떠한 경우에 worst case가 발생하나요?
Q. 해결방법은 무엇인가요?