시작하기
이어서 Graph, Tree, Heap, Priority Queue을 알아보자.
Graph
Graph는 Node와 Edge로 이루어져 있다. 간단히 설명하자면 점(Node)과 선(Edge)으로 그려진 지도같은 형태이며 점과 점을 선으로 잇고 있는 형태이다. Edge는 방향성을 지닐 수 있으며, 가중치 또한 가질 수 있다. 여기서 가중치란 Edge의 비용이라고 이해해도 된다.
사실 Graph 자체도 직접 구현해볼 수 있으나 실제적으로 자주 사용되는 것은 Graph 중 Tree이기에 Tree로 바로 넘어가본다.
Tree
Graph의 일종이며 Node와 Edge로 이뤄어져 있으며 tree 구조로 배열된 계층적 데이터 구조이다.
기본 개념
- parent node: 연결된 두 node 중 edge가 시작되는(출발하는)쪽 node
- child node: 연결된 두 node 중 edge가 끝나는 쪽 node
- root node : tree의 시작이 되는 node이며 parent node를 갖지 않는다.
- leaf node : node들 중 child node를 갖지 않는 node를 말한다.
- tree의 height : tree에서 leaf node들 까지의 거리 중 가장 먼 것을 의미한다.
- node의 depth : root node에서 해당 node까지 edge의 갯수를 의미한다.
- node의 level : 특정 depth를 갖는 node의 집합
이진 트리(binary-tree)
tree들 중 가장 일반적인 것이 이진 트리 입니다. 특징으로는 각 node는 child를 최대 2개까지만 가질 수 있습니다.
이진 트리의 종류
- full binary tree(정이진 트리) : 노드의 자식이 0 or 2개인 것
- complete binary tree(완전 이진 트리) : 마지막 level을 제외하고는 node가 꽉 차 있으며, 마지막 level의 경우 왼쪽부터 채워지는 트리. Heap 자료 구조가 이를 사용한다.
- perfect binary tree(포화 이진 트리) : 모든 노드가 꽉 차 있는 이진 트리이다.
- balanced binary tree(균형 이진 트리) : 왼쪽과 오른쪽 노드의 높이가 1이하인 트리. AVL tree, Red-Black tree가 이를 이용한다.(두 개 다 잘 알지는 못한다...)
- binary serach tree(이진 탐색 트리) : 각 노드의 왼쪽 하위 트리에는 node보다 작은 값들이, 오른쪽 하위 트리에는 node보다 큰 값들이 있다.
간단한 이진 트리 구현
data class Node(
var value: Int,
var left: Node? = null,
var right: Node? = null
)
data class Tree(val root: Node)
fun main() {
val a = Node(1)
val b = Node(2)
val t = Tree(a)
a.right = b
println(t.root.right?.value)
}
Tree traversal(트리 순회)
- preorder : Root 먼저 탑색
- inorder : Root는 중간에 탐색
- postorder : Root는 마지막에 탐색
- level-order : 같은 레벨 먼저 탐색
참고자료
https://medium.com/depayse/kotlin-data-structure-tree-b8518d233f9d
Heap
complete binary tree를 기반의 자료구조 이며, 최소힙과 최대힙 두가지고 있고 해당 힙에 따라 특정한 특징을 지킨 트리이다.
최대힙의 경우 각 node의 값은 모든 자신의 자식들 중 가장 커야 하며, 각각의 자식 node들에 대해서도 재귀적으로 같은 규칙이 적용되어야 한다. 최소힙의 경우 그 반대이다.
Heap에서의 삽입
최대힙의 가정하고 설명한다.
1. Heap은 complete binary tree 기반이므로 마지막 노드의 위치에 새 요소를 넣는다.
2. 자신의 부모 node와 비교하여 더 클 경우 값을 교체한다.
3. 자신의 부모 node보다 작아질 때 까지 이를 반복한다.
Heap에서의 삭제
최대값을 제거하는 경우이다.
1. 최대값을 나타내는 root node의 값을 삭제한다.
2. 마지막 node의 값을 root node로 옮기고 마지막 node 제거
3. root node의 두 child node중 더 큰 쪽과 현재 root node의 값을 비교하여 heap의 규칙을 맞춰준다.
4. 이를 반복적으로 시행한다.
in kotlin
kotlin에서는 따로 Heap을 제공하지 않는다. 그 대신 다른 방식으로 Heap을 만나볼 수 있다. 이는 바로 priority queue이다.
Priority Queue
우선순위 큐이며 기본 queue의 경우 FIFO를 따르지만, priority queue의 경우 우선순위가 높은 요소가 가장 먼저 제공된다. 이 priority queue가 Heap을 기반으로 구현된다.
in kotlin
kotlin의 priority queue의 경우 element Type에 compareTo가 정의되어 있지 않으면 comparator를 제공해줘야 한다. 그렇지 않은 경우라도 custom comparator를 제공해 줄 수 있다.
import java.util.*
val a = PriorityQueue<Int>()
a.addAll(arrayOf(1,6,3,8,0,4))
a.offer(11)
println(a.peek()) // 11
println(a.poll()) // 11
val b = PriorityQueue<String>() { a, b ->
a.length.compareTo(b.length)
}
b.addAll(arrayOf("sdf", "123123", "23424", "z"))
println(b) // [z, sdf, 23424, 123123]