방송대 방통대 컴퓨터과학개론 6강 - 알고리즘 (2) - 요약 노트 시험족보 예상문제 - 올에이클래스

컴퓨터과학개론 6강 - 알고리즘 (2)

분할정복을 이용하는 퀵 정렬과 합병 정렬의 처리 과정 및 수행 시간을 학습한다. 이어서 순차 탐색과 이진 탐색을 비교하고, 이진 탐색 트리의 성질과 탐색·삽입·삭제 연산 및 트리 모양에 따른 성능 차이를 정리한다.

1. 퀵 정렬의 원리와 분할 과정

퀵 정렬(quick sort)은 특정 데이터를 기준으로 입력 배열을 두 부분배열로 분할하고, 각 부분배열에 같은 정렬 방법을 순환적으로 적용하는 정렬 알고리즘이다. 문제를 더 작은 문제로 나누어 해결한 결과로 전체 문제를 해결한다는 점에서 분할정복(divide and conquer) 방법에 해당한다.

배열을 나누는 기준 데이터는 피벗(pivot) 또는 분할 원소라고 한다. 분할을 마치면 피벗은 정렬된 배열에서 자신이 들어갈 최종 위치를 잡는다. 이때 피벗의 왼쪽 부분배열에는 피벗보다 작은 값들이, 오른쪽 부분배열에는 피벗보다 큰 값들이 놓이도록 데이터를 교환한다.

퀵 정렬의 한 번의 분할 결과는 왼쪽 부분배열의 모든 값 < 피벗 < 오른쪽 부분배열의 모든 값이라는 관계로 요약할 수 있다.

피벗을 첫 원소로 선택한 분할

강의록에서는 배열의 첫 원소를 피벗으로 선택한다. 왼쪽에서 오른쪽으로 이동하는 위치 표시자 L은 피벗보다 큰 값 또는 같은 값을 찾고, 오른쪽에서 왼쪽으로 이동하는 위치 표시자 R은 피벗보다 작은 값을 찾는다. L < R이면 두 위치의 데이터를 교환하고 탐색을 계속한다. 두 위치가 엇갈려 L > R이 되면 피벗과 R 위치의 데이터를 교환하여 피벗을 제자리에 놓는다.

단계	처리 내용
피벗 선택	부분배열의 첫 원소를 피벗으로 정한다.
왼쪽 탐색	L을 오른쪽으로 이동하며 피벗보다 크거나 같은 값을 찾는다.
오른쪽 탐색	R을 왼쪽으로 이동하며 피벗보다 작은 값을 찾는다.
데이터 교환	L < R이면 두 데이터를 교환하고 탐색을 반복한다.
분할 완료	L > R이면 피벗과 R 위치를 교환한다.

예를 들어 [30, 45, 20, 15, 40, 25, 35, 10]에서 30을 피벗으로 선택하면 분할 과정에서 45와 10, 40과 25가 차례로 교환된다. 위치 표시자가 엇갈린 뒤 피벗 30과 25를 교환하면 [25, 10, 20, 15, 30, 40, 35, 45]가 된다. 이제 30의 왼쪽과 오른쪽 부분배열을 각각 다시 퀵 정렬하면 된다.

한 번의 분할만으로 전체 배열이 정렬되는 것은 아니다. 다만 피벗은 최종 위치가 확정되며, 피벗을 제외한 두 부분배열에 같은 과정을 반복함으로써 전체 정렬이 완성된다.

2. 퀵 정렬의 특징과 수행 시간

퀵 정렬의 분할 단계는 피벗을 중심으로 정렬할 데이터를 두 부분배열로 나눈다. 정복 단계에서는 두 부분배열에 퀵 정렬을 순환적으로 적용한다. 별도의 합병 과정은 필요하지 않는데, 분할 과정 자체에서 피벗의 위치가 확정되고 두 부분배열의 값 범위가 구분되기 때문이다.

경우	분할 형태	수행 시간
최선	피벗을 중심으로 두 부분배열의 크기가 거의 같게 나뉨	O(n log n)
평균	피벗 선택이 특정 방향에 치우치지 않고 비교적 고르게 나뉨	O(n log n)
최악	피벗만 제자리를 잡고 나머지가 하나의 부분배열에 몰림	O(n²)

