🌳 트리(Tree) 관련 예상 질문
1. 트리(Tree)와 그래프(Graph)의 차이를 설명해보세요.
- 그래프는 순환이 있을 수 있지만, 트리는 항상 하나의 루트에서 시작하며 사이클이 없는 계층적 구조입니다.
2. 이진 트리(Binary Tree), 정 이진 트리(Full), 포화 이진 트리(Perfect), 완전 이진 트리(Complete)의 차이를 설명해보세요.
- 이진트리는 각 노드가 최대 두개의 자식을 가지는 트리이고, 정 이진 트리는 모든 노드가 자식을 0개 또는 2개만 가지며, 포화 이진트리는 모든 레벨이 꽉찬 이진 트리를 뜻합니다. 마지막으로 완전 이진 트리는 마지막 레벨만 제외하고 꽉 차 있으며, 마지막 레벨은 왼쪽부터 채워진 이진트리를 뜻합니다.
3. 트리 순회 방법에는 어떤 것이 있나요?
- 트리 순회 방법으로는 깊이를 먼저 탐색하는 DFS와 너비를 우선적으로 탐색하는 BFS가 있습니다. DFS로는 전위순회, 중위순회, 후위순회가 있으며 전위 순회는 루트 -> 왼쪽 -> 오른쪽 순으로 순회하며 중위 순회는 왼쪽 -> 루트 -> 오른쪽 순, 후위 순회는 왼쪽 -> 오른쪽 -> 루트 순으로 순회합니다.
BFS로는 레벨 순회가 있습니다. 레벨 순회는 위에서 아래, 왼쪽에서 오른쪽으로 순회하며 낮은 레벨에 있는 노드를 모두 방문 후 다음 레벨 노드를 방문합니다.
4. 힙(Heap)은 어떤 트리 구조를 기반으로 하나요?
- 힙은 완전 이진 트리 구조를 기반으로 구현합니다. 완전 이진 트리란 마지막 레벨을 제외하고 꽉 차있으며, 마지막 레벨은 왼쪽부터 채워진 이진 트리입니다.
🌲 이진 탐색 트리(BST) 관련 예상 질문
1. 이진 탐색 트리(BST)의 정의와 특징을 설명해보세요.
- 이진 탐색 트리란 정렬된 이진 트리로, 루트를 기준으로 왼쪽 서브 트리에는 부모 노드보다 작은 값이 위치하며, 오른쪽 서브트리에는 부모 노드보다 큰 값이 위치한 트리입니다.
2. BST에서 탐색/삽입/삭제의 평균·최악 시간 복잡도는 각각 얼마인가요
- BST의 탐색/삽입/삭제 모두 트리가 균형 잡힌 상태일때의 평균은 O(log n)이고, 트리가 한쪽으로 치우친 상태일 경우 최악 O(n)입니다.
3. BST가 한쪽으로 치우치면 성능이 어떻게 되나요?
- 사실상 연결리스트가 되어 탐색/삽입/삭제 모두 O(n)까지 떨어집니다.
4. BST 삭제 연산 시 자식 노드가 2개인 경우는 어떻게 처리하나요?
- successor노드를 사용하여 삭제합니다. successor노드란 오른쪽 서브트리의 최소값을 말하며, 우선 삭제할 노드를 찾고, 삭제할 노드의 successor 노드를 찾습니다. 그후 삭제할 노드와 successor 노드의 값을 바꾼 후, 노드를 삭제합니다.
5. BST에서 중위 순회를 하면 어떤 결과가 나오나요?
- 정렬된 오름차순 결과가 나옵니다.
⚖️ 균형 이진 탐색 트리 관련 확장 질문
1. BST가 불균형해지는 문제를 해결하는 방법은 무엇이 있나요?
- AVL 트리나 레드블랙트리 같은 균형 이진 탐색 트리를 사용합니다.
2. AVL 트리와 Red-Black 트리의 차이를 설명해보세요.
- AVL 트리란 말단 노드의 레벨 차이가 항상 1 이하로 나는 트리이며, 노드 삽입/삭제 후 자동으로 균형을 유지하기 위해 회전 연산을 사용합니다. 높이 균형을 엄격하게 유지하며 탐색이 빠릅니다.
레드-블랙 트리는 모든 노드가 레드, 블랙의 색을 가지는 트리로, 균형을 느슨하게 유지하며 삽입/삭제에 효율적이며 라이브러리에 많이 사용됩니다.
3. 왜 RBT가 라이브러리 구현에서 더 많이 쓰일까요?
- 라이브러리는 삽입/삭제/탐색이 골고루 일어나므로 탐색 성능이 조금 더 빠른 것보다 삽입/삭제를 안정적으로 보장하는것이 더중요하므로 유지 비용이 적은 RBT가 적합합니다.
4. Java의 TreeMap, TreeSet은 어떤 자료구조로 구현되어 있나요?
- RBT로 구현되어 있습니다.
배우고 기록하며 성장하는 백엔드 개발자입니다!