[Kotlin/자료구조] Tree에 대하여(1)

1. 들어가기 전에 : 선형 구조 vs 비선형 구조

 이전 포스팅에서 설명한 LinkedList(연결 리스트), Queue(큐), Stack(스택)은 선형(Linear) 자료구조라고 한다.

 선형 자료구조는 데이터가 연속적으로, 순차적으로 나열된 형태를 뜻한다. 배열과 리스트가 대표적이다.

 하나의 선에 데이터의 앞(front). 뒤(rear)가 존재한다고 생각하면 쉽다.

 

 선형 구조 외에 분류로 비선형(NonLinear) 자료구조가 있다.

 비선형 자료구조는 데이터의 관계들이 계층적으로 연관된, 또는 1:n / n:m 관계를 갖는 자료구조이다. 트리와 그래프가 대표적이다.

 하나의 데이터 뒤에 여러개의 데이터가 존재한다고 생각하면 쉽다.

 

선형 구조 vs 비선형 구조

 그래프에 대해서는 다음 포스팅에서 다루도록 하겠다. 사실 트리도 그래프의 한 종류이다.

---

2. 용어 정리

 트리의 모양이 나무를 뒤집어 놓은 것과 같다고 하여 이런 이름이 붙었다.

 트리는 노드로 구성되어 있다. 데이터를 포함하며 다른 노드와 연결될 수 있는 것을 노드라고 한다. (연결 리스트 노드와 동일한 개념)

 