최선의 경우에는 크기 n인 배열이 매 단계에서 약 n/2씩 나뉜다. 분할의 깊이는 약 log n이 되고, 각 단계에서 전체적으로 n개 정도의 데이터를 비교하므로 수행 시간은 O(n log n)이다.

최악의 경우는 피벗이 부분배열에서 계속 최솟값이나 최댓값이 되는 경우이다. 이미 오름차순으로 정렬된 배열에서 첫 원소를 계속 피벗으로 고르는 상황이 대표적이다. 이때 부분배열의 크기가 0과 n-1로 불균형하게 나뉘는 과정이 반복되어 O(n²)이 된다.

퀵 정렬은 평균적으로 빠르지만 피벗 선택과 입력 상태에 따라 성능 차이가 크다. 피벗 선택의 임의성이 보장되면 평균 수행 시간인 O(n log n)을 보일 가능성이 높아진다.

3. 합병 정렬의 원리와 합병 과정

합병 정렬(merge sort)은 입력 배열을 동일하거나 거의 동일한 크기의 두 부분배열로 분할하고, 각 부분배열을 순환적으로 정렬한 다음, 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만드는 방식이다. 퀵 정렬과 마찬가지로 분할정복 방법을 적용하지만, 정렬된 결과를 만드는 핵심 작업이 합병 단계에 있다는 차이가 있다.

1. 배열을 크기가 같은 두 부분배열로 분할한다.
2. 각 부분배열에 합병 정렬을 순환적으로 적용한다.
3. 정렬된 두 부분배열을 하나의 정렬된 배열로 합병한다.

분할은 각 부분배열의 원소가 하나가 될 때까지 계속된다. 원소가 하나인 배열은 이미 정렬된 것으로 볼 수 있으므로, 이후에는 인접한 두 부분배열을 합병한다. 합병할 때에는 두 부분배열의 맨 앞 원소를 비교하여 더 작은 값을 결과 배열에 옮기고, 선택된 쪽의 다음 원소와 다시 비교한다.

정렬된 두 부분배열의 합병

정렬된 배열 A=[34, 41, 54, 89]와 B=[16, 23, 52, 67]을 합병한다고 하자. 먼저 34와 16을 비교하여 16을 결과 배열 C에 저장한다. 이어서 34와 23, 34와 52를 비교하는 식으로 진행하면 C=[16, 23, 34, 41, 52, 54, 67, 89]가 된다.

합병 단계의 입력인 두 부분배열은 반드시 각각 정렬되어 있어야 한다. 이 조건 덕분에 각 부분배열의 맨 앞 원소만 비교하면서 전체를 순서대로 합칠 수 있다.

합병 정렬은 입력 배열의 상태와 관계없이 분할 깊이가 약 log n이고 각 단계의 합병에 전체적으로 n의 작업이 필요하다. 따라서 최선·평균·최악 수행 시간이 모두 O(n log n)이다.

비교 항목	퀵 정렬	합병 정렬
공통 원리	분할정복 방법을 적용한다.
분할 기준	피벗을 중심으로 값의 크기에 따라 분할	위치를 기준으로 비슷한 크기의 두 배열로 분할
합병 과정	별도의 합병이 필요 없음	정렬된 두 부분배열을 합병해야 함
최악 수행 시간	O(n²)	O(n log n)

4. 탐색과 순차 탐색

탐색(search)은 주어진 데이터 집합에서 원하는 값을 가진 데이터를 찾는 작업이다. 찾으려는 값을 탐색키(search key)라고 한다. 강의록에서는 순차 탐색, 이진 탐색, 이진 탐색 트리를 이용한 탐색을 다룬다.

탐색 방법	기본 조건과 방법	주요 성능
순차 탐색	처음부터 차례대로 비교하며 정렬이 필요 없음	O(n)
이진 탐색	정렬된 배열의 탐색 범위를 절반씩 줄임	O(log n)
이진 탐색 트리	키의 대소 관계에 따라 왼쪽 또는 오른쪽 서브트리로 이동	평균 O(log n), 최악 O(n)

순차 탐색의 처리 과정

