🤔 면접 질문
Q1. BST는 어떤 자료구조 인가요?
A1. 이진탐색트리(Binary Search Tree; BST)는 정렬된 tree입니다. 어느 node를 선택하든 해당 node의 left subtree에는 그 node의 값보다 작은 값들을 지닌 node들로만 이루어져 있고, node의 right subtree에는 그 node의 값보다 큰 값들을 지닌 node들로만 이루어져 있는 binary tree입니다.
검색과 저장, 삭제의 시간 복잡도는 모두 O(logn)이고, worst case는 한쪽으로 치우친 tree가 됐을 때 O(n)입니다.
💡 면접🐕🍯 tip
BST는 저장과 동시에 정렬을 하는 자료구조이다. 따라서 새로운 데이터를 저장할 때 일정한 규칙에 따라 저장을 하게 된다. Heap을 공부했었을 때와 마찬가지로, 저장하는 방식을 그림으로 설명할 수 있으면 좋다. 이진 탐색 트리가 되기 위한 조건이 무엇인지, 시간 복잡도, worst case, worst case가 발생하지 않게 하기 위해서는 어떻게 해야하는지를 대답할 수 있으면 된다. BST는 자주 나오면서 꽤 어려운 자료구조이기 때문에 충분한 학습을 하고 면접을 보러 가길 바란다.
1️⃣ BST
2️⃣ BST 조건
- root node의 값보다 작은 값은 left subtree에 큰 값은 right subtree에 있다.
- subtree도 1번 조건을 만족한다.(=Recursive)
🚀 심화 면접 질문
Q1.이진트리(Binary tree)는 어떤 자료구조 인가요?
A1. 모든 node의 child nodes의 갯수가 2 이하인 트리를 이진트리라고 합니다.
Q2. BST의 worst case 시간 복잡도는 O(n)입니다. 어떠한 경우에 worst case가 발생하나요?
A2. 균형이 많이 깨져서 한 쪽으로 치우친 BST의 경우에 worst case가 됩니다. 이렇게 되면 Linked list와 다를게 없어집니다. 따라서 탐색시에 O(logn)이 아니라 O(n)이 됩니다.
Q3. A2의 해결방법은 무엇인가요?
A3. 자가 균형 이진 탐색 트리(Self-Balancing BST)는 알고리즘으로 이진 트리의 균형이 잘 맞도록 유지하여 높이를 가능한 낮게 유지합니다. 대표적으로 AVL tree와 Red-black tree가 있습니다. Java에서는 hashmap의 seperate chaning으로써 Linked list와 Red-black tree를 병행하여 저장합니다.