자료구조 트리와 그래프
목차
- 그래프
- 트리
2-1. 이진트리
2-2. 완전 이진트리
1. 그래프
: 노드와 그 노드를 연결하는 간선(edge)들로 구성된 자료구조
- 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조 Ex. 지하철 노선도, 도로, 검색엔진
- 네트워크 모델
- 노드들 사이에 방향/무방향 경로를 가질 수 있음
- 순환 혹은 비순환
- 방향 그래프와 비방향 그래프
그래프의 용어
용어
- 정점(vertext) : 위치라는 개념
- 간선(edge) : 정점을 연결하는 선
- 인접 정점(adjacent vertex) : 간선에 직접 연결된 정점
- 차수(degree) : 한 정점에 연결된 간선의 수 (주로 무방향 그래프에서 사용)
- 입력 차수(in-degree) : 한 정점으로 들어오는 간선의 수 (주로 방향그래프에서 사용)
- 출력 차수(out-degree) : 한 정점에서 나가는 간선의 수(주로 방향그래프에서 사용)
- 사이클(cycle) : 한 정점에서 출발하여 시작했던 정점으로 돌아오는 경로
- 가중치 그래프 : 간선마다 가중치 값이 매겨져있는 그래프
그래프의 종류
무방향 그래프(Undirected Graph)
- 간선을 통해 양방향으로 갈 수 있다.
정점 A와 정점 B를 연결하는 간선은 (A,B), (B,A)
방향 그래프(Directed Graph)
- 간선에 방향성이 존재하는 그래프
A -> B로 갈 수 있는 간선은 (A, B)로 표시
가중치 그래프(Weighted Graph)
- 간선을 이동하는데 비용이나 가중치가 할당된 그래프
네트워크라고도 함
그래프의 구현방법
- 인접 리스트
- 인접 행렬
2. 트리
: 노드(node)와 브랜치(branch)를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 Ex. 회사의 전체 조직도, 족보
- 계층 모델
- 비순환 그래프
- 노드가 N개인 트리는 항상 N-1개의 간선을 가짐
- 루트 노드가 존재하고, 루트노드를 시작으로 부모와 자식관계가 형성
- 자식노드는 반드시 한개의 부모노드만을 가짐(두 정점 사이에는 반드시 한개의 경로)
트리의 용어
용어
- 루트 노드(root node) : 부모가 없는 노드, 트리는 하나의 루트 노드 만을 가짐
- 단말 노드(leaf node) : 자식이 없는 노드
- 내부(internal) 노드 : 단말 노드가 아닌 노드
- 간선(edge) : 노드를 연결하는 선
- 형제(sibling) : 같은 부모를 가지는 노드
- 조상 노드(ancestors node) : 임의의 노드에서 루트 노드에 이르는 경로상에 있는 노드들 (D의 조상은 B, A이다)
- 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수
- 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 커쳐야하는 간선 수
- 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합
- 노드의 차수(degree) : 각 노드에서 뻗어나온 가지의 수 (D의 차수는 2이다.)
- 트리의 차수(degree of tree) : 트리에서 가장 큰 차수
- 트리의 높이(height) : 가장 깊숙히 있는 노드의 깊이 (3)
트리의 종류 : 이진트리, 이진 탐색 트리, 균형 트리, 이진 힙
2-1. 이진트리
: 자식을 최대 2개만 가지고 있는 트리(모든 노드의 차수가 2 이하인 트리)
- 이진트리와 이진 탐색 트리
- 이진트리 : 루트 노드의 최대 브랜치가 2개인 트리이며, 사이클을 이루지 않도록 구성한 데이터 구조
- 이진 탐색 트리 : 이진 트리 + 추가 조건 (왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음) Ex. 데이터 검색
2-2. 완전 이진트리(+ 불완전 이진트리)
이미지 출처 : https://www.techiedelight.com/ko/check-given-binary-tree-complete-binary-tree-not/
완전 이진트리 : 부모노드에서 시작해, 좌측에서부터 채워져 있는 구조
그래프와 트리 비교
그래프 | 트리 | |
---|---|---|
정의 | 노드와 노드를 연결하는 간선으로 표현되는 자료 구조 | 그래프의 한 종류, 방향성이 있는 비순환 그래프 |
핵심 표현 | 개체간의 ‘관계’ 표현 | 개체를 ‘계층’ 그조로 표현 |
방향성 | 방향 그래프, 무방향 그래프 둘 다 존재함 | 방향 그래프만 존재함 |
사이클 | 사이클 가능함, 순환 및 비순환 그래프 모두 존재함 | 비순환 그래프로 사이클이 존재하지 않음 |
루트 노드 | 루트 노드 존재하지 않음 | 루트 노드 존재함 |
부모/자식 관계 | 부모 자식 개념이 존재하지 않음 | 부모 자식 관계가 존재함 |
출처