자료구조 7강 - 트리와 이진 트리의 이해
트리의 계층 구조와 주요 용어를 익히고, 이진 트리의 종류와 배열·포인터 구현 방법을 살펴본다. 전위·중위·후위 순회의 방문 순서, 노드 삽입·삭제·개수 계산, 일반 트리를 이진 트리로 바꾸는 방법까지 시험에 필요한 흐름으로 정리한다.
01. 트리의 개념과 계층 구조
자료 사이의 상하 관계를 나타내는 구조
트리(tree)는 논리적인 계층이 있는 비선형 자료구조이다. 트리를 구성하는 각 항목을 노드(node)라고 하며, 노드 사이의 상하 관계를 선 또는 링크로 표현한다. 직업을 예술가와 학자로 나누고, 예술가를 다시 음악가와 화가로 구분하는 분류 체계처럼 상위 개념에서 하위 개념으로 갈라지는 자료를 나타내기에 알맞다.
트리는 계층에 따라 검색 범위를 줄일 수 있어 탐색이 편리하고, 상위 항목과 하위 항목의 논리적 관계를 명확히 보여 준다. 파일 시스템, 조직도, 문서 구조, 분류 체계 등이 대표적인 응용이다.
| 용어 | 의미 |
|---|---|
| 부모 노드 | 직접 연결된 두 노드 중 상위 계층의 노드 |
| 자식 노드 | 직접 연결된 두 노드 중 하위 계층의 노드 |
| 루트 노드 | 부모가 없는 트리의 최상위 노드 |
| 내부 노드 | 루트도 잎도 아닌 노드 |
| 잎 노드 | 자신의 서브트리를 갖지 않는 트리 끝의 노드 |
| 형제 노드 | 같은 부모를 갖는 노드 |
| 서브트리 | 어떤 노드의 부모 연결을 제거했을 때 생기는 하위 트리 |
차수, 레벨, 깊이
노드의 진입 차수는 그 노드로 들어오는 선의 수이다. 루트의 진입 차수는 0이고, 루트를 제외한 일반적인 트리 노드의 진입 차수는 1이다. 노드의 진출 차수는 그 노드에서 나가는 선, 즉 자식 수와 같다. 따라서 잎 노드의 진출 차수는 0이다.
노드의 레벨은 루트에서 그 노드까지 이어진 경로의 길이이다. 루트의 레벨은 0이며 바로 아래 자식은 레벨 1이다. 트리의 깊이는 트리에 존재하는 레벨 중 가장 큰 값에 1을 더한 것이다.
시험 핵심: 루트는 부모가 없고 진입 차수가 0이다. 잎 노드는 자식이 없으므로 진출 차수가 0이다. 레벨은 0부터 세지만 깊이는 최대 레벨에 1을 더한다.
02. 트리의 표현 방법과 추상 자료형
다양한 표현 방식
트리는 일반적인 가지 모양뿐 아니라 회전된 모양으로 그릴 수도 있고, 각 서브트리를 포함 관계로 나타내는 중첩 집합이나 들여쓰기 목록으로도 표현할 수 있다. 그림의 방향이 달라도 부모와 자식의 연결 관계가 같다면 같은 트리이다. 따라서 모양보다 노드 사이의 관계를 읽는 것이 중요하다.
트리 추상 자료형
트리 객체는 루트 노드를 갖는 유한 리스트로 정의할 수 있다. 추상 자료형은 실제 저장 방식과 관계없이 트리가 제공해야 할 기능을 연산으로 나타낸다.
| 연산 | 기능 |
|---|---|
| Create() | 트리를 생성하고 루트를 가리키는 포인터를 반환 |
| Destroy(Tree) | 더 사용하지 않는 트리의 기억 공간을 반환 |
| Copy_Tree(Tree) | 트리를 복사하여 새 트리의 루트 포인터를 반환 |
| Insert(n) | 트리에 노드 n을 삽입 |
| Delete() | 트리에서 노드를 삭제하고 필요하면 재구성 |
| Search() | 특정 키를 가진 노드를 찾아 성공 여부를 반환 |
| Traverse() | 정해진 방문 순서로 트리의 값을 반환 |
| Root() | 루트 노드의 값을 반환 |
| Parent(n) | 노드 n의 부모를 반환 |
| Children(n) | 노드 n의 자식들을 반환 |
| IsRoot(n)·IsInternal(n)·IsLeaf(n) | 노드의 종류를 판별 |
| IsEmpty() | 트리가 비어 있는지 검사 |
| Replace(n, m) | 노드 n을 노드 m으로 교체 |
03. 이진 트리의 정의와 종류
자식 수가 최대 두 개인 트리
이진 트리(binary tree)는 모든 노드의 차수가 2 이하인 트리이다. 각 노드는 최대 두 자식만 가지며 두 서브트리를 왼쪽 서브트리와 오른쪽 서브트리로 구분한다. 자식이 하나뿐이어도 왼쪽인지 오른쪽인지에 따라 서로 다른 이진 트리가 된다.
이진 트리는 일반성이 충분하면서도 구조가 단순해 수학적 성질을 정리하기 쉽고 컴퓨터 내부에서 효율적으로 구현할 수 있다.
| 종류 | 정의 | 핵심 구분 |
|---|---|---|
| 가득 찬 이진 트리 | 각 레벨에서 허용되는 최대 개수의 노드를 가진 트리 | 모든 레벨의 자리가 채워짐 |
| 완전 이진 트리 | 높이가 k일 때 레벨 0부터 k-2까지 채우고 마지막 레벨은 왼쪽부터 연속해서 채운 트리 | 마지막 레벨에 빈자리가 생길 수 있으나 왼쪽 정렬 |
가득 찬 이진 트리는 완전 이진 트리이지만, 완전 이진 트리가 항상 가득 찬 것은 아니다. 높이가 h인 가득 찬 이진 트리의 노드 수는 레벨별 1, 2, 4, …의 합으로 2h - 1이다. 여기서 루트 레벨을 0, 깊이 또는 높이를 레벨 수 h로 센다.
완전 이진 트리의 마지막 레벨은 오른쪽에 노드가 있으면서 그보다 왼쪽에 빈자리가 있으면 안 된다. “왼쪽부터 차례로 채운다”가 판별 기준이다.
04. 이진 트리의 구현
배열을 이용한 구현
완전 이진 트리나 가득 찬 이진 트리는 배열에 저장하면 빈 공간이 거의 없어 효율적이다. 일반적인 1번 시작 배열에서 인덱스 i인 노드의 왼쪽 자식은 2i, 오른쪽 자식은 2i+1, 부모는 ⌊i/2⌋ 위치에 놓인다. 그러나 한쪽으로 치우친 트리는 깊이가 증가할수록 사용하지 않는 배열 칸이 2의 거듭제곱 비율로 늘어 공간 낭비가 심해진다.
포인터를 이용한 구현
포인터 방식에서는 각 노드를 왼쪽 자식 포인터, 데이터, 오른쪽 자식 포인터의 세 필드로 구성한다. 자식이 없으면 해당 포인터를 NULL로 둔다. 필요한 노드만 동적으로 만들기 때문에 트리 모양이 불규칙해도 배열처럼 큰 빈 영역이 생기지 않는다.
| 구현 | 장점 | 주의점 |
|---|---|---|
| 배열 | 완전·가득 찬 이진 트리에서 위치 계산이 간단하고 공간 효율이 높음 | 편향 트리에서 빈 칸이 많이 생김 |
| 포인터 | 트리 모양에 맞춰 필요한 노드만 생성 | 각 노드에 두 포인터를 저장해야 함 |
강의의 C 구조체는 개념적으로 node *left, char data, node *right를 가진다. 포인터 기반 순회와 계수 알고리즘은 현재 노드가 NULL인지 먼저 검사한 뒤 왼쪽과 오른쪽 포인터를 재귀적으로 따라간다.
05. 이진 트리의 순회
모든 노드를 빠짐없이 한 번씩 방문하기
순회(traverse)는 이진 트리의 각 노드를 빠짐없이, 중복 없이 한 번씩 방문하는 연산이다. 현재 루트 방문을 P, 왼쪽 서브트리 순회를 L, 오른쪽 서브트리 순회를 R로 나타내면 방문 순서에 따라 전위·중위·후위 순회로 나뉜다.
| 순회 | 방문 순서 | 재귀적 절차 |
|---|---|---|
| 전위 순회 | PLR | 루트 → 왼쪽 서브트리 → 오른쪽 서브트리 |
| 중위 순회 | LPR | 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 |
| 후위 순회 | LRP | 왼쪽 서브트리 → 오른쪽 서브트리 → 루트 |
예제로 순서 계산하기
A가 루트이고 왼쪽 자식 B, 오른쪽 자식 C가 있으며, B의 자식이 D와 E이고 C의 오른쪽 자식이 F인 트리를 생각하자. 전위 순회는 A-B-D-E-C-F, 중위 순회는 D-B-E-A-C-F, 후위 순회는 D-E-B-F-C-A이다.
재귀 알고리즘은 현재 포인터가 NULL이 아닐 때만 실행한다. 전위 함수는 출력 후 왼쪽·오른쪽 재귀 호출, 중위 함수는 왼쪽 호출 후 출력과 오른쪽 호출, 후위 함수는 두 서브트리 호출 후 출력의 순서로 작성한다.
빠른 암기: P의 위치만 보면 된다. P가 앞이면 전위(PLR), 가운데면 중위(LPR), 뒤면 후위(LRP)이다. 왼쪽 L은 세 방식 모두 오른쪽 R보다 먼저 처리한다.
06. 이진 트리의 생성·삽입·삭제와 계수
연결 리스트 연산으로 노드 다루기
포인터 이진 트리는 첫 노드를 생성해 루트로 삼고, 새 노드를 추가할 때 부모의 left 또는 right 포인터가 새 노드를 가리키게 한다. 잎 노드를 삭제할 때는 그 노드를 가리키던 부모 포인터를 NULL로 바꾸고 기억 공간을 반환하면 된다. 내부 노드를 삭제하려면 자식 서브트리가 끊기지 않도록 별도의 재연결 또는 재구성 절차가 필요하다.
재귀를 이용한 개수 계산
전체 노드 수는 현재 노드 1개에 왼쪽과 오른쪽 서브트리의 노드 수를 더해 계산한다. 즉 빈 트리는 0, 빈 트리가 아니면 1 + 왼쪽 노드 수 + 오른쪽 노드 수이다.
잎 노드 수는 현재 노드가 NULL이면 0, left와 right가 모두 NULL이면 1을 반환한다. 내부 노드라면 왼쪽과 오른쪽 서브트리에서 구한 잎 노드 수를 더한다. 이 방식은 트리 전체를 재귀적으로 순회하면서 각 노드의 상태를 판별한다.
내부 노드 삭제를 단순히 NULL 처리하면 그 아래 서브트리 전체에 접근할 수 없게 된다. 삭제 대상이 잎인지 내부 노드인지 먼저 구분해야 한다.
07. 일반 트리를 이진 트리로 변환
왼쪽 자식-오른쪽 형제 표현
자식 수에 제한이 없는 일반 트리도 이진 트리 형태로 바꿀 수 있다. 먼저 같은 부모를 가진 형제 노드를 왼쪽에서 오른쪽 순서로 연결한다. 다음으로 각 부모에서는 가장 왼쪽 자식과의 연결만 남기고 나머지 자식으로 향하는 직접 연결을 제거한다. 마지막으로 루트가 왼쪽 자식만 갖도록 정리하면 각 노드는 최대 두 링크만 갖는다.
변환된 구조에서 left 링크는 원래 트리의 첫 번째 자식을, right 링크는 원래 트리의 다음 형제를 뜻한다. 그래서 이를 왼쪽 자식-오른쪽 형제 방식이라고 한다.
변환 순서: 형제 연결 → 각 노드에서 가장 왼쪽 자식 연결만 유지 → 루트의 형제 연결 제거. 결과적으로 일반 트리의 계층 관계를 두 포인터만으로 표현할 수 있다.
08. 핵심 개념 정리
트리는 노드와 링크로 계층 관계를 표현한다. 루트의 진입 차수는 0, 잎의 진출 차수는 0이며, 깊이는 최대 레벨에 1을 더한 값이다.
이진 트리는 각 노드의 자식 수가 최대 2이다. 가득 찬 이진 트리는 모든 레벨을 채우고, 완전 이진 트리는 마지막 레벨을 왼쪽부터 채운다. 배열은 완전한 형태에, 포인터는 불규칙한 형태에 유리하다.
순회는 전위 PLR, 중위 LPR, 후위 LRP로 구분한다. 노드 수와 잎 수는 NULL과 잎 여부를 기저 조건으로 삼아 재귀적으로 계산한다. 일반 트리는 왼쪽 자식-오른쪽 형제 방식으로 이진 트리로 바꿀 수 있다.
최종 암기: 루트 진입 0 · 잎 진출 0 · 깊이 = 최대 레벨 + 1 · 이진 트리 차수 ≤ 2 · 전위 PLR · 중위 LPR · 후위 LRP · 일반 트리 변환의 left는 첫 자식, right는 다음 형제.
예상문제 20개
1. 트리 자료구조의 가장 중요한 특징은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
트리는 상위와 하위 항목의 계층 관계를 노드와 링크로 나타내는 비선형 구조이다.
2. 트리에서 부모가 없는 노드는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
루트는 트리의 최상위 노드로 부모가 없으며 진입 차수가 0이다.
3. 잎 노드에 대한 설명으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
잎 노드는 자신의 서브트리를 갖지 않는 끝 노드이므로 나가는 선이 없다.
4. 루트의 레벨을 0으로 할 때 트리의 깊이를 구하는 식은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
강의에서는 트리의 깊이를 가장 큰 레벨 값에 1을 더한 것으로 정의한다.
5. 같은 부모를 갖는 노드들의 관계는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
같은 부모의 자식 노드들은 서로 형제 관계이다.
6. 트리 추상 자료형의 Traverse() 연산이 수행하는 일은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
Traverse는 전위·중위·후위처럼 정의된 순서에 따라 노드를 방문한다.
7. 이진 트리의 정의로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
이진 트리의 각 노드는 왼쪽과 오른쪽을 합해 최대 두 자식을 가진다.
8. 완전 이진 트리의 마지막 레벨에 대한 설명으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
완전 이진 트리는 이전 레벨을 채우고 마지막 레벨의 노드를 왼쪽부터 배치한다.
9. 높이가 h인 가득 찬 이진 트리의 노드 수는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
각 레벨의 최대 노드 수 1, 2, 4, …를 h개 레벨까지 합하면 2의 h제곱에서 1을 뺀 값이다.
10. 1번부터 시작하는 배열에서 인덱스 i인 노드의 왼쪽 자식 위치는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
1번 시작 배열에서 왼쪽 자식은 2i, 오른쪽 자식은 2i+1 위치이다.
11. 배열로 편향된 이진 트리를 구현할 때 생기기 쉬운 문제는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
배열 인덱스가 레벨마다 2배씩 벌어져 한쪽으로 긴 트리는 빈 공간을 많이 만든다.
12. 포인터 방식의 이진 트리 노드를 이루는 세 필드는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
각 노드는 데이터와 두 자식 노드를 가리키는 left·right 포인터를 갖는다.
13. 전위 순회의 방문 순서는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
전위 순회는 루트 P를 먼저 방문하고 왼쪽 L, 오른쪽 R의 순서로 진행한다.
14. 중위 순회의 방문 순서는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
중위 순회는 왼쪽 서브트리, 루트, 오른쪽 서브트리 순서이다.
15. 후위 순회의 방문 순서는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
후위 순회는 두 서브트리를 모두 처리한 뒤 마지막에 루트를 방문한다.
16. 루트 A, 왼쪽 B, 오른쪽 C인 이진 트리의 전위 순회 결과는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
전위 PLR에 따라 루트 A를 방문한 뒤 왼쪽 B와 오른쪽 C를 방문한다.
17. 잎 노드를 포인터 이진 트리에서 삭제하는 기본 방법은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
잎은 자식이 없으므로 부모와의 연결을 끊고 해당 노드의 공간을 반환하면 된다.
18. 빈 트리가 아닐 때 전체 노드 수를 재귀적으로 구하는 식은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
현재 노드 하나와 두 서브트리에서 재귀적으로 센 노드 수를 모두 더한다.
19. 일반 트리를 이진 트리로 변환한 구조에서 right 링크가 뜻하는 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
왼쪽 자식-오른쪽 형제 표현에서 left는 첫 자식, right는 다음 형제를 가리킨다.
20. 일반 트리를 이진 트리로 변환할 때 각 부모에 대해 남기는 자식 연결은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
형제들을 오른쪽으로 연결한 뒤 부모에서는 가장 왼쪽 자식과의 직접 연결만 유지한다.
댓글
댓글 쓰기