순차 탐색(sequential search)은 리스트의 처음부터 데이터를 하나씩 차례대로 탐색키와 비교하는 방법이다. 배열 [60, 20, 50, 70, 30, 10, 40]에서 30을 찾는다면 인덱스 0부터 비교하여 인덱스 4에서 탐색에 성공한다.

탐색에 실패하면 리스트의 모든 원소를 비교하므로 비교 횟수는 n번이다. 탐색에 성공하는 경우에는 위치에 따라 1번부터 n번까지 비교하며, 각 위치에서 발견될 가능성이 같다고 보면 평균 비교 횟수는 (n+1)/2번이다. 따라서 순차 탐색의 시간 복잡도는 O(n)이다.

순차 탐색은 배열과 연결 리스트 등 모든 리스트에 적용할 수 있고 데이터가 정렬되지 않아도 된다. 데이터가 자주 바뀌거나 연속적으로 저장되지 않은 경우에도 사용할 수 있다는 점이 장점이다.

5. 이진 탐색의 원리와 특징

이진 탐색(binary search)은 정렬된 입력 배열에서 탐색 대상의 범위를 절반씩 줄여 가며 원하는 값을 찾는 방법이다. 현재 탐색 범위의 왼쪽 끝을 Left, 오른쪽 끝을 Right라고 하면 가운데 인덱스는 Mid=(Left+Right)/2로 정한다.

비교 결과	다음 처리
key = A[Mid]	탐색에 성공하고 Mid를 반환한다.
key < A[Mid]	가운데 값보다 작은 왼쪽 부분배열을 다시 탐색한다.
key > A[Mid]	가운데 값보다 큰 오른쪽 부분배열을 다시 탐색한다.

정렬된 배열 [10, 15, 20, 25, 30, 35, 40, 45, 50]에서 35를 찾는 과정을 살펴보자. 처음에는 Mid=4이고 가운데 값 30이 탐색키보다 작으므로 오른쪽 부분배열로 이동한다. 다음 Mid=6의 값 40은 탐색키보다 크므로 왼쪽으로 범위를 줄인다. 마지막으로 Mid=5에서 35를 찾아 탐색에 성공한다.

탐색을 한 번 반복할 때마다 대상 원소의 수가 절반으로 감소하므로 이진 탐색의 수행 시간은 O(log n)이다. 그러나 입력 데이터가 이미 정렬되어 있어야 적용할 수 있다. 또한 배열에서 삽입과 삭제가 발생하면 정렬 상태를 유지하기 위해 여러 데이터를 이동해야 하므로 동적인 연산이 많은 응용에는 부담이 될 수 있다.

순차 탐색은 정렬 여부와 관계없이 사용할 수 있지만 O(n)이고, 이진 탐색은 정렬이 필요하지만 O(log n)이다. 탐색 속도만이 아니라 데이터의 정렬 상태와 삽입·삭제 빈도까지 함께 고려해야 한다.

6. 이진 탐색 트리와 탐색·삽입 연산

이진 탐색 트리(binary search tree)는 각 노드를 기준으로 왼쪽과 오른쪽 서브트리의 키값 관계가 정해진 이진 트리이다. 각 노드의 왼쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 작고, 오른쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 크다.

• 왼쪽 서브트리의 모든 키값 < 부모 노드의 키값
• 부모 노드의 키값 < 오른쪽 서브트리의 모든 키값

탐색 연산

탐색은 루트 노드에서 시작한다. 탐색키가 현재 노드의 키값과 같으면 성공한다. 탐색키가 더 작으면 왼쪽 서브트리로, 더 크면 오른쪽 서브트리로 이동하여 비교를 반복한다. 더 이동할 자식 노드가 없는데도 일치하는 값을 찾지 못하면 탐색에 실패한다.

예를 들어 루트가 35인 트리에서 44를 찾는다면 44는 35보다 크므로 오른쪽의 55로 이동한다. 44는 55보다 작으므로 왼쪽 자식 44로 이동하여 탐색에 성공한다.

삽입 연산

새 데이터를 삽입할 때에도 먼저 해당 키를 탐색한다. 같은 값이 이미 존재하면 강의록의 처리에서는 탐색 성공 상태에서 종료한다. 값이 없다면 탐색이 실패한 빈 위치에 새 노드를 자식 노드로 추가한다.

