2021년 3회 정보처리기사 기출문제 37번

37. 다음 중 최악의 경우 검색 효율이 가장 나쁜트리 구조는?

❶ 이진 탐색트리      ② AVL 트리

③ 2-3 트리               ④ 레드-블랙 트리

 

이 문제는 검색 효율이 가장 나쁜 트리 구조에 대한 질문입니다. 각 트리 구조의 검색 효율이 최악의 경우 어떻게 될지에 대해 살펴보겠습니다.

각 트리 구조에 대한 설명

1. 이진 탐색 트리 (Binary Search Tree, BST)
   • 이진 탐색 트리는 각 노드가 두 개 이하의 자식 노드를 가지고, 왼쪽 자식 노드는 부모보다 작은 값, 오른쪽 자식 노드는 부모보다 큰 값을 가지는 트리입니다.
   • 최악의 경우: 트리가 한쪽으로 치우쳐진 상태(예: 삽입 순서가 정렬된 순서일 때)에서는, 트리가 리스트처럼 변형되고, 검색 효율이 **O(n)**이 됩니다.
2. AVL 트리
   • AVL 트리는 자기 균형 이진 탐색 트리로, 각 노드에 대해 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 유지됩니다. 이로 인해 트리의 높이가 항상 균형을 이루어 검색 효율이 보장됩니다.
   • 최악의 경우: 균형이 맞춰져 있기 때문에 검색 효율은 항상 **O(log n)**입니다.
3. 2-3 트리
   • 2-3 트리는 균형 이진 트리로, 각 노드가 2개 또는 3개의 자식을 가질 수 있습니다. 모든 리프 노드는 같은 깊이에 위치해 있어서, 트리의 높이가 항상 균형을 이룹니다.
   • 최악의 경우: 이 트리도 균형이 맞춰져 있으므로 검색 효율은 항상 **O(log n)**입니다.
4. 레드-블랙 트리
   • 레드-블랙 트리는 자기 균형 이진 탐색 트리로, 각 노드는 빨간색 또는 검은색을 가지고 있으며, 몇 가지 규칙을 통해 균형을 유지합니다. 이는 AVL 트리처럼 균형을 유지하므로 검색 효율이 높습니다.
   • 최악의 경우: 레드-블랙 트리의 검색 효율은 **O(log n)**입니다.

결론

최악의 경우, 검색 효율이 가장 나쁜 트리 구조는 이진 탐색 트리입니다. 이진 탐색 트리가 한쪽으로 치우친 상태가 되면, 그 **검색 효율이 O(n)**이 되어 리스트와 동일해지기 때문에, 가장 나쁜 효율을 가집니다.

정답: ① 이진 탐색트리