그래프와 트리
31 Mar 2021많이 들어봤지만 자꾸 헷갈리는 그래프와 트리.. 이번에 한번 정리해보자.
트리(Tree)
트리 구조는 그래프의 일종으로 순환 구조를 갖지 않는 그래프이다. 또한, 부모노드에서 자식노드로 내려가는 단방향의 1:N 구조로 계층형 자료구조이다. 한개 이상의 노드로 이루어진 유한 집합이며 아래의 조건을 만족한다.
- 노드 중 가장 최상위 노드를 루트라 ,부른다.
- 루트노드를 제외한 나머지 노드들은 간선의 수만큼 n개의 분리집합(T1 ~ Tn)으로 분리할 수 있다. 이들 T1~Tn은 각각 하나의 트리가 되며 루트의 부 트리라 한다.
트리의 구성요소
- 노드(node) : 트리의 원소
- 간선(edge) : 노드를 연결하는 선으로 부모 노드와 자식 노드를 연결
- 루트 노드(root node) : 최상위 노드
- 차수(degree)
노드의 차수 : 노드에 연결된 자식 노드의 수(=간선의 개수)
트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
- 단말노드 : 차수가 0인 노드. 즉, 자식 노드가 없는 노드
- 높이
노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨
트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값. 최대 레벨
이진 트리
알고리즘 문제를 풀 때 주로 많이 만드는 형태로, 모든 노드들이 자식 노드를 최대 2개까지만 갖는 특별한 형태의 트리이다. 이 트리의 특징으로는
- 레벨 i에서 노드의 최대 개수는 2^i 개
- 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는
h+1개, 최대 개수는2^(h+1)-1개
이진트리의 종류로는
- 포화 이진 트리 : 모든 레벨에 포화 상태로 차있는 이진트리
- 완전 이진 트리 : 높이가 h이고 노드의 수가 n일때 노드 번호 1~n까지 빈자리가 없는 이진 트리
- 편향 이진 트리 : 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진트리
그래프(Graph)
그래프는 비선형 자료구조 중 N:N의 관계를 나타낼 수 있는 자료구조이다. 정점과 간선으로 연결 관계를 표현할 수 있다.
그래프의 구성요소
- 정점(vertex) : 하나의 연결점
- 간선(edge) : 두 정점을 연결하는 선
- 차수(degree) : 정점에 연결된 간선의 수
그래프의 종류
- 방향성에 따라 : 무향 그래프(방향성이 없음, 양방향), 유향 그래프(방향성이 있음, 단방향)
- 가중치에 따라 : 가중치그래프(관계의 정도를 수치화)
- 사이클 유무에 따라 : 사이클이 있는 방향 그래프, 사이클이 없는 방향 그래프
- 간선의 형태에 따라 : 완전 그래프(정점에 대해 가질 수 있는 모든 간선을 가짐), 부분 그래프(일부 간선만 가짐)