루트가 35이고 왼쪽에 30, 그 왼쪽에 15와 오른쪽에 22가 있는 트리에 25를 삽입한다고 하자. 25는 35보다 작아 왼쪽으로, 30보다 작아 다시 왼쪽으로, 15보다 커서 오른쪽으로, 22보다 커서 오른쪽으로 이동한다. 그 위치가 비어 있으므로 22의 오른쪽 자식으로 25를 삽입한다.

7. 이진 탐색 트리의 삭제와 성능

이진 탐색 트리의 삭제는 삭제할 노드가 가진 자식 노드의 개수에 따라 방법이 달라진다. 삭제 후에도 모든 노드에서 왼쪽 키값은 작고 오른쪽 키값은 크다는 이진 탐색 트리의 성질이 유지되어야 한다.

삭제할 노드의 상태	삭제 방법
자식이 없는 단말 노드	다른 노드의 위치를 조절하지 않고 해당 노드만 삭제한다.
자식이 하나인 노드	자식 노드를 삭제되는 노드의 위치로 올리고 그 아래 서브트리도 함께 연결한다.
자식이 둘인 노드	삭제되는 노드의 후속자 노드를 해당 위치로 올리고, 후속자 노드는 자신의 자식 수에 따라 다시 처리한다.

후속자 노드(successor, 계승자 노드)는 어떤 노드의 키값 바로 다음 키값을 갖는 노드이다. 이진 탐색 트리의 키들을 작은 값부터 나열했을 때 삭제 대상 바로 뒤에 오는 값이라고 이해할 수 있다. 자식이 둘인 노드를 삭제할 때 후속자를 올리면 키값의 순서 관계를 유지할 수 있다.

이진 탐색 트리 연산의 수행 시간은 루트부터 비교하며 이동한 경로의 길이, 즉 트리 높이에 비례한다. 트리가 비교적 균형을 이루면 높이가 약 log n이므로 탐색·삽입·삭제의 평균 수행 시간은 O(log n)이다. 반면 키가 한쪽 방향으로 삽입되어 연결 리스트처럼 기울어진 경사 이진 트리가 되면 높이가 n에 가까워져 최악 수행 시간은 O(n)이 된다.

이진 탐색 트리의 성능은 노드 수만으로 결정되지 않는다. 같은 노드 수라도 균형 잡힌 트리는 빠르고, 한쪽으로 치우친 트리는 순차 탐색과 비슷한 성능까지 저하될 수 있다.

핵심 개념 정리

• 퀵 정렬은 피벗을 기준으로 작은 값과 큰 값을 나누고 두 부분배열을 순환적으로 정렬한다.
• 퀵 정렬은 평균 O(n log n)이지만 극단적으로 불균형한 분할이 반복되면 O(n²)이다.
• 합병 정렬은 비슷한 크기로 나누고, 정렬된 두 부분배열을 합병하며 모든 경우 O(n log n)이다.
• 순차 탐색은 정렬이 필요 없고 모든 리스트에 적용할 수 있지만 수행 시간은 O(n)이다.
• 이진 탐색은 정렬된 배열의 범위를 절반씩 줄이므로 O(log n)이다.
• 이진 탐색 트리는 왼쪽 키 < 부모 키 < 오른쪽 키의 관계를 만족한다.
• 이진 탐색 트리의 삭제는 자식 수가 0개, 1개, 2개인 경우로 나누어 처리한다.
• 이진 탐색 트리는 평균 O(log n)이지만 경사 트리가 되면 최악 O(n)이다.

시험 대비 최종 정리: 정렬에서는 퀵 정렬의 피벗 분할과 최악 O(n²), 합병 정렬의 분할 후 합병과 항상 O(n log n)을 구분해야 한다. 탐색에서는 순차 탐색의 무정렬·O(n), 이진 탐색의 정렬 필수·O(log n), 이진 탐색 트리의 평균 O(log n)·경사 상태 최악 O(n)을 연결하여 기억한다.

예상문제 20선

1. 퀵 정렬에서 배열을 두 부분배열로 나누는 기준 데이터는 무엇인가?

