트리(Tree) 자료 구조에 대해서 간단히 복습해보자. 이전의 포스팅을 참고해도 좋다. 이전의 포스팅은 아래 링크를 통해 확인할 수 있다.
https://hongjw1938.tistory.com/5?category=884192
자료구조(Java) - Collection Framework 2
이전 포스팅에 이어서 Map 인터페이스를 구현한 Collection Class들에 대해서 소개한다. ④ HashTable, HashMap, TreeMap HashTable은 Map 인터페이스를 구현한 Key - Value 쌍을 저장할 수 있는 형태의 Collectio..
hongjw1938.tistory.com
1. 트리(Tree)란?
자바의 Collection Framework를 학습하며 여러 자료 구조에 대해 이미 살펴본 바 있다. ArrayList, LinkedList, Map, Stack, Queue 등의 내용이 기억날 것이다. Map은 조금 다르지만 이 자료 구조들은 기본적으로 공통점이 있다.
바로 선형(Linear) 자료 구조라는 점이다.
선형(Linear) 자료 구조란 무엇인가? 구조에 저장될 데이터들이 순차적으로 저장되는 형태를 의미한다. 간단히 배열을 생각해보면 메모리 공간에 순서대로 나열해서 저장하는 것을 알 수 있다.
ArrayList는 배열을 기반으로 하며, LinkedList는 배열은 아니지만 각 데이터를 저장한 노드들이 선형으로 이어진 형태인 것이다. Stack, Queue 또한 이러한 구조를 바탕으로 설계되었다.
이번에 써내려갈 Tree 구조는 비-선형(Non-Linear) 자료 구조이다. 이러한 구조는 단일 방향으로 각각의 데이터들이 연결되거나 나열된 것이 아니라 복수의 데이터들이 복수의 데이터들과 연결될 수 있는 구조로 설계될 수 있다.
비-선형(Non-Linear) 자료 구조는 대표적으로 Tree, Graph 가 있다. 그래프(Graph)는 추후 별도 포스팅을 참조. 왜 이러한 비선형 자료 구조를 개발하게 되었을까? 우선 선형 구조와 비선형 구조의 차이를 명료하게 살펴보기 위해 아래 표를 보자
※ 선형 구조와 비-선형 구조의 차이
| Point | 선형 구조 | 비-선형 구조 |
| 데이터 저장 | 순차적으로 각 데이터를 순회할 수 있도록 저장 | 데이터들이 계층적으로 연결되어 저장 |
| 수준(Level) | 단일 수준(Level)에서 모든 데이터를 저장 | 복수 수준(Level)에서 데이터를 저장 |
| 구현 복잡도 | 구현이 쉬움 | 구현이 어렵고 이해도 난해 |
| 순회 | 단일 동작으로 모든 데이터 순차적 순회 가능 | 데이터 순회에 복수의 동작 필요 |
| 메모리 활용 | 메모리 공간 활용 효율성 낮음 | 메모리 공간을 매우 효율적으로 활용 |
| 시간 복잡도 | 저장 공간이 늘어나면 비례하여 증가 | 저장 공간이 늘어나면 비례하는 수준보다 적게 증가 |
선형 구조와 비-선형 구조는 그 쓰임새도 다르고 공간을 활용하는 방법과 데이터를 찾는 시간적 복잡도에서도 차이가 있다. 실제 추후에 포스팅하겠으나 알고리즘 중 BFS / DFS 와 같은 문제를 푸는 경우 비-선형 구조의 형태를 많이 활용 한다.
Tree를 이해하기 가장 쉬운 구조는 집안의 계보이다. 조상님부터 대대로 내려오는 계보를 보면 어떠한 구조로 집안 내력이 형성되어 있는지를 명료하게 알 수 있을 것이다. 누가 어느 집안 사람인지, 몇 번째 자식인지 등등..
혹은 회사의 조직 구조도를 보면 된다. 누가 어디 조직에 소속되어 있는지, 조직 간 연결 구조는 어떠한지 매우 명료하게 확인할 수 있다.
간단하게 그러한 구조를 떠올려 보며 아래의 그림을 보자.
위 그림은 대표적인 Tree 형태의 구조를 의미한다. 각각이 의 노드가 있고 이 노드들이 각각 2개의 노드와 연결되어 있다. 이러한 구조를 이진 트리(Binary Tree) 라고 한다. 우선 용어 부터 정리해보자
| 이름 | 설명 | 위 그림 기반 예시 |
| Root | Tree 구조의 최상단 Node | Node1 |
| Edge | Node와 Node의 연결 | 화살표 |
| Parent | Leaf Node 제외한 모든 Node Edge로 연결된 Node를 하위에 보유한 모든 Node |
Node1 ~ 3 |
| Child | Root Node를 제외한 모든 Node 즉, Parent를 갖는 Node |
Node2 ~ 7 |
| Leaf | Tree의 구조에서 Child를 갖지 않는 모든 최하단 Node | Node4 ~ 7 |
| Height | 전체 Tree 구조에서 가장 긴 경로 | Root - Leaf 모든 경로가 2의 거리(경로) |
| Depth | 특정 Node에서 Root Node 까지의 경로(깊이) | Node3은 Root 까지 1의 Depth |
| Sub Tree | Tree 구조 내에 있는 모든 부분적인 Tree들 | Node2와 그 아래는 전체 Tree의 Sub Tree |
| Sibling | 동일한 Parent / Level 갖는 관계인 Node | Node2, Node3은 Sibling |
* 트리의 Depth(깊이)는 루트를 0으로 두거나 1로 두는 경우가 있다. 반드시 정해진 것은 아님
추가로, 조상(Ancestor), 자손(Descendent)도 있는데 이는 정점 A에서 정점 B사이를 루트를 경유하지 않고 위 혹은 아래 방향으로 한 방향으로만 이동이 가능할 때, A가 루트에 더 가깝다면 A를 조상, B를 자손이라고 부른다.
조상은 자기 자신을 포함하여 간주하기 때문에 자기 자신도 스스로의 조상이 된다고 본다.
Tree 라고 하면 위의 구조를 쉽게 떠올리게 되는데, 반드시 위처럼 Child가 2개인 이진 트리만 있는 것은 아니다. Child를 몇 개를 가지든 위와 같은 형태의 구조를 통해 형성된다면 Tree 구조라고 볼 수 있다.
참고로 트리는 그래프의 일종이다.(그래프에 대한 설명은 여기를 참조)
그래프와 트리의 차이를 다음의 표로 알아보자.
그래프와 트리의 차이는 아래와 같다.
| 구분 | 그래프(Graph) | 트리(Tree) |
| 정의 | 객체 혹은 노드(Node)와 그것을 연결하는 간선(Edge)으로 모인 구조 | 그래프의 한 종류 방향성이 없으며 순환하지 않음 |
| 방향성 | 무방향 혹은 유방향으로 가능 | 무방향 그래프 |
| 순환성 | 순환 가능 자기 자신을 연결하는 간선(Self-Loop) 가능 순환(Cyclic), 비순환(Acyclic) 그래프 모두 가능 |
순환 불가능 자기 자신 연결 간선(Self-Loop) 불가능 비순환 그래프(Acyclic Graph) |
| 루트 | 루트의 개념이 있거나 없을 수 있음 | 하나의 루트 노드 존재 |
| 모델 | 네트워크 모델 | 계층 모델 |
| 순회 | 넓이 우선 탐색(BFS) 깊이 우선 탐색(DFS) |
전위(Pre) / 중위(In) / 후위(Post) 순회 방식 |
| 간선 수 | 그래프에 따라 다르며 없을 수도 있음 | N개의 노드(Node)라면 N-1개 |
순회의 경우, 전위 / 중위 / 후위 순회방식은 기본적으로 DFS를 사용한 방식이라고 볼 수 있다. 트리는 그래프의 일종이므로 BFS / DFS로도 탐색은 가능하다.
2. 이진 트리
여러 형태의 트리 구조가 있겠지만 여기서는 이진 트리에 대해서 깊이 들여다 본다. 이진 트리는 트리 구조의 자료 형태 중에서도 가장 많이 쓰인다. 이 구조를 여러 가지 방법을 활용해 개량하여 필요에 따라 사용할 수 있다.
이진 트리는 각 노드가 Child 노드를 최대 2개씩 보유한 형태를 의미한다. 각 노드는 Left / Right Child 노드라고 명명해서 부른다. 위 그림에서 예시로 든 트리 형태 또한 이진 트리이다.
그렇다면 이진 트리를 자바로 직접 구현해보자. 어떤 형태로 구현할 수 있을까? 우선 최초의 빈 상태라면 제일 먼저 넣은 노드를 Root로 가져가야 할 것이다.
① 완전 이진 트리 / 포화 이진 트리
이진 트리는 위의 그림과 같은데 그 중에서도 완전 이진 트리(Complete Binary Tree)와 포화 이진 트리(Perfect Binary Tree)가 있다.
완전 이진 트리는 위 층위부터 시작하여 왼쪽에서 오른쪽 방향으로 모든 노드가 차 있는 경우를 의미한다.
포화 이진 트리는 Leaf 노드가 있는 층위까지 모든 노드가 다 꽉 차 있는 상태를 의미한다.
아래의 그림을 보자.
위 그림은 완전 이진 트리이다. 위 층위부터 아래 층위로 가면서 왼쪽부터 차곡차곡 쌓여 있기 때문이다.
위 그림은 그냥 이진 트리일 뿐, 완전 이진 트리가 아니다. 왜냐하면 Node3의 자식이 좌측부터 채워지지 않았기 때문이다.
위 그림은 포화 이진 트리의 그림이다. 모든 층위에 노드가 꽉 차있기 때문이다.
이는 완전 이진 트리이기도 하다. 포화 이진 트리는 반드시 완전 이진 트리이지만 완전 이진 트리가 반드시 포화 이진 트리는 아니다.
② 트리 표현하는 방법
트리를 구현하는 방법은 기본적으로 3가지가 있다.
⑴ 트리는 기본적으로 그래프 형태의 구조이다. 따라서 그래프의 인접 리스트 방식으로 쉽게 표현이 가능하다.
⑵ 배열로 표현하기 - 이 경우는 완전 이진 트리만 가능하다.
- 루트 노드를 index 1로 표현하고 좌측 자식을 x2, 우측 자식을 x2+1의 index에 넣어서 저장하면 된다.
- Heap, 세그먼트 트리 구현 시 많이 쓰인다.(Heap은 여기 포스팅, 세그먼트 트리는 여기 포스팅 참조)
⑶ 별도의 class(구조화)로 구성하는 방법이 있다.
아래에서 ⑶을 이용하여 구현한 방법을 알아보자.
3. 이진 트리(Binary Tree) 구현하기
① Node 클래스
Node class는 LinkedList 의 노드처럼 자체적으로 데이터 값을 저장하고 있으며 각 Parent / Child 노드에 대한 정보도 갖고 있어야 한다. 따라서 아래와 같이 구현될 수 있다.
class Node<T>{
T value;
Node left;
Node right;
public Node(T value){
this.value = value;
}
}안전한 캡슐화를 하려면 getter/setter를 생성해야겠지만 짧은 예시로 구현해보도록 한다. 위 코드 클래스를 전체 Binary Tree를 위한 Class의 inner class로 구현하였다.
이를 통해 전체 코드의 캡슐화를 증대시키고 코드의 복잡성을 줄일 수 있도록 구현하였다.
② BinrayTree 클래스
BinaryTree 클래스는 전체 이진 트리에 대한 정보를 갖고 있는 클래스이다. 따라서, 현재 Root 노드가 무엇인지, 현재 저장된 노드의 수는 몇 개인지 등의 정보를 갖고 있다.
public class BinaryTree<T> {
Node<T> root = null;
int size = 0;
public BinaryTree(){}
}
③ 데이터 노드 삽입하기
데이터 삽입은 최초에 Root가 비어 있다면 Root에 담고, 아니라면 Root의 Left부터 차곡차곡 데이터를 삽입하는 방식으로 진행한다. 이전 포스팅에서 읽었다면 이것이 무슨 트리인지 기억할 것이다. 바로 완전 이진 트리를 구현하고자 하는 것이다.
이 방식을 유지하려면 레벨 순회가 가능해야 한다. 순회란 Tree 구조에서 저장된 모든 데이터를 빼내는 방식에 대한 정의를 의미한다. 일단 아래의 코드를 통해 어떻게 삽입을 하는 지 확인하자.
public boolean insert(T value){
Node newNode = new Node(value);
if(size == 0){
root = newNode;
return true;
}
Queue<Node<T>> q = new LinkedList<>();
q.add(root);
while(true){
Node tmp = q.peek();
if(tmp.left == null){
tmp.left = newNode;
newNode.parent=tmp;
break;
} else {
q.add(tmp.left);
}
if(tmp.right == null){
tmp.right = newNode;
newNode.parent=tmp;
break;
} else {
q.add(tmp.right);
}
}
return true;
}이는 레벨 순회의 방식을 통해 진행한 것인데, Queue 자료 구조를 통해 Root 부터 시작하여 Child를 left - right 순서로 모두 순회 후 다음 레벨로 넘어가서 순회하는 구조를 만든 것이다.
이 부분을 이해하기 전에 순회에 대해서 일단 더 자세히 알아보자.
④ 트리(Tree) 순회(traversal)하여 데이터 출력하기
비-선형 구조의 데이터는 상단의 표에서 설명하였듯이 선형 구조의 데이터 참조와는 다르다. 선형 구조에서는 순차적으로 데이터를 꺼내오기만 하면 되었다.
예를 들어, Array(배열) 구조라면 Index를 0부터 현재 배열 size -1 까지 순차적으로 접근하여 데이터를 꺼내오면 된다.
LinkedList라면 노드가 상호 선형적으로 연결되어 순차적인 방향으로 다음 노드를 순회하여 데이터를 꺼내오면 된다.
그러나 트리(Tree) 구조는 하나의 노드가 복수의 다른 노드와의 연결점을 갖는다. 이것은 즉, 동일한 수준(Level)에 있는, 동일한 깊이(Depth)에 있는 노드라도 어떤 데이터는 먼저 순회되고 다른 데이터는 연기되어 순회된다는 의미다.
또 하나 생각해볼 트리(Tree) 구조의 특성은 재귀적이라는 것이다.(DFS 방식!) 재귀적이라는 것은 커다란 구조안에 동일한 형태의 작은 구조로 나뉘어져 있는 경우를 의미한다. 위에서 보여준 트리(Tree) 사진을 조금 변경해서 다시 보자.
위 사진에서 보이듯이, 연보라 색의 부분 또한 전체 Tree의 부분적인 Sub Tree이지만 이 또한 Tree 구조이다. 즉, 전체 구조와 그 안의 작은 구조가 동일한 형태이므로 재귀적인 구조를 갖는다.
왜 이것이 중요한가? 왜냐하면, 전체 트리(Tree) 구조의 데이터를 순회할 때 이 재귀적인 구조를 이용해 쉽고 짧은 순회가 가능해지기 때문이다. 이제 순회의 방법을 알아보자.
아래 경우 중 레벨 순회를 제외하고는 DFS 방식을 사용한 것이다.(DFS 관련 내용은 여기를 참조)
그리고, 중위 순회(InOrder)는 이진 트리가 아니면 사용이 불가하지만 전위 / 후위 순회는 이진 트리가 아닌 자식이 3개 이상인 트리에서도 사용이 가능하다!
ⓐ 중위 순회(InOrder)
중위 순회는 현재 노드를 순회 시 중간에 순회하는 방법이다. 즉, 현재 노드는 Left - Right 의 Child 노드가 있을 것인데, 방문 순서를 LEFT - 자기 자신 - RIGHT 순서로 방문하도록 하는 것을 의미한다. 자기 자신을 N으로 줄여서 LNR 방식이라고도 한다.
아래의 그림을 보면서 쉽게 이해해보자.
위의 사진을 보면 빨간색 화살표를 순서대로 노드를 순회함을 의미하는 것을 알 수 있다.
순서 : 8 - 4 - 2 - 5 - 1 - 6 - 3 - 7
재귀를 이용하여 코드를 짜면 다음과 같이 구성할 수 있다.
public void inorder(Node node){
if(node != null){
inorder(node.left);
System.out.print(node.value + ", ");
inorder(node.right);
}
}코드에서 볼 수 있듯이, 현재 parameter로 전달된 노드가 null이 아니라면 현재 노드의 left child 노드부터 순회하고 자신이 가진 값을 출력한 다음 right child 노드를 방문하고 있다.
ⓑ 전위 순회(preOrder)
전위 순회는 현재 자기 자신 노드를 제일 먼저 순회하고 차후 Left - Right 순서로 순회하는 것을 의미한다. NLR 방식
그림으로 이해하면 다음과 같이 그릴 수 있다.
화살표가 조금 애매하게 그려지긴 했는데 큰 그림은 이해할 수 있다. 동일하게 빨간 화살표를 따라 순회한다.
순서 : 1 - 2 - 4 - 8 - 5 - 3 - 6 - 7
코드는 아래와 같다.
public void preOrder(Node node){
if(node != null){
System.out.print(node.value + ", ");
preOrder(node.left);
preOrder(node.right);
}
}현재 parameter로 전달된 노드가 비어있지 않다면 해당 노드의 값을 출력하고 left - right child 노드를 순회한다.
ⓒ 후위 순회(postOrder)
후위 순회는 유추할 수 있듯이 현재 노드를 가장 마지막에 순회하는 것이다. LRN 방식
참고로 이 후위 순회가 제일 중요하다. 왜냐면, Leaf에서 Root로 올라갈수록 작은 문제들의 결과를 통해 큰 문제를 해결하는 방향이라고 한다면 자식 노드들의 결과를 통해 현재 노드의 결과를 구하는 방식이 필요할 수 있기 때문이다.
그래서, Dynamic Programming이나 Segment Tree를 통해 문제를 해결할 때 등 모두 이 후위 순회를 사용한다! 즉, 매우 중요!
그림은 아래와 같다.
코드는 아래와 같다.
public void postOrder(Node node){
if(node != null){
preOrder(node.left);
preOrder(node.right);
System.out.print(node.value + ", ");
}
}현재 parameter로 전달된 노드가 비어있지 않다면 그의 child 노드들부터 방문한 뒤 자기 자신의 데이터를 출력한다.
ⓓ 레벨 순회(levelOrder, 층위 순회)
레벨 순회는 다른 순위와는 조금 다르다. 다른 순회들은 모두 parent - child 관계인 경우만 이용하면 되는데, 이 순회는 Sibling 관계에 있는 노드간에 방문 순서가 정해져야 한다.
Sibling 관계는 재귀적으로는 풀기가 어렵다. 왜냐하면 다른 관계는 각 노드에 속성으로 parent / child 관계를 알 수 있도록 설정되어 있으나, Sibling은 설정하지 않았기 때문이다. 물론 해주면 할 수는 있겠지만.. 전체 코드가 너무 복잡해질 수 있다.
그림으로 이해해보자.
각 층위를 모두 방문한 뒤에 추후 Child 노드로 이어져서 방문하는 것을 알 수 있다. 이 방식의 설계를 위해서는 Queue 자료구조를 사용하는 것이 일반적이다. 최상단 노드부터 시작하여 자신의 Child 노드를 모두 방문한 뒤 다음 단계로 넘어가야 하기 때문
순서 : 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8
따라서 최상단 노드 방문 후, Child 노드를 차례로 Queue에 넣고 각 Child 노드를 방문할 때마다 해당 노드가 Child 노드를 갖고 있다면 Queue에 넣어서 순차적으로 방문할 수 있도록 해야 한다.
위에서 이진 트리 삽입을 완전 이진 트리로 가져가겠다고 정하였기 때문에 삽입 시에도 이 방법을 활용한 것이다. 코드는 아래와 같다.
public void levelOrder(Node root){
Queue<Node<T>> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
Node temp = q.peek();
System.out.print(temp.value + ", ");
if(temp.left != null){
q.add(temp.left);
}
if(temp.right != null) {
q.add(temp.right);
}
q.poll();
}
}설명한 그대로 코드를 이해해보면 이해하기 쉬울 것이다.
여태까지 배운 순회 방식은 추후 포스팅할 알고리즘 풀이 기법인 BFS(Breadth - First - Search), DFS(Depth - First - Search)에 매우 잘 활용되는 방식이므로 기억해둘 필요가 있다.
지금까지 구성한 내용의 전체 코드는 아래와 같다. 데이터 삭제 등의 코드는 별도로 구성하지 않았는데 보통 이진 트리는 이런식으로 활용하는 경우는 없다.
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTree<T> {
class Node<T>{
T value;
Node parent;
Node left;
Node right;
public Node(T value){
this.value = value;
}
}
Node<T> root = null;
int size = 0;
public BinaryTree(){}
public boolean insert(T value){
Node newNode = new Node(value);
if(size == 0){
root = newNode;
return true;
}
Queue<Node<T>> q = new LinkedList<>();
q.add(root);
while(true){
Node tmp = q.peek();
if(tmp.left == null){
tmp.left = newNode;
newNode.parent=tmp;
break;
} else {
q.add(tmp.left);
}
if(tmp.right == null){
tmp.right = newNode;
newNode.parent=tmp;
break;
} else {
q.add(tmp.right);
}
}
return true;
}
public void inorder(Node node){
if(node != null){
inorder(node.left);
System.out.print(node.value + ", ");
inorder(node.right);
}
}
public void preOrder(Node node){
if(node != null){
System.out.print(node.value + ", ");
preOrder(node.left);
preOrder(node.right);
}
}
public void postOrder(Node node){
if(node != null){
preOrder(node.left);
preOrder(node.right);
System.out.print(node.value + ", ");
}
}
public void levelOrder(Node root){
Queue<Node<T>> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
Node temp = q.peek();
System.out.print(temp.value + ", ");
if(temp.left != null){
q.add(temp.left);
}
if(temp.right != null) {
q.add(temp.right);
}
q.poll();
}
}
}
데이터의 빠른 순회가 중요하기 때문에 트리 내부의 데이터 간 정렬을 이용해 설계되도록 구조를 짜는 경우가 많다. 그러한 예시는 다음 포스팅인 Binary Search Tree에서 찾아본다. 이번 포스팅을 통해서는 트리 구조와 이진 트리에 대한 개념을 이해하는 정도로 넘어간다.
4. 추가
※ 트리의 지름 구하기
트리에서 지름이란 노드 간의 간격이 가장 긴 것을 의미한다. 즉, 노드 간에는 각각 거리가 있는데 그 거리가 가장 길게 되는 두 노드를 찾게 되는 각각의 노드가 트리의 지름을 구성하는 노드가 되는 것이다.
트리의 지름을 구하는 방법은 2번의 탐색을 통해 가능하다.(증명은 제외)
1. 한 노드 s에서 모든 노드까지의 거리를 구하여 가장 먼 거리에 있는 노드 u를 찾는다.
2. 노드 u에서 모든 노드까지의 거리를 구하여 가장 먼 노드인 노드 v를 구한다.
3. 노드 u와 v 사이의 거리가 지름이 된다.
이 부분은 관련 문제를 해결한 포스팅을 보면서 코드로 더 쉽게 이해해보자.
백준 1167(트리의 지름) 포스팅(여기) 참조
백준 1967(트리의 지름) 포스팅(여기) 참조
오류가 있는 부분은 댓글로 남겨주시면 반영하겠습니다. 감사합니다.
'자바 프로그래밍 > 자료구조(Data Structure)' 카테고리의 다른 글
| 자료구조 - 세그먼트 트리(Segment Tree) (0) | 2020.09.20 |
|---|---|
| 자료구조 - 이진 탐색 트리(Binary Search Tree) (2) | 2020.08.24 |
| 자료구조 - HashMap 들여다보기(2) (1) | 2020.08.20 |
| 자료구조 - HashMap 들여다보기(1) (0) | 2020.08.19 |
| LinkedList 직접 구현해보기 (Java) (0) | 2020.08.15 |