트리 (출처: https://tutorialspoint.com)

• Root : 트리 최상단의 노드, Parent가 존재하지 않는 노드
  
  • 최대 한 개의 루트 노드만 가질 수 있다. (최대 한 개라고 표현한 이유는 null도 트리일 수 있기 때문이다.)
• Edge : Parent로부터 Child에게 이어지는 연결 선, 한국말로 '간선'이라고 부른다.
• Leaf : Child가 존재하지 않는 노드
• Level : 루트 노드부터 Level 0, Depth(깊이)에 따라 레벨이 늘어난다.
• Sibilings : 형제. 같은 부모를 가진 Child들을 뜻한다.
• Ancestor : 조상. 해당 노드의 Parent 노드들의 집합을 뜻한다.
• Descendant : 자손. 해당 노드로부터 Child 노드들의 집합을 뜻한다. (Child의 Child...)
• Sub-tree : Child 노드의 Tree. 노드의 자손들. 트리안에 존재하는 트리를 뜻한다.
• Node size : 자기 자신을 포함하여 그 노드가 가진 자손의 수
• Skew tree : 경사 트리. 모든 노드가 오직 한 개의 자식만을 가질 때를 뜻한다.

Skew tree

---

3. Binary Tree

 트리는 여러(n) 자식(Child)를 가질 수 있다. 아무런 규칙이 존재하지 않을 경우 자료 구조에서의 쓰임, 효율 등이 좋지 않을 것이다.

 

 우선 이진 트리에 대해서 알아보자.

 

3-1. 정의

 각 노드가 자식이 없거나, 한 개 혹은 두 개. 즉, 최대 두 개의 노드로 구성된 트리를 Binary Tree라고 한다.

 트리를 채우는 방법, 최종적인 자료 구조 모양에 따른 이름들이 존재한다.

• Strict Binary Tree
  • 모든 노드가 두 개의 자식을 가지거나 자식이 없는 트리
• Full Binary Tree (포화 이진 트리 또는 정 이진 트리)
  • 모든 노드가 두 개의 자식을 가지고, 리프 노드가 같은 레벨에 있는 트리
  • 이름에서 보는 것과 같이 모든 레벨에 노드들이 꽉 채워진 형태라고 할 수 있다.
• Complete Binary Tree (완전 이진 트리)
  • 마지막 레벨을 제외한 모든 레벨에서 노드들이 채워지고, 마지막 레벨에서는 순차적으로 채워져있는 트리
  • 루트부터 시작하여 각 노드에 순차적으로 번호를 매기면 트리 안의 노드 수까지 완전한 순열을 이룬다.
  • 이진 트리의 높이를 h라고 해보자.
    모든 리프 노드가 높이 h나 h-1에 있고 순열에서 빠진 숫자가 없을 때 Complete Binary Tree라고 할 수 있다.

Full Binary Tree와 Complete Binary Tree

 위 그림에서 볼 수 있듯이 Full Binary Tree는 Complete Binary Tree이기도 하다.

 

---

 

3-2. 속성

• Full Binary Tree의 노드 사이즈를 레벨에 따라 알아보면 다음과 같다.

Level	Node size
Level 0	$2^0$
Level 1	$2^1$
Level 2	$2^2$
Level 3	$2^3$
...	...
$h$	$2^h$
total	$2^{h+1} - 1$

• 즉 Full Binary Tree의 노드 개수는 $2^{h+1} - 1$ 이다.
• Complete Binary Tree의 노드의 크기는 Level $h-1$의 Full Binary Tree 크기와 Level $h$ 크기 사이에 존재함도 알 수 있다.
  
  • 개수는 $2^h$와 $2^{h+1} - 1$ 범위에 존재한다.

 

---

 

3-3. 구조

data class TreeNode<T>(
	var data: T,
    	var leftNode: TreeNode<T>?,
    	var rightNode: TreeNode<T>?
)

연결 리스트(LinkedList)와 상당히 유사한 구조라고 할 수 있다. 데이터와 왼쪽 노드, 오른쪽 노드에 대한 참조가 존재한다.

 

---

 

3-4. 탐색(Traversal)

 Binary Tree의 루트부터 시작하여 모든 노드를 탐색하는 데에는 세 가지 단계가 있다.

 이 단계들은 현재 노드에 대해 어떤 체계로 작업을 수행할 것인지에 따라 유형이 달라진다. 쉬운 말로 노드를 방문하는 순서에 따라 달라진다.

 

 다음 트리와 함께 세 가지 단계에 대하여 알아보겠다.

• 전위 탐색(Pre-order traversal)
  • 루트 노드를 먼저 방문하고, 왼쪽 서브 트리를 방문하고, 오른쪽 서브 트리를 방문하는 탐색 방법이다.
  • 모든 탐색은 각 서브 트리로 방문(진입)했을 때도 같은 규칙을 적용한다.
  • 위 트리에 대해서 전위 탐색을 진행했을 때  1 - 2 - 4 - 5 - 3  순서대로 탐색을 진행한다.
• 중위 탐색(In-order traversal)
  • 왼쪽 서브 트리를 먼저 방문하고, 루트 노드(자신)을 방문하고, 오른쪽 서브 트리를 방문하는 탐색 방법이다.
  • 위 트리에 대해서 중위 탐색을 진행했을 때  4 - 2 - 5 - 1 - 3  순서대로 탐색을 진행한다.
• 후위 탐색(Post-order traversal)
  • 왼쪽 서브 트리를 먼저 방문하고, 오른쪽 서브 트리를 방문하고, 마지막으로 루트 노드(자신)을 방문하는 탐색 방법이다.
  • 위 트리에 대해서 후위 탐색을 진행했을 때  4 - 5 - 2 - 3 - 1  순서대로 탐색을 진행한다.

 

 이 외에 트리의 레벨 순서대로 순회하는 Level-order traversal도 존재한다.

 위 트리에 대해서 순회할 경우 1 - 2 - 3 - 4 - 5  순서대로 탐색을 진행한다.

 

 Level-order traversal을 하는 방법은 Queue를 이용하는 것이다.

 n 번째 레벨의 노드들을 탐색하는 동안 다음 n + 1 번째 레벨의 노드들을 Queue에 넣어 간단하게 구현할 수 있다.

import java.util.*

fun main() {
    val binaryTree = BinaryTree()
    binaryTree.root = TreeNode(1)
    binaryTree.root!!.left = TreeNode(2)
    binaryTree.root!!.right = TreeNode(3)
    binaryTree.root!!.left!!.left = TreeNode(4)
    binaryTree.root!!.left!!.right = TreeNode(5)

    binaryTree.orderingByLevel()
}

data class TreeNode<T>(var data: T, var left: TreeNode<T>? = null, var right: TreeNode<T>? = null)

class BinaryTree {
    var root: TreeNode<Int>? = null

    fun orderingByLevel() {
        val queue: Queue<TreeNode<Int>> = LinkedList()
        
        queue.add(root)
        
        while (queue.isNotEmpty()) {
            val polledNode = queue.poll()
            print("${polledNode.data} ")

            /* 왼쪽 노드 offer */
            if (polledNode.left != null) {
                queue.offer(polledNode.left)
            }

            /* 오른쪽 노드 offer */
            if (polledNode.right != null) {
                queue.offer(polledNode.right)
            }
        }
    }
}

---

 

다음 포스팅에서는 이진 검색 트리, 균형 이진 검색 트리에 대해서 알아보겠다.