![자바 [JAVA] - 트리(Tree), 이진 트리(Binary Tree)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FdVYDbm%2Fbtr2tCIZ8io%2Fd177mABokajbm9kczjwUmk%2Fimg.png)
1. 트리(Tree)란?
자바의 Collection Framework를 학습하며 여러 자료 구조에 대해 이미 살펴본 바 있다. ArrayList, LinkedList, Map, Stack, Queue 등의 내용들이 있었. Map은 조금 다르지만 이 자료 구조들은 기본적으로 공통점이 있다.
바로 선형(Linear) 자료 구조라는 점이다.
선형(Linear) 자료 구조란 무엇인가? 구조에 저장될 데이터들이 순차적으로 저장되는 형태를 의미한다. 간단히 배열을 생각해보면 메모리 공간에 순서대로 나열해서 저장하는 것을 알 수 있다.
ArrayList는 배열을 기반으로 하며, LinkedList는 각 데이터를 저장한 노드들이 논리적인 선형으로 이어진 형태인 것이다. Stack, Queue 또한 이러한 구조를 바탕으로 설계되었다.
이번에 써내려갈 Tree 구조는 비-선형(Non-Linear) 자료 구조이다. 이러한 구조는 단일 방향으로 각각의 데이터들이 연결되거나 나열된 것이 아니라 복수의 데이터들이 복수의 데이터들과 연결될 수 있는 구조로 설계될 수 있다.
비-선형(Non-Linear) 자료 구조는 대표적으로 Tree, Graph 가 있다. 왜 이러한 비선형 자료 구조를 개발하게 되었을까? 우선 선형 구조와 비선형 구조의 차이를 명료하게 살펴보기 위해 아래 표를 살펴보자.
※ 선형 구조와 비-선형 구조의 차이
| Point | 선형 구조 | 비-선형 구조 |
| 데이터 저장 | 순차적으로 각 데이터를 순회할 수 있도록 저장 | 데이터들이 계층적으로 연결되어 저장 |
| 수준(Level) | 단일 수준(Level)에서 모든 데이터를 저장 | 복수 수준(Level)에서 데이터를 저장 |
| 구현 복잡도 | 구현이 쉬움 | 구현이 어렵고 이해도 난해 |
| 순회 | 단일 동작으로 모든 데이터 순차적 순회 가능 | 데이터 순회에 복수의 동작 필요 |
| 메모리 활용 | 메모리 공간 활용 효율성 낮음 | 메모리 공간을 매우 효율적으로 활용 |
| 시간 복잡도 | 저장 공간이 늘어나면 비례하여 증가 | 저장 공간이 늘어나면 비례하는 수준보다 적게 증가 |
선형 구조와 비-선형 구조는 그 쓰임새도 다르고 공간을 활용하는 방법과 데이터를 찾는 시간적 복잡도에서도 차이가 있다. 알고리즘 중 BFS / DFS 와 같은 문제를 푸는 경우 비-선형 구조의 형태를 많이 활용 한다.
Tree를 이해하기 가장 쉬운 구조는 집안의 계보이다. 조상님부터 대대로 내려오는 계보를 보면 어떠한 구조로 집안 내력이 형성되어 있는지를 명료하게 알 수 있을 것이다. 누가 어느 집안 사람인지, 몇 번째 자식인지 등등..
혹은 회사의 조직 구조도를 보면 된다. 누가 어디 조직에 소속되어 있는지, 조직 간 연결 구조는 어떠한지 매우 명료하게 확인할 수 있다.
아래의 그림을 살펴보자.
위 그림은 대표적인 Tree 형태의 구조를 의미한다. 각각의 노드가 있고 이 노드들이 각각 2개의 노드와 연결되어 있다. 이러한 구조를 이진 트리(Binary Tree) 라고 한다. 우선 용어 부터 정리해보자
* 트리의 Depth(깊이)는 루트를 0으로 두거나 1로 두는 경우가 있다. 반드시 정해진 것은 아님
추가로, 조상(Ancestor), 자손(Descendent)도 있는데 이는 정점 A에서 정점 B사이를 루트를 경유하지 않고 위 혹은 아래 방향으로 한 방향으로만 이동이 가능할 때, A가 루트에 더 가깝다면 A를 조상, B를 자손이라고 부른다.
조상은 자기 자신을 포함하여 간주하기 때문에 자기 자신도 스스로의 조상이 된다고 본다.
Tree 라고 하면 위의 구조를 쉽게 떠올리게 되는데, 반드시 위처럼 Child가 2개인 이진 트리만 있는 것은 아니다. Child를 몇 개를 가지든 위와 같은 형태의 구조를 통해 형성된다면 Tree 구조라고 볼 수 있다.
참고로 트리는 그래프의 일종이다.(그래프에 대한 설명은 여기를 참조)
그래프와 트리의 차이를 다음의 표로 알아보자.
그래프와 트리의 차이는 아래와 같다.
순회의 경우, 전위 / 중위 / 후위 순회방식은 기본적으로 DFS를 사용한 방식이라고 볼 수 있다. 트리는 그래프의 일종이므로 BFS / DFS로도 탐색은 가능하다.
2. 이진 트리
이진트리란 자식노드가 최대 두 개인 노드들로 구성된 트리다. 이진트리에는 정이진트리(full binary tree), 완전이진트리(complete binary tree), 균형이진트리(balanced binary tree) 등이 있다.
이진 트리는 다음과 같은 특징을 갖는다.
- 각 노드가 Child 노드를 최대 2개씩 보유한 형태를 의미한다. 각 노드는 Left / Right Child 노드라고 명명해서 부른다.
- 자식 노드는 좌우를 구분한다
- 왼쪽 자식: 부모 노드의 왼쪽 아래
- 오른쪽 자식: 부모 노드의 오른쪽 아래
이진 트리 종류
완전 이진 트리 / 포화 이진 트리
이진 트리는 위의 그림과 같은데 그 중에서도 완전 이진 트리(Complete Binary Tree)와 포화 이진 트리(Perfect Binary Tree)가 있다.
'완전 이진 트리'란 '마지막 레벨'을 제외한 모든 노드가 채워져있으면서 모든 노드(=사실상 마지막 레벨의 노드들)가 왼쪽부터 채워져있어야 한다.
즉, 완전 이진 트리는 이진 트리에서 두 가지 조건을 더 만족해야 하는 것이다.
- 마지막 레벨을 제외한 모든 노드가 채워져있어야함
- 모든 노드들은 왼쪽부터 채워져있어야함
그리고 완전 이진 트리에서 한 가지 조건만 더 추가하면 '포화 이진 트리(perfect binary tree)'가 된다. 바로 '마지막 레벨을 제외한 모든 노드는 두 개의 자식노드를 갖는다'라는 조건이다.
아래의 그림을 보자.
위 그림은 완전 이진 트리이다. 위 층위부터 아래 층위로 가면서 왼쪽부터 차곡차곡 쌓여 있기 때문이다.
위 그림은 그냥 이진 트리일 뿐, 완전 이진 트리가 아니다. 왜냐하면 Node3의 자식이 좌측부터 채워지지 않았기 때문이다.
위 그림은 포화 이진 트리의 그림이다. 모든 층위에 노드가 꽉 차있기 때문이다.
이는 완전 이진 트리이기도 하다. 포화 이진 트리는 반드시 완전 이진 트리이지만 완전 이진 트리가 반드시 포화 이진 트리는 아니다.
정 이진트리(Full Binary Tree)
모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.
편향 이진트리(skewed binary tree)
같은 높이의 이진 트리 중에서 최소 개수의 노드 개수를 가지면서 왼쪽 혹은 오른쪽 서브트리만을 가지는 이진트리이다.
즉 모든 노드가 왼쪽에 있거나 반대로 오른쪽에 있는 트리이다.
- 각 부모 노드가 오직 한 개의 연관 자식 노드를 갖는 트리이다.
- 사향 이진 트리(Degenerate (or Pathological) Tree) 라고도 부른다.
- Linked List 성능과 동일하다.
균형 이진 트리 (Balanced Binary Tree)
높이 균형이 맞춰진 이진트리이다. 왼쪽과 오른쪽 트리의 높이 차이가 모두 1이상 차이 나지 않는 트리다.
예로는 AVL(높이 균형 이진 탐색 트리) 과 Red-Black 트리가 있다.
3. 트리 표현하는 방법
트리를 구현하는 방법은 기본적으로 3가지가 있다.
⑴ 트리는 기본적으로 그래프 형태의 구조이다. 따라서 그래프의 인접 리스트 방식으로 쉽게 표현이 가능하다.
⑵ 배열로 표현하기 - 이 경우는 완전 이진 트리만 가능하다.
배열로 구현하게 되면 특징 및 장점들이 있다. 일단 아래 그림을 보도록 하자.
[특징]
- 구현의 용이함을 위해 시작 인덱스(root)는 1 부터 시작한다.
- 각 노드와 대응되는 배열의 인덱스는 '불변한다'
위 특징을 기준으로 각 인덱스별로 채워넣으면 특이한 성질이 나오는데 이는 다음과 같다.
[성질]
- 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2
- 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 1
- 부모 노드 인덱스 = 자식 노드 인덱스 / 2
위 세개의 법칙은 절대 변하지 않는다.
예로들어 index 3 의 왼쪽 자식 노드를 찾고 싶다면 3 × 2를 해주면 된다. 즉 index 6 이 index 3 의 자식 노드라는 것이다.
반대로 index 5의 부모 노드를 찾고 싶다면 5 / 2 를 해주면 된다.(몫만 취함) 그러면 2 이므로 index 2가 index 5의 부모노드라는 것이다.
Heap, 세그먼트 트리 구현 시 많이 쓰인다.
⑶ 별도의 class(구조화)로 구성하는 방법이 있다.
4. 이진 트리를 사용하는 이유?
선형 구조와 달리 탐색과 삽입에서 연산 횟수를 대폭 줄일 수 있기 때문이다.
배열, 연결 리스트, 스택, 큐, 데크(Deque)와 같은 선형 자료구조에서는 하나의 자료 뒤에 오직 하나의 자료만 존재한다. 그렇기 때문에 선형 자료구조에서는 정렬이 되어있지 않은 상태에서 특정 값을 탐색할 때, 최악의 시간 복잡도는 맨 끝까지 탐색하는 경우이기 때문에 O(n) 이 된다
하지만, 이진 트리에서는 탐색하는데 최적의 시간 복잡도는 O(logn) 이 된다. 이를 증명하면 다음과 같다.
포화 이진 트리의 루트 노드의 depth 를 0 으로 지정했을 때, 노드(데이터) 개수는 다음과 같다. n 은 데이터의 개수이고, h 는 트리의 높이를 의미한다.
위의 수식에서 h 를 n 에 관한 식으로 바꾸면 다음과 같다.
여기에 시간 복잡도를 적용하면 다음과 같다.
5. 트리(Tree) 순회(traversal)하여 데이터 출력하기
비-선형 구조의 데이터는 상단의 표에서 설명하였듯이 선형 구조의 데이터 참조와는 다르다. 선형 구조에서는 순차적으로 데이터를 꺼내오기만 하면 되었다.
예를 들어, Array(배열) 구조라면 Index를 0부터 현재 배열 size -1 까지 순차적으로 접근하여 데이터를 꺼내오면 된다.
LinkedList라면 노드가 상호 선형적으로 연결되어 순차적인 방향으로 다음 노드를 순회하여 데이터를 꺼내오면 된다.
그러나 트리(Tree) 구조는 하나의 노드가 복수의 다른 노드와의 연결점을 갖는다. 이것은 즉, 동일한 수준(Level)에 있는, 동일한 깊이(Depth)에 있는 노드라도 어떤 데이터는 먼저 순회되고 다른 데이터는 연기되어 순회된다는 의미다.
또 하나 생각해볼 트리(Tree) 구조의 특성은 재귀적이라는 것이다.(DFS 방식!) 재귀적이라는 것은 커다란 구조안에 동일한 형태의 작은 구조로 나뉘어져 있는 경우를 의미한다. 위에서 보여준 트리(Tree) 사진을 조금 변경해서 다시 보자.
위 사진에서 보이듯이, 연보라 색의 부분 또한 전체 Tree의 부분적인 Sub Tree이지만 이 또한 Tree 구조이다. 즉, 전체 구조와 그 안의 작은 구조가 동일한 형태이므로 재귀적인 구조를 갖는다.
왜 이것이 중요한가? 왜냐하면, 전체 트리(Tree) 구조의 데이터를 순회할 때 이 재귀적인 구조를 이용해 쉽고 짧은 순회가 가능해지기 때문이다. 이제 순회의 방법을 알아보자.
아래 경우 중 레벨 순회를 제외하고는 DFS 방식을 사용한 것이다.
그리고, 중위 순회(InOrder)는 이진 트리가 아니면 사용이 불가하지만 전위 / 후위 순회는 이진 트리가 아닌 자식이 3개 이상인 트리에서도 사용이 가능하다!
ⓐ 중위 순회(InOrder)
중위 순회는 현재 노드를 순회 시 중간에 순회하는 방법이다. 즉, 현재 노드는 Left - Right 의 Child 노드가 있을 것인데, 방문 순서를 LEFT - 자기 자신 - RIGHT 순서로 방문하도록 하는 것을 의미한다. 자기 자신을 N으로 줄여서 LNR 방식이라고도 한다.
위의 사진을 보면 빨간색 화살표를 순서대로 노드를 순회함을 의미하는 것을 알 수 있다.
순서 : 8 - 4 - 2 - 5 - 1 - 6 - 3 - 7
재귀를 이용하여 코드를 짜면 다음과 같이 구성할 수 있다.
|
1
2
3
4
5
6
7
|
public void inorder(Node node){
if(node != null){
inorder(node.left);
System.out.print(node.value + ", ");
inorder(node.right);
}
}
|
cs |
코드에서 볼 수 있듯이, 현재 parameter로 전달된 노드가 null이 아니라면 현재 노드의 left child 노드부터 순회하고 자신이 가진 값을 출력한 다음 right child 노드를 방문하고 있다.
ⓑ 전위 순회(preOrder)
전위 순회는 현재 자기 자신 노드를 제일 먼저 순회하고 차후 Left - Right 순서로 순회하는 것을 의미한다. NLR 방식
동일하게 빨간 화살표를 따라 순회한다.
순서 : 1 - 2 - 4 - 8 - 5 - 3 - 6 - 7
코드는 아래와 같다.
|
1
2
3
4
5
6
7
|
public void preOrder(Node node){
if(node != null){
System.out.print(node.value + ", ");
preOrder(node.left);
preOrder(node.right);
}
}
|
cs |
현재 parameter로 전달된 노드가 비어있지 않다면 해당 노드의 값을 출력하고 left - right child 노드를 순회한다.
ⓒ 후위 순회(postOrder)
후위 순회는 유추할 수 있듯이 현재 노드를 가장 마지막에 순회하는 것이다. LRN 방식
참고로 이 후위 순회가 제일 중요하다. 왜냐면, Leaf에서 Root로 올라갈수록 작은 문제들의 결과를 통해 큰 문제를 해결하는 방향이라고 한다면 자식 노드들의 결과를 통해 현재 노드의 결과를 구하는 방식이 필요할 수 있기 때문이다.
그래서, Dynamic Programming이나 Segment Tree를 통해 문제를 해결할 때 등 모두 이 후위 순회를 사용한다! 즉, 매우 중요!
순서 : 8 - 4 - 5 - 2 - 6 - 7 - 3 - 1
코드는 아래와 같다.
|
1
2
3
4
5
6
7
|
public void postOrder(Node node){
if(node != null){
preOrder(node.left);
preOrder(node.right);
System.out.print(node.value + ", ");
}
}
|
cs |
ⓓ 레벨 순회(levelOrder, 층위 순회)
레벨 순회는 다른 순위와는 조금 다르다. 다른 순회들은 모두 parent - child 관계인 경우만 이용하면 되는데, 이 순회는 Sibling 관계에 있는 노드간에 방문 순서가 정해져야 한다.
Sibling 관계는 재귀적으로는 풀기가 어렵다. 왜냐하면 다른 관계는 각 노드에 속성으로 parent / child 관계를 알 수 있도록 설정되어 있으나, Sibling은 설정하지 않았기 때문이다. 물론 해주면 할 수는 있겠지만. 전체 코드가 너무 복잡해질 수 있다.
각 층위를 모두 방문한 뒤에 추후 Child 노드로 이어져서 방문하는 것을 알 수 있다. 이 방식의 설계를 위해서는 Queue 자료구조를 사용하는 것이 일반적이다. 최상단 노드부터 시작하여 자신의 Child 노드를 모두 방문한 뒤 다음 단계로 넘어가야 하기 때문
순서 : 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8
따라서 최상단 노드 방문 후, Child 노드를 차례로 Queue에 넣고 각 Child 노드를 방문할 때마다 해당 노드가 Child 노드를 갖고 있다면 Queue에 넣어서 순차적으로 방문할 수 있도록 해야 한다.
위에서 이진 트리 삽입을 완전 이진 트리로 가져가겠다고 정하였기 때문에 삽입 시에도 이 방법을 활용한 것이다. 코드는 아래와 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
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();
}
}
|
cs |
설명한 그대로 코드를 이해해보면 이해하기 쉬울 것이다.
여태까지 배운 순회 방식은 추후 포스팅할 알고리즘 풀이 기법인 BFS(Breadth - First - Search), DFS(Depth - First - Search)에 매우 잘 활용되는 방식이므로 기억해둘 필요가 있다.
참고
https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/
https://code-lab1.tistory.com/8
https://kingpodo.tistory.com/27