1. 트리(Tree)
- 비선형 구조 중 하나
- 데이터를 계층적으로 구조화 하여 저장하는 자료 구조
- 노드(Node)들과 노드들을 연결하는 링크(Link)들로 구성됨.
root, branch, leaf가 연결되어 있다.
central node, structural node, sub-node가 edge를 통해 연결되어 있다. - 노드(node)들 간에 계층적인 관계를 가지고 있다.
- 재귀 구조(Recursive Structure)를 형성
- 각 노드는 여러 개의 자식 노드(child node)를 가질 수 있다.
그리고 이러한 자식 노드(child node) 또한 자식 노드(child node)를 가질 수 있다. - 루트 노드(root node)와 0개 이상의 하위 트리(sub-tree)로 구성된다.
- 각 노드는 여러 개의 자식 노드(child node)를 가질 수 있다.
용어
노드(Node)
루트 노드(Root Node) : 부모가 없는 노드
1이 루트 노드
리프 노드(Leaf Node = 외부 노드; External Node = 터미널 노드) : 자식이 없는 노드
3,4,5가 리프 노드
인터널 노드(Internal Node) : 적어도 하나의 자식 자식 노드를 가지는 노드
노드는 키와 자손을 가리키는 참조변수를 갖는다.
- 키(Key) : 노드가 저장하는 값
기타 용어
하위(부분) 트리(Sub-tree)
노드 X의 하위 트리(sub-tree)
노드 X를 조상(ancestor)로 갖는 모든 노드들로 구성된다.
노드 X와 노드 X의 모든 자손(descendant) 노드들로 구성된다.2와3으로 이루어진 트리가 서브트리이다.
간선(Edge = Link = Branch) : 노드와 노드를 연결하는 선
레벨(Level) : 0이나 1부터 시작
높이(height) : 트리에 존재하는 서로 다른 레벨의 총 개수
- 레벨
0,1,2가 존재하므로 높이(height)는 3이다.
- 레벨
깊이(Depth) : 루트 노드부터 현재 노드까지 오는데 거치는 간선의 개수
- 현재 노드가
3이라면 깊이(depth)는 2이다.
- 현재 노드가
차수(Degree) : 자식 노드의 총 수 = 한 노드가 가진 서브 트리의 수
- 루트 노드의 차수는 자식 노드의
- 차수(degree)가 가장 높은 노드는
1로 차수(degree)가 3이다. 2의 차수(degree)는 1- 트리의 차수(Degree of tree) : 트리의 최대 차수
1의 차수, 3
크기(size) : 자신을 포함한 모든 자손 노드의 개수
1의 크기(size)는 4이다.2의 크기(size)는 2이다.
노드 간의 관계
부모(Parent) : branch로 연결된 2개의 노드(node) 중, 위의 노드가 부모(parent) 노드이다.
루트 노드를 제외한 모든 노드는 하나의 부모(parent)를 갖는다.자식(child) : branch로 연결된 2개의 노드(node) 중, 아래 노드가 자식(child) 노드이다.
2,4,5는1의 자식 노드(child node)1은2,4,5의 부모 노드(parent node)- 루트 노드(root node)인
1은 부모 노드(parent node)를 가지지 않는다.
형제(Sibling) : 부모 노드(parent node)가 같은 노드들을 형제(sibling)라고 한다.
2,4,5는 같은 부모 노드(parent node =1)를 가지고 있으므로 서로 형제(sibling)이다.
이웃(Neighbor) : 현재 노드의 부모(parent) 또는 자식(child) 노드들을 이웃(neighbor)이라고 한다.
조상(Ancestor) : 현재 노드에 대한 루트 경로의 모든 선행 노드
자손(Descendant) : 노드 X가 노드 Y의 조상이다. ⇔ 노드 Y는 노드 X의 자손이다.
3은1의 자손1은3의 조상
노드의 표현
트리는 노드들의 모음으로 표현할 수 있다.
public static class Node {
int data;
Node first_child;
Node second_child;
Node third_child;
...
Node nth_child;
}중요성(Importance)
1. 자연스럽게 계층 구조를 형성하는 데이터를 저장할 수 있다.
예시
- 조직도
- 컴퓨터 파일 시스템에서의 디렉토리와 서브디렉토리 : 내 컴퓨터\C:\Program Files)
- 가계도
2. (BST 같은 )트리는 적당한 액세스/검색을 제공한다.
LinkedList보다는 빠르고 Array보다는 느림
3. 트리는 적당한 삽입/삭제 기능을 제공한다.
Array보다 빠르고 순서가 없는 LinkedList보다는 느림
4. LinkedList와 같이(Array와는 달리) 트리는 노드가 포인터를 사용하여 연결되므로 노드를 무수히 많이 연결할 수 있다.
유형
각 노드가 가질 수 있는 자식 노드의 수에 따라 3가지 종류로 나뉜다.
이미지 출처: Geeksforgeeks | Introduction to Tree – Data Structure and Algorithm Tutorials
이진 트리(Binary Tree) : 각 노드가 최대 2개의 자식 노드를 가질 수 있다.
데이터를 저장하는데 매우 효율적이며 검색 알고리즘과 정렬 알고리즘, 데이터 구조에 유용하게 사용됩니다.
삼항 트리(Ternary Tree) : 각 노드가 최대 3개의 자식 노드를 가질 수 있다.
일반적으로
left,mid,right로 구분된다.N-ary Tree(= Generic Tree) : 각 노드가 자식 노드들에 대한 레코드와 참조 리스트로 구성된 자료 구조인 노드의 모음(중복 참조는 허용되지 않음)
LinkedList와 달리 각 노드는 여러 노드의 주소를 저장
영어가 제대로 해석된 건지 잘 모르겠어서 영문도 첨부합니다.
Generic trees are a collection of nodes where each node is a data structure that consists of records and a list of references to its children(duplicate references are not allowed).
기본 연산
- 생성(Create) : 자료 구조에 트리를 생성
- 삽입(Insert) : 트리에 데이터를 삽입
- 검색(Search) : 트리에서 특정 데이터를 검색하여 존재 여부를 확인
- 순회(Traversal)
- 깊이 우선 탐색(DFS; Depth First Search Traversal)
- 너비 우선 탐색(BFS; Breadth First Search Traversl)
구현
import java.io.*;
import java.util.*;
public class GFG {
public static void printParents(int node, Vector<Vector<Integer>> adj, int parent) {
// 부모노드가 0이면 루트 노드임을 나타냄.
if (parent == 0) {
System.out.println(node + " -> Root");
} else {
System.out.println(node + " -> " + parent);
}
// DFS(깊이 우선 탐색)
for (int i = 0; i < adj.get(node).size(); i++) {
if (adj.get(node).get(i) != parent) {
printParents(adj.get(node).get(i), adj, node);
}
}
}
public static void printChildren(int Root, Vector<Vector<Integer>> adj) {
// BFS(너비 우선 탐색)를 위한 Queue
Queue<Integer> q = new LinkedList<>();
q.add(Root);
// vis Array to keep track of nodes that have been visited
// node를 방문했으면 1
// node를 방문하지 않았으면 0
int vis[] = new int[adj.size()];
Arrays.fill(vis, 0);
//BFS
while(q.size() != 0) {
int node = q.peek();
q.remove();
vis[node] = 1;
System.out.print(node + " -> ");
for (int i = 0; i < adj.get(node).size(); i++) {
if (vis[adj.get(node).get(i)] == 0) {
System.out.print(adj.get(node).get(i) + " ");
q.add(adj.get(node).get(i));
}
}
System.out.println();
}
}
public static void printLeafNodes(int Root, Vector<Vector<Integer>> adj) {
// 리프 노드는 간선이 1개, 그리고 루트 노드가 아님.
for (int i = 1; i < adj.size(); i++) {
if (adj.get(i).size() == 1 && i != Root) {
System.out.print(i + " ");
}
}
System.out.println();
}
// 차수(Degree)는 자식 노드의 총 수
public static void printDegrees(int Root, Vector<Vector<Integer>> adj) {
for (int i = 1; i < adj.size(); i++) {
System.out.print(i + " : ");
// 루트 노드는 부모 노드가 없고 자식 노드만 존재하므로 차수는 adj.get(i).size()
// 그 외의 노드는 부모 노드와 자식 노드 모두 존재 하므로 차수는 adj.get(i).size() - 1
if (i == Root) {
System.out.println(adj.get(i).size());
} else {
System.out.println(adj.get(i).size() - 1);
}
}
}
public static void main(String[] args) {
int N = 7, Root = 1;
Vector<Vector<Integer>> adj = new Vector<Vector<Integer>>();
for (int i = 0; i < N + 1; i++) {
adj.add(new Vector<Integer>());
}
// 키가 n1인 노드와 키가 n2인 노드가 간선으로 연결되어 있으면
// adj.get(n1)는 n2을 포함함.
// adj.get(n2)는 n1을 포함함.
// 즉, adj.get(n)에는 n의 부모 노드와 자식 노드를 모두 포함.
adj.get(1).add(2);
adj.get(2).add(1);
adj.get(1).add(3);
adj.get(3).add(1);
adj.get(1).add(4);
adj.get(4).add(1);
adj.get(2).add(5);
adj.get(5).add(2);
adj.get(2).add(6);
adj.get(6).add(2);
adj.get(4).add(7);
adj.get(7).add(4);
System.out.println("The parents of each node are: ");
printParents(Root, adj, 0);
System.out.println("The children of each node are: ");
printChildren(Root, adj);
System.out.println("The leaf nodes of the tree are: ");
printLeafNodes(Root, adj);
System.out.println("The degrees of each node are: ");
printDegrees(Root, adj);
}
}
// This code is contributed by rj13to.Output
The parents of each node are:
1 -> Root
2 -> 1
5 -> 2
6 -> 2
3 -> 1
4 -> 1
7 -> 4
The children of each node are:
1 -> 2 3 4
2 -> 5 6
3 ->
4 -> 7
5 ->
6 ->
7 ->
The leaf nodes of the tree are:
3 5 6 7
The degrees of each node are:
1 : 3
2 : 2
3 : 0
4 : 1
5 : 0
6 : 0
7 : 0기본 성질
- 간선의 수(Number of edges) : 한 간선은 두 노드 사이의 연결로 정의된다.
- 노드가 `N`개인 트리는 항상 `N - 1`개의 간선(link)를 가진다.
트리의 각 노드에서 다른 노드까지의 경로는 유일하다.
(단, 같은 노드를 두번 이상 방문하지 않는다는 조건이 전제되어야 한다.)
- 노드의 깊이(Depth of a Node) : 루트에서 해당 노드까지의 경로의 길이
노드의 깊이 = 루트 노드에서 해당 노드까지의 경로에 있는 간선의 수
∵ 각 간선은 경로에 길이 1을 추가하는 것을 의미
- 노드의 높이(Height of a Node) : 노드에서 트리의 리프 노드까지 가장 긴 경로의 길이
- 트리의 높이(Height of the Tree) : 트리의 루트에서 트리의 리프 노드까지의 가장 긴 경로의 길이
- 노드의 차수(Degree of a Node) : 해당 노드에 연결된 하위 트리의 총 개수
- 리프 노드의 차수는 0이다.
- 트리의 차수(Degree of the Tree) : 트리의 모든 노드 중 해당 노드의 최대 차수
응용
- 파일 시스템 : 효율적으로 탐색 및 구성
- 데이터 압축 : 허프만 코딩으로 구현된 트리는 필요한 저장 공간을 최소화하는 방식으로 데이터를 인코딩하는 데 사용된다.
- 컴파일러 디자인 : 프로그램의 구조를 나타내는 데 Syntax Tree를 사용한다.
- 데이터베이스 인덱싱 : B-Tree 및 기타 트리 구조를 이용하여 데이터를 효율적으로 검색, 탐색한디.
장점
- 트리를 이용한 효율적인 검색은 트리의 유형에 따라 다르며, AVL같은 균형 트리의 평균 검색 시간은 O(log n)이다.
- 트리는 데이터의 계층적 표현을 제공하여 많은 양의 정보를 쉽게 구성, 탐색 할 수 있다.
- 트리의 재귀적 특성으로 인해 재귀 알고리즘을 이용한 트리의 탐색과 조작이 쉽다.
단점
- 불균형 트리(Unbalanced Trees) : 트리의 높이가 한쪽으로 치우져있어 검색 시간이 비효율적일 수 있다.
- 트리는 Arrays나 LinkedList같은 자료 구조보다 많은 메모리 공간을 필요로 하며 특히, 트리가 클 수록 그러하다.
- 트리의 구현과 조작이 복잡할 수 있으며 알고리즘에 대한 이해를 필요로 한다.
📚 References(참고 자료)
Codewhoop | Trees Introduction
[Algorithm] 트리의 개념과 용어정리
[Java] 트리 자료구조의 개념과 구현
트리 소개 – 데이터 구조 및 알고리즘 튜토리얼
[데이터 구조] 재귀(recursive) 란?
[Java/알고리즘] 재귀 함수(Recursion Function) 이해하기
[Java/자료구조] 비선형구조 이해하기 - 1 : 트리(일반트리, 이진트리)
