[컴퓨터과학개론] 4. 자료구조(2)

워터파슬리 2022. 10. 10. 16:15

2022. 10. 10. 16:15

728x90

💡 현실 세계에서 다루는 데이터들을 추상화(자료구조화)하기 위해서는 트리와 그래프가 훨씬 더 많이 사용됨

1. 트리 용어 정의

✅ 트리

데이터 간의 관계를 나타내는 비선형 자료구조(데이터 간의 관계가 1:n) ↔ (선형 자료구조: 데이터 간의 관계가 1:1:1)
노드(node)라고 불리는 부분과 노드를 연결하는 가지(branch, edge)로 구분됨
노드 사이에는 계층적인 관계성을 가짐

트리 용어 정리
노드(node)	- 정보 항목을 의미함
루트(root)	- 빈 트리가 아닌 경우에 맨 꼭대기에 있는 하나의 노드
차수(degree)	- 각 노드에 있는 가지의 수
잎 노드(leaf node)	= 단말 노드(terminal node) - 노드의 차수가 0인 노드
내부 노드(internal node)	= 비단말 노드(non-terminal node) - 루트 노드와 단말 노드를 제외한 나머지 노드
조상(선조) 노드	- 루트 노드로부터 어떤 노드 X까지의 경로(가지들의 모음) 상에 존재하는 모든 노드를 X의 조상 노드라고 함 예) K의 조상 노드 = E, B, A
자손(후손) 노드	- 어떤 노드 X에서 단말 노드까지의 경로 상에 존재하는 모든 노드를 자손 노드라고 함 예) C의 자손 노드 = G, H, I, L, M
레벨(level)	- 루트 노드로부터의 거리(가지의 수)를 의미함
트리의 깊이(depth)/높이(height)	- 루트 노드로부터 가장 긴 경로에 있는 단말 노드의 레벨에 1의 값을 더한 것(예: 깊이:4)
서브 트리(subtree)	- 특정 노드를 루트 노드로 하고, 그 아래에 있는 열결된 구조의 트리
숲(forest)	- n개의 서브 트리를 가진 트리에서 루트 노드를 제거해서 얻을 수 있는 분리된 서브 트리의 집합 (위 트리의 경우 3개의 숲을 가질 수 있음)

2. 이진 트리

✅ 이진 트리(binary tree)

트리 중에서 차수가 2인 트리
모든 노드의 차수는 최대 2를 넘지 않음
모든 노드는 최대 2개의 서브 트리를 가짐(각 서브 트리는 왼쪽/오른쪽 서브 트리로 구분)
왼쪽 노드와 오른쪽 노드에 '순서'의 의미를 부여함 → 왼쪽과 오른쪽을 구분함으로써 편하게 의사소통하고 효율적으로 알고리즘을 만들 수 있어!
이진 트리의 각 서브 트리는 다시 이진 트리가 됨

✅ 이진 트리의 높이

N개의 노드를 가진 이진 트리의 높이를 계산으로 구할 수 있음
트리는 높이가 낮을 수록 검색 속도가 빨라짐(비교 횟수가 줄어듬)

최대 높이	최소 높이
- N으로 노드의 개수와 같음	- 최대 2개의 자식 노드를 갖는 경우로서 [log₂ N]+1이 높이(레벨+1)가 됨

✅ 이진 트리 순회 연산 (암기)

일정한 순서에 따라 트리에 있는 각 노드를 한 번씩 방문하는 것
1. 전위 순회: DLR
2. 중위 순회: LDR
3. 후위 순회: LRD

Data Left Right (전위 순회; preorder)

A B D H I E J K C F L M G N O
루트노드 방문 → 왼쪽 서브 트리 방문 → 오른쪽 서브 트리 방문

Left Data Right (중위 순회; inorder)

H D I B J E K A L F M C N G O
왼쪽 서브트리 방문 → 루트 노드 방문 → 오른쪽 서브 트리 방문

Left Right Data (후위 순회; postorder)

H I D J K E B L F M N O G C A
왼쪽 서브 트리 방문 → 오른쪽 서브 트리 방문 → 루트 노드 방문

✅ 포화 이진 트리(full binary tree)

깊이가 k인 이진 트리 중에서 노드의 개수가 2^k - 1개인 이진 트리
- 즉, 깊이가 k인 이진 트리가 가질 수 있는 노드의 최대 개수는 2^k - 1개이며, 단말 노드의 개수가 2^k-1개
각 레벨에서 빈자리가 없이 노드를 모두 가지고 있음
모든 내부 노드들은 2개의 자식 노드를 가짐