① 피벗 ② 탐색키 ③ 후속자 ④ 루트

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
퀵 정렬은 피벗 또는 분할 원소를 기준으로 작은 값과 큰 값을 두 부분배열로 나눈다.

2. 퀵 정렬의 한 번의 분할이 완료된 직후 피벗에 대한 설명으로 옳은 것은?

① 항상 배열의 첫 위치로 이동한다. ② 정렬된 배열에서 자신의 최종 위치를 잡는다. ③ 두 부분배열에서 모두 제거된다. ④ 반드시 전체 배열의 최솟값이 된다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
분할이 끝나면 피벗 왼쪽에는 작은 값, 오른쪽에는 큰 값이 놓이므로 피벗의 최종 위치가 확정된다.

3. 퀵 정렬의 최악 수행 시간은 무엇인가?

① O(1) ② O(log n) ③ O(n²) ④ O(n³)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
피벗을 기준으로 배열이 계속 0개와 n-1개처럼 불균형하게 나뉘면 퀵 정렬은 O(n²)이 된다.

4. 퀵 정렬에서 최선의 성능을 기대할 수 있는 분할 형태는?

① 모든 값이 왼쪽 부분배열에 들어간다. ② 피벗이 항상 최솟값이다. ③ 부분배열의 크기가 0과 n-1이다. ④ 두 부분배열의 크기가 거의 같게 나뉜다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
균형 있게 분할되면 순환 호출의 깊이가 약 log n이 되어 O(n log n)의 성능을 보인다.

5. 합병 정렬의 처리 순서로 가장 적절한 것은?

① 분할 → 각 부분배열의 순환적 정렬 → 합병 ② 합병 → 피벗 선택 → 분할 ③ 탐색 → 삽입 → 삭제 ④ 피벗 교환 → 합병 → 순차 탐색

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
합병 정렬은 배열을 나누고 각 부분을 정렬한 뒤 정렬된 두 부분배열을 하나로 합친다.

6. 합병 정렬의 최선·평균·최악 수행 시간으로 옳은 것은?

① 모두 O(n) ② 모두 O(n log n) ③ 모두 O(n²) ④ 각각 O(1), O(n), O(n²)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
합병 정렬은 입력 상태와 관계없이 비슷한 분할과 합병 과정을 수행하므로 세 경우 모두 O(n log n)이다.

7. 퀵 정렬과 합병 정렬의 공통점은?

① 정렬되지 않은 데이터에는 적용할 수 없다. ② 반드시 피벗을 사용한다. ③ 분할정복 방법을 적용한다. ④ 최악 수행 시간이 항상 O(n²)이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
두 알고리즘 모두 큰 배열을 작은 부분배열로 나누고 순환적으로 해결하는 분할정복 방식이다.

8. 합병 정렬의 합병 단계에 들어가는 두 부분배열이 갖추어야 할 조건은?

① 두 배열의 모든 값이 같아야 한다. ② 두 배열이 연결 리스트여야 한다. ③ 첫 원소가 피벗이어야 한다. ④ 각 부분배열이 이미 정렬되어 있어야 한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
두 부분배열이 각각 정렬되어 있어야 맨 앞 값들을 비교하는 방식으로 올바르게 합병할 수 있다.

9. 순차 탐색에 대한 설명으로 옳은 것은?

① 데이터가 정렬되지 않아도 적용할 수 있다. ② 매번 탐색 범위를 절반으로 줄인다. ③ 평균 수행 시간은 O(log n)이다. ④ 배열에는 적용할 수 없다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
순차 탐색은 리스트의 처음부터 차례로 비교하므로 사전 정렬이 필요 없다.

10. 원소 수가 n인 리스트에서 순차 탐색이 실패할 때 비교 횟수는?

① 1번 ② n번 ③ log n번 ④ n²번

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
값이 없다는 사실을 확인하려면 마지막 원소까지 모두 비교해야 하므로 n번 비교한다.

11. 이진 탐색을 적용하기 위한 필수 조건은?

① 데이터가 모두 서로 같아야 한다. ② 데이터가 트리 형태여야 한다. ③ 입력 배열이 정렬되어 있어야 한다. ④ 원소 수가 짝수여야 한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
가운데 값과 탐색키의 대소 관계로 한쪽 절반을 제외하려면 배열이 정렬되어 있어야 한다.

