[Kotlin] Tree
- 본 포스트는 Kotlin 언어에 관한 설명은 없습니다. Kotlin에 관한 내용은 저의 다른 포스트를 참고해주시면 감사하겠습니다.
Tree 개념
지난 포스트에서 Graph라는 자료구조를 살펴 봤었다. 오늘 다룰 Tree라는 자료구조는 Graph의 일종이다. Graph를 여러 기준에 따라 분류할 수 있었는데, Tree는
- 간선의 방향이 있어 방향 그래프(directed graph)이다.
- 가중치는 있을 수도 있고, 없을 수도 있다.
- 모든 노드가 상호 연결되어 있지 않은 부분 그래프(sub graph)이다.
- 모든 노드가 연결되어 있는 연결 그래프(connected graph)이다.
- 순환이 없는 비순환 그래프(acyclic graph)이다.
이런 Graph 중 여러 노드가 한 노드를 가리킬 수 없는 그래프를 특별히 Tree라고 부른다. Fig1과 같은 임의의 Tree를 하나 그려볼 수 있다.
그러나 Fig1을 봐서는 이런 구조가 왜 Tree라고 부르는지 이해할 수 없다. 사실 Fig1을 잘 다듬어보면 왜 Tree라는 구조인지 이해하기 쉬울 것 같다. 아래 Fig2를 보자.
Fig2는 Fig1과 완전히 같은 Graph이고, 노드들을 재배치한 것 뿐이다. 이 자료구조를 다시 보니 Tree라고 부르는 이유는 나뭇가지가 자랄 때 여러 갈래로 나누어지며 뻗는 모습 또는 뿌리가 여러 갈래로 갈라지는 모습과 비슷하기 때문인 것 같다. 이런 Tree 구조는 계층적 구조(hierarchical structure)를 나타내는데 적합하기도 하다. Fig1과 Fig2는 노드들이 각각 최대 두 개의 가지를 뻗지만, 두 개 이상이 되도 Tree라고 부른다. 대부분의 경우 노드 하나가 최대 두 개의 가지를 뻗는 이진 트리(Binary Tree)를 사용하게 된다.
Tree 에 쓰이는 용어
Tree가 사용되는 곳이 많아져서인지, Tree에 쓰이는 용어들도 적지 않다. Fig2에도 표시해놓았지만, 용어의 의미를 짚고 넘어가자. 용어가 많다고 느껴진다면 Parent Node, Child Node, Root Node, Leaf Node 4가지는 꼭 익히고 나머지는 필요할 때 찾아보면서 하는 것도 좋을 것 같다.
- Parent Node(부모 노드) : 연결된 두 노드 중 간선의 방향이 시작되는 쪽의 노드를 Parent Node라고 한다. Fig2에서 A노드는 B, C노드의 Parent Node, B 노드는 D, E노드의 Parent Node…와 같은 방식이다.
- Child Node(자식 노드) : 연결된 두 노드 중 간선의 방향이 가리키는 쪽의 노드를 Child Node라고 한다. Fig2에서 B노드는 A노드의 Child Node, D노드는 B노드의 Child Node…와 같은 방식이다.
- Root Node : 어떤 노드에서 시작해서 Parent Node를 계속해서 따라가다 보면 Parent Node가 없는 노드를 하나 발견할 수 있는데, 이 노드를 Root Node라고 한다. 이 노드가 하나일 경우에만 Root Node라고 하고, 이 노드를 포함하는 Tree를 Rooted Tree라고 한다. 대부분의 경우 Rooted Tree를 다루게 된다.
- Leaf Node : Root Node와는 반대로 Child Node를 갖지 않는 노드를 Leaf Node라고 한다.
- Internal Node : Leaf Node가 아닌 노드들을 Internal Node라고 한다.
- Siblings : 같은 부모를 갖는 노드들을 Siblings관계에 있다고 부른다.
- 노드의 Ancestor(조상) : Child Node에서 Parent Node방향으로 반복적으로 이동하면서 도달할 수 있는 모든 Node를 한 노드의 Ancestor(조상)이라고 한다.
- 노드의 Descendant(자손) : Parent Node에서 Child Node방향으로 반복적으로 이동하면서 도달할 수 있는 모든 Node를 한 노드의 Decendant라고 한다.
- Distance(거리) : 두 노드를 잇는 경로 중 가장 적은 간선 수를 갖는 경로를 최단 거리라고 하는데, 최단 거리가 갖는 간선 개수를 노드 간 Distance(거리)라고 한다.
- 노드의 Depth(깊이) : Root Node에서 특정 노드로 갈 때 까지 거쳐야 하는 간선의 개수를 Depth(깊이)라고 부른다.
- 노드의 Level: 특정 Depth를 갖는 노드의 집합을 Level이라고 부른다.
- Level의 Width : 특정 Level이 갖는 노드의 개수를 Width라고 부른다.
- Tree의 Breadth : Leaf Node의 총 개수를 Tree의 Breadth라고 부른다.
- 노드의 Degree(차수) : 특정 노드와 연결된 Child Node의 개수를 노드의 Degree(차수)라고 부른다.
- Tree의 Degree(차수) : Tree에서 각 노드가 갖는 Degree중 최댓값을 Tree의 Degree(차수)라고 부른다.
- Tree의 Height(높이) : Root Node와 Leaf Node들의 거리 중 가장 큰 값을 Tree의 Height(높이)라고 부른다.
- Tree의 Size(크기) : Tree가 갖는 노드의 총 개수를 Tree의 Size(크기)라고 부른다.
- SubTree(부분 트리) : Tree에서 특정 노드와 그 노드의 모든 Decendants들을 포함하는 Tree를 SubTree라고 한다. 또 Fig2에 표시된 SubTree는 C노드의 left SubTree라고 한다.
Tree 종류
Fig3은 Tree의 종류를 정리한 것이다.
Tree 구현
다음 Fig4와 같은 간단한 Tree를 만들어보자. 본 포스트에서는 Tree 구조의 이해를 목적으로 하기 때문에 Tree 구조의 데이터 추가, 제거, 정렬 등의 함수는 다루지 않는다. Node가 갖는 데이터는 Int 구조로 한정했다.
Tree는 모든 노드가 연결된 그래프이기 때문에, Root Node에 대한 정보만 있으면 모든 Node에 접근할 수 있다. Node를 구현해야 하는데, Node는 필요한 데이터를 담을 변수와, 왼쪽 노드의 참조값을 저장할 변수, 오른쪽 노드의 참조값을 저장할 변수 세 가지로 구성하면 될 것 같다. Fig4에 표시한 Root Node의 left child와 right child에 3과 7을 표시했는데, 이 표기는 이해를 위한 것이며 실제로는 3과 7의 데이터를 담는 Node의 참조값을 저장하는 변수임을 주의하자.
Example1. 간단한 Tree 구현class Node(val data: Int, var left: Node? = null, var right: Node? = null)
class Tree(val root: Node)
fun main() {
val tree = Tree(Node(5))
tree.root.left = Node(3, null, Node(4))
tree.root.right = Node(7)
}
Tree 순회(traversal)
Graph 순회에서 Stack을 이용한 DFS, Queue를 이용한 BFS를 알아봤었다. Tree도 Graph의 일종이므로 물론 DFS, BFS 방법이 가능하지만, Tree를 순회하는 방법은 보통 preorder(전위 순회), inorder(중위 순회), postorder(후위 순회), level-order(레벨 순서 순회) 네 가지 경우로 나뉜다.
순회할 때 필요한 노드 변수는 Root Node와 Left Node, Right Node이다. Left Node는 항상 Right Node보다 먼저 나오고, 순회의 기준은 Root Node가 된다. 즉 preorder는 Root Node를 먼저 탐색한다는 의미, inorder는 Root Node를 중간에 탐색한다는 의미, postorder는 Root Node를 제일 나중에 탐색한다는 의미이다. Fig5–1은 순회할 Tree 예제와 순회 방법에 따른 결과이고, Fig5–2는 Tree 순회를 영상으로 나타낸 것이다.
preorder는 Graph 순회의 DFS, leve-order는 Graph 순회외 BFS와 유사한 것을 확인할 수 있다. Example2는 Tree를 순회한 것을 코드로 작성한 것이다. 재귀함수 호출을 이용하여 구현하였다.
Example2. Tree traversal 구현class Node(val data: Char, val left: Node? = null, val right: Node? = null)
class Tree(val root: Node){
//preorder 구현
fun preorder(){
fun preorderInternal(node:Node){
print("${node.data} ")
if(node.left!=null) preorderInternal(node.left)
if(node.right!=null) preorderInternal(node.right)
}
preorderInternal(root)
println()
}
//inorder 구현
fun inorder(){
fun inorderInternal(node:Node){
if(node.left!=null) inorderInternal(node.left)
print("${node.data} ")
if(node.right!=null) inorderInternal(node.right)
}
inorderInternal(root)
println()
}
//postorder구현
fun postorder(){
fun postorderInternal(node:Node){
if(node.left!=null) postorderInternal(node.left)
if(node.right!=null) postorderInternal(node.right)
print("${node.data} ")
}
postorderInternal(root)
println()
}
}
fun main() {
val tree = Tree(Node('A',Node('B',Node('D'),Node('E')),Node('C',Node('F'),Node('G'))))
print("preorder result : ")
tree.preorder()
print("inorder result : ")
tree.inorder()
print("postorder result : ")
tree.postorder()
}
/*결과:
preorder result : A B D E C F G
inorder result : D B E A F C G
postorder result : D E B F G C A
*/
Kotlin에서 Tree 이용
Kotlin에서 제공되는 클래스 중 Tree를 자료구조로 이용하고 있는 클래스는 많겠지만, Collection frameworks에 포함된 클래스만 이야기해보려고 한다. Collection Frameworks의 TreeMap은 Balanced Binary Search Tree인(균형 이진 탐색 트리) Red-Black Tree로 구현되어 있으며, TreeSet은 TreeMap을 이용하여 구현되어 있다. 또 Priority Queue는 Complete Binary Tree인 Heap으로 구현되어 Max Heap이나 Min Heap으로 사용할 수 있다.
Reference
Tree에 쓰이는 용어 part
1. [Wikipedia] “Tree (data structure)” — https://en.wikipedia.org/wiki/Tree_(data_structure)
2. [heejeong Kwon] “[자료구조] 트리(Tree)란” — https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html
Tree 종류 part
3. [Programiz] “Balanced Binary Tree” — https://www.programiz.com/dsa/balanced-binary-tree