✅ 완전 이진 트리(complete binary tree)

트리의 최대 레벨이 k 일 때, 레벨 k-1까지는 포화 이진 트리를 형성하고, 레벨 k에서는 왼쪽부터 오른쪽으로 채워진 트리

총 노드의 개수가 2^k+1 -1을 초과하지 않으면서, 포화 이진 트리의 노드 번호에 해당하는 연속적인 번호를 갖는 트리
포화 이진 트리는 완전 이진 트리에 속함 ↔ 완전 이진 트리는 포화 이진 트리가 될 수 없음

✅ 경사 이진 트리(skewed binary tree)

한 쪽(왼쪽/오른쪽) 방향으로만 가지가 뻗어 나간 경사 이진 트리
검색 시간 등 여러 가지 측면에서 수행 시간을 늘려나감 = 비효율적

3. 그래프

✅ 그래프 G

정점(vertex)들의 유한 집합 V와 두 개의 정점을 연결하는 간선(edge)들의 유한 집합 E로 정의
G=(V,E)로 표시

무방향 그래프(undirected graph)	방향 그래프(directed graph, digraph)

간선이 방향성이 없는 간선으로 연결된 그래프 V(G1)={1,2,3,4} E(G1)={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)} *정점의 차수(degree): 정점에 부수된 간선의 개수	두 정점을 연결하는 간선이 방향성을 가지는 간선으로 연결된 그래프 V(G2)={1,2,3,4} E(G2)={<1,2>,<1,3>,<3,2>,<3,4>,<4,1>,<4,2>} 정점의 차수(degree) - 진입 차수(indegree): 다른 정점에서 해당 정점을 향하는 간선의 개수 - 진출 차수(outdegree)*: 해당 정점으로부터 다른 정점으로 향하는 간선의 개수

🔸용어 정리

두 정점이 간선으로 직접 연결되어 있으면 두 정점은 인접(adjacent)해 있다고 하며, 해당 간선은 두 정점에 부수(incident) 되었다고 함
- '인접한다': 정점 간의 관계
- '부수되었다': 정점과 간선 간의 관계
경로(path): 간선으로 연결된 정점들의 순차적 나열을 의미함
경로의 길이: 경로에 포함된 간선의 개수
단순 경로(simple path): 경로 상에 존재하는 정점들이 모두 다른 경로
사이클(cycle): 세 개 이상의 정점을 가진 경로 중에서 시작 정점과 끝 정점이 같은 경로 (예: 1,2,1 또는 1,2,3,4,2,1)
단순 사이클(simple cycle): 시작 정점과 끝 정점을 제외하고 모든 정점이 다른 사이클 (예:1,2,3,4)
'두 정점은 서로 연결되었다': 두 정점 사이에 경로가 존재함
'그래프가 서로 연결되었다': 무방향 그래프에서 서로 다른 모든 정점들 사이에 경로가 존재함
방향 그래프에서 적어도 두 정점 사이에 어느 한 쪽으로만 경로가 존재할 때, 약하게 연결되었다고 함
트리는 그래프의 특수한 형태로 봄
- 무방향 그래프에서 모든 정점이 서로 연결되어 있으면서 사이클이 존재하지 않는 그래프를 트리라고 함

4. 그래프의 표현

인접 행렬(adjacency matrix)	인접 리스트(adjacency list)
출처: 한국방송통신대학교

그래프를 컴퓨터 프로그래밍 언어로 구현하기 위해서는 인접 행렬(adjacency matrix)이나 인접 리스트(adjacency list)를 이용하여 표현함
인접 행렬을 이용하여 n개의 정점을 가진 그래프를 표현하기 위해서는 n*n 크기의 2차원 배열을 이용함
- 인접 행렬 A[i][x]에 값(1)이 존재하면 그래프의 정점 Vᵢ에서 정점 Vₓ 사이에 간선이 존재함을 의미

✅ 그래프의 탐색

그래프의 모든 정점을 체계적으로 방문하는 것

깊이 우선 탐색(depth first search)	너비 우선 탐색(breadth first search)
- 최근에 방문하지 않은 인접한 하나의 정점을 우선적으로 방문함 - 최종 방문 순서는 (1,2,4,5,7,6,3) 이지만 이는 구현 방법에 따라 달라질 수 있음	- 최근에 방문하지 않은 인접한 모든 정점을 모두 방문함 - 최종 방문 순서는 (1,2,3,4,5,6,7) 이지만 이는 구현 방범에 따라 달라질 수 있음