12. 이진 탐색에서 key < A[Mid]인 경우 다음에 탐색할 범위는?

① 전체 배열 ② 가운데 원소 하나 ③ 오른쪽 부분배열 ④ 왼쪽 부분배열

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
정렬된 배열에서 탐색키가 가운데 값보다 작으면 탐색키는 가운데 값의 왼쪽에 있을 수 있다.

13. 이진 탐색의 수행 시간이 O(log n)인 주된 이유는?

① 비교할 때마다 탐색 대상이 절반으로 감소하기 때문이다. ② 모든 데이터를 한 번씩 비교하기 때문이다. ③ 피벗을 무작위로 선택하기 때문이다. ④ 두 배열을 합병하기 때문이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
한 번 비교할 때마다 남는 후보가 약 절반이 되므로 반복 횟수는 원소 수의 로그에 비례한다.

14. 이진 탐색 트리의 성질로 옳은 것은?

① 왼쪽 서브트리의 모든 키는 부모보다 크다. ② 오른쪽 서브트리의 모든 키는 부모보다 크다. ③ 모든 단말 노드의 키는 서로 같다. ④ 루트는 항상 전체 키의 최솟값이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
이진 탐색 트리에서는 왼쪽 서브트리의 키가 부모보다 작고 오른쪽 서브트리의 키가 부모보다 크다.

15. 이진 탐색 트리에서 탐색키가 현재 노드의 키보다 작을 때 이동할 곳은?

① 부모 노드 ② 오른쪽 서브트리 ③ 왼쪽 서브트리 ④ 무조건 루트 노드

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
부모보다 작은 키들은 왼쪽 서브트리에 있으므로 탐색키가 작으면 왼쪽으로 이동한다.

16. 이진 탐색 트리에 존재하지 않는 새 키를 삽입하는 위치는?

① 항상 새로운 루트 위치 ② 키의 크기와 관계없는 임의 위치 ③ 현재 트리의 가장 왼쪽 위치 ④ 탐색이 실패한 빈 자식 위치

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
삽입할 키를 탐색하다가 더 이동할 노드가 없는 위치를 만나면 그 빈 자리에 새 노드를 연결한다.

17. 자식이 없는 이진 탐색 트리의 노드를 삭제하는 방법은?

① 다른 노드를 이동하지 않고 해당 노드만 삭제한다. ② 반드시 루트 노드와 교환한다. ③ 왼쪽 서브트리 전체를 삭제한다. ④ 후속자 노드의 두 자식을 모두 삭제한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
자식이 없는 단말 노드는 연결된 하위 트리가 없으므로 그 노드만 제거하면 된다.

18. 자식이 하나인 노드를 삭제할 때의 처리로 옳은 것은?

① 자식 노드도 함께 삭제한다. ② 자식 노드를 삭제되는 노드의 위치로 올린다. ③ 트리의 모든 키를 다시 정렬한다. ④ 무조건 후속자 노드를 새로 생성한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
하나뿐인 자식과 그 서브트리를 삭제 대상의 위치에 연결하면 탐색 트리의 관계를 유지할 수 있다.

19. 이진 탐색 트리에서 후속자 노드의 의미는?

① 트리에서 가장 작은 키를 가진 노드 ② 삭제 대상의 부모 노드 ③ 어떤 노드의 키값 바로 다음 키값을 가진 노드 ④ 항상 삭제 대상의 왼쪽 자식 노드

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
후속자는 키를 오름차순으로 나열했을 때 해당 노드 바로 다음에 오는 키를 가진 노드이다.

20. 이진 탐색 트리의 수행 시간이 최악의 경우 O(n)이 되는 상황은?

① 트리가 완전히 균형을 이룬 경우 ② 루트에만 값이 있는 경우 ③ 모든 단말 노드의 깊이가 같은 경우 ④ 노드가 한쪽으로 치우친 경사 이진 트리가 된 경우

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
경사 이진 트리의 높이는 노드 수에 비례하므로 루트에서 단말까지 최대 n개에 가까운 노드를 비교할 수 있다.