1. 트리 (Tree)
트리 개념
노드끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프
- Unrooted tree : 부모 자식 관계가 정의되지 않은 트리 (루트 노드 존재하지 않음)
- Rooted tree : 부모 자식 관계가 정의되어 있는 트리로, 루트 노드는 단 하나만 존재합니다.
Unrooted tree에서 루트 노드는 사람이 정하기 나름입니다.
트리 용어
- 노드(정점) : 각 지점을 의미합니다.
- 간선(에지) : 두 노드를 연결하는 선을 의미합니다.
- 루트 노드: 트리에서 맨 꼭기를 의미합니다.
- 부모, 자식: 트리에서 연결된 두 노드의 관계를 의미하는데, 더 위쪽에 있는 노드를 부모 노드, 아래쪽에 있는 노드를 자식 노드라고 부릅니다. 한 노드의 자식노드 개수는 제한이 없지만, 부모 노드는 최대 1개만 존재합니다.
- 차수: 특정 노드를 기준으로, 자식의 수가 얼마나 되는지 의미합니다.
- 깊이: 루트 노드와 얼마나 떨어져 있는지를 가리키는 말입니다.
- 높이: 트리에서 깊이가 가장 깊은 노드의 깊이에 1을 더한 값을 의미합니다.
- 리프 노드: 자식을 갖고 있지 않은 노드를 의미합니다.
Unrooted tree에서의 차수는 노드에 연결된 간선의 개수이고, 리프 노드는 차수가 1인 노드입니다.
2. 이진 트리 (Binary Tree)
이진트리 개념
- 모든 노드의 자식의 수가 최대 2개인 트리입니다. (자식의 수가 1개, 0개 될 수 있음)
- 배열로도 구현이 가능(0번 인덱스 값은 비우고 루트 노드를 1번에 넣고 시작)하며, 자식이 없는 경우 배열에도 칸을 비워둡니다.
- 특정 노드의 위치가 i라고 하면, 왼쪽 자식의 위치는 i*2, 오른쪽 자식의 위치는 i*2+1이 됩니다. 또한, 특정 노드의 위치가 i라고 하면, 부모 노드의 위치는 i/2가 됩니다.
이진트리의 탐색
이진트리는 재귀를 사용하면 탐색을 비교적 쉽게 구현할 수 있습니다. 어떤식으로 방문하는 순서에 따라, 전위 탐색(Preorder Traversal), 중위 탐색(Inorder Traversal), 후위 탐색(Postorder Traversal) 크게 세 가지로 나뉩니다.
- 전위 탐색 : 부모 - 왼쪽 자식 - 오른쪽 자식순으로 탐색합니다. 모든 노드에 대해 부모를 먼저 방문하고, 왼쪽 자식들을 전부 순회하고, 그 이후에 오른쪽 자식들을 순회합니다.
- 중위 탐색 : 왼쪽 자식 - 부모 - 오른쪽 자식순으로 탐색합니다. 모든 노드에 대해 왼쪽 자식들을 먼저 전부 순회한 후, 부모를 방문하고, 그 이후에 오른쪽 자식들을 순합니다.
- 후위 탐색 : 왼쪽 자식 - 오른쪽 자식 - 부모순으로 탐색합니다. 모든 노드에 대해 왼쪽 자식들을 먼저 전부 순회한 후, 오른쪽 자식들을 전부 순회하고, 그 이후에 부모를 방문합니다.
3. 이진 탐색 트리 (Binary Search Tree)
이진탐색트리 개념
부모의 왼쪽 방향에 있는 모든 노드들이 부모보다 값이 작고, 부모의 오른쪽 방향에 있는 모든 노드들 부모보다 값이 큰 이진트리입니다.
이진탐색트리의 탐색
루트 노드에서 시작하여, 찾고자 하는 값(x)과 일치하기 전까지 계속 이동합니다. 만약, 찾고자 하는 값(x)이 없는 경우라면, 탐색 도중 노드가 null 위치(비어있는 위치)로 이동하게 됩니다.
- 현재 노드(node)의 값 > 찾는 값(x)인 경우 : 찾는 값(x)은 현재 노드의 왼쪽에 있으므로, node.left로 이동합니다.
- 현재 노드(node)의 값 < 찾는 값(x)인 경우 : 찾는 값(x)은 현재 노드의 오른쪽에 있으므로, node.right로 이동합니다.
function bst.search(x)
set node = bst.root // root에서 시작합니다.
while node != null and node.value != x // node에 들어있는 값이 x가 되기 전까지 계속 반복합니다.
if node.value > x // 노드에 있는 값이 x보다 크다면
node = node.left // 왼쪽 자식으로 내려와 탐색을 진행합니다.
else // 노드에 있는 값이 x보다 작다면
node = node.right // 오른쪽 자식으로 내려와 탐색을 진행합니다.
return node // 최종 위치를 반환합니다.(x가 없는 경우에는 null)이진 탐색 트리에서 중위탐색을 하면, 오름차순으로 정렬된 순서대로 결과가 나오게 됩니다.
이진탐색트리의 삽입
루트 노드에서 시작하여, null에 도달하기 전까지 계속 이동합니다. 만약, null인 위치를 찾았다면, 해당 지점에서의 parent 정보를 이용해서 값 x를 넣어줍니다. 이때, parent 정보는 처음 루트에서 시작하여 node가 이동하기 직전의 위치를 계속 적어주는 식으로 쉽게 구현이 가능합니다.
- 트리에 노드가 전혀 없는 경우 : 이때 parent 값은 null이며, 이진 탐색 트리의 루트를 node(x)로 설정해줘야 합니다.
- parent의 값 > 삽입하려는 값(x)인 경우 : parent의 왼쪽에 node(x)를 넣어줘야 합니다.
- parent의 값 < 삽입하려는 값(x)인 경우 : parent의 오른쪽에 node(x)를 넣어줘야 합니다.
function bst.insert(x)
set node = bst.root // root에서 시작합니다.
set parent = bst.root // parent도 root로 설정하고 시작합니다.
while node != null // node가 null이 되기 전까지 반복합니다.
parent = node // parent는 항상 node가 움직이기 직전의 위치로 갱신해줍니다.
if node.value > x // node에 적혀있는 값이 x보다 크다면
node = node.left // 왼쪽 자식으로 이동해야 합니다.
else // node에 적혀있는 값이 x보다 작다면
node = node.right // 오른쪽 자식으로 이동해야 합니다.
if parent == null // Case 1. 비어있는 tree라면
bst.root = node(x) // root를 node(x)로 설정해줍니다.
else if parent.value > x // Case 2. parent에 적혀있는 값이 추가하려는 값 x보다 크다면
parent.left = node(x) // parent의 왼쪽에 node(x)를 넣어줍니다.
else // Case 3. parent에 적혀있는 값이 추가하려는 값 x보다 작다면
parent.right = node(x) // parent의 오른쪽에 node(x)를 넣어줍니다.
이진탐색트리의 삭제
먼저 루트 노드에서 시작하여, 찾고자 하는 값(x)과 일치하기 전까지 계속 이동하는 탐색 과정을 진행합니다. 만약, 찾고자 하는 값(x)이 있는 경우라면, 아래의 3개의 과정 중 하나를 진행합니다.
- 해당 노드(node)의 왼쪽 노드가 비어있는 경우 : 해당 노드(node)의 오른쪽을 위로 올려줍니다.
- 해당 노드(node)의 오른쪽 노드가 비어있는 경우 : 해당 노드(node)의 왼쪽을 위로 올려줍니다.
- 해당 노드(node)의 왼쪽 및 오른쪽 노드가 전부 채워져 있는 경우 : 해당 노드(node)를 기준으로 더 크면서 가장 작은 값을 갖는 노드인 successor를 찾습니다. 이후 successor에 있는 값을 node에 옮겨준 뒤, successor의 오른쪽을 위로 올려줍니다.
- 이때 successor는 현재 node의 오른쪽 자식인 node.right를 시작으로 계속 내려갈 수 있는 만큼 왼쪽으로 내려가는 방식으로 구현 할 수 있습니다.
- successor가 node.right(node의 오른쪽 자식)인 경우에는 단순히 node의 오른쪽을 위로 올려줍니다.
function bst.search(x)
set node = bst.root
while node != null and node.value != x
if node.value > x
node = node.left
else
node = node.right
return node
function bst.minimum(node) // node 하위 트리에서 최솟값을 구합니다.
while node.left != null // node의 left가 null이 아니면 계속 내려갑니다.
node = node.left
return node // 최종 node의 위치를 반환합니다.
function bst.delete(x) // x를 찾아 삭제하는 함수입니다.
set node = bst.search(x) // x 값을 찾습니다.
if node.left == null // Case 1. node의 왼쪽 자식이 비어있다면
move(node.right, node) // 오른쪽 자식을 위로 올려줍니다.
else if node.right == null // Case 2. node의 오른쪽 자식이 비어있다면
move(node.left, node) // 왼쪽 자식을 위로 올려줍니다.
else // Case 3. 왼쪽 오른쪽 자식이 모두 채워져있다면
set succ = bst.minimum(node.right) // 해당 노드의 successor를 구합니다.
// 이는 현재 노드의 오른쪽 자식에서 시작하여 계속 왼쪽으로 내려가는 것을 반복하면 가능합니다.
if succ == node.right // 만약 successor가 현재 노드의 오른쪽 자식이라면
move(node.right, node) // 오른쪽 자식을 위로 올려줍니다.
else // 그렇지 않은 일반적인 경우라면
node.value = succ.value // node의 값을 successor의 값으로 대체시켜준 뒤,
move(succ.right, succ) // successor의 오른쪽 자식을 위로 끌어올려줍니다.
삽입·삭제·탐색의 시간복잡도
- 균형 잡힌 이진탐색트리 : 삽입/삭제/탐색의 시간복잡도가 모두 O(logN)이 됩니다.
- Red Black Tree나 AVL Tree 같이 이진탐색트리를 특정 규칙에 따라 관리함으로써, 균형 잡힌 이진탐색트리를 유지할 수 있습니다.
- 이는 삽입, 삭제가 일어나는 순간 루트 노드와 주위에 있는 노드를 회전 등의 작업을 통해 적절하게 조절하여, 왼쪽 자식과 오른족 자식에 있는 노드간의 높이 차가 크게 벌어지지 않도록 하는 방법입니다. 따라서, 이를 이용하면 트리의 높이를 항상 logN으로 유지시킬 수 있기 때문에 삽입, 삭제, 탐색의 시간이 O(logN)이 됨을 보장합니다.
- 균형 잡히지 못한 일반 이진탐색트리 : 삽입/삭제/탐색의 시간복잡도가 모두 O(N)이 됩니다.
예시 문제
동일한 값을 트리에 저장한다 하더라도, 값을 어떤 순서에 넣냐에 따라 다른 결과가 나옵니다. 다음과 같은 트리가 있다고 가정할 때, 이 트리를 만들 수 있도록 하는 모든 순서의 경우의 수는?
자식 노드들은 반드시 부모 노드보다 늦게 들어가야 합니다. 때문에 3 - 6 - (4,8) 순서로 들어가야 하고, 3 - 1 순서로 들어가야 합니다. 임의대로 4,8의 순서를 4 - 8로 지정한 경우, 1이 들어갈 수 있는 순서를 보면 다음과 같이 4가지가 존재합니다.
- 3 - 1 - 6 - 4 - 8
- 3 - 6 - 1 - 4 - 8
- 3 - 6 - 4 - 1 - 8
- 3 - 6 - 4 - 8 - 1
또한, 4와 8의 순서를 바꿀 수 있으므로, 추가로 4가지의 순서가 존재합니다.
- 3 - 1 - 6 - 8 - 4
- 3 - 6 - 1 - 8 - 4
- 3 - 6 - 8 - 1 - 4
- 3 - 6 - 8 - 4 - 1
따라서 총 8가지 순서가 존재합니다.
4. 힙 (Heap)
완전 이진트리
트리의 모든 값이 왼쪽에서 순서대로 차 있는 것을 의미합니다. 완전 이진트리를 배열에 채우게 되면, 중간에 비는 값 없이 일자로 채워집니다.
힙 개념
항상 최댓값/최솟값이 무엇인지 알 수 있는 자료구조로, 종류에는 max-heap, min-heap이 있습니다.
- max-heap : 완전 이진트리를 띄는 구조 안에서, 모든 노드에 대해 부모 노드 ≥ 자식 노드를 만족합니다. 루트 노드에는 항상 전체 숫자 중 최댓값이 들어 있습니다.
- min-heap : 완전 이진트리를 띄는 구조 안에서, 모든 노드에 대해 부모 노드 ≤ 자식 노드를 만족합니다. 루트 노드에는 항상 전체 숫자 중 최솟값이 들어 있습니다.
힙의 특징
- 삭제는 항상 루트 노드만 가능합니다. 즉, 루트를 제외한 특정 값을 삭제하는 것은 불가능합니다.
- 항상 가장 큰 값/작은 값이 무엇인지만 알 수 있고, k번째 최댓값/최솟값은 구할 수 없습니다. 즉, 힙에서 의미있는 데이터는 루트값 단 하나이기 때문에, 탐색 자체는 의미가 없습니다.
Max-Heap의 생성 과정
n/2 번째 원소부터 거꾸로 1번째 원소까지 순서대로 보면서 heapify 과정을 거칩니다. heapify란 현재 노드를 기준으로 이 노드가 heap 특성에 맞을 때까지 계속 밑으로 내려주는 과정을 말합니다.
- 현재 노드 위치를 i라고 한다면, 현재 노드, 왼쪽 자식(i * 2번째) 노드, 그리고 오른쪽 자식(i * 2 + 1번째) 노드 중 가장 큰 노드가 무엇인지 판단합니다. 이 세 노드 중 가장 큰 노드를 편의상 largest 노드라고 하겠습니다.
- 만약 largest 노드가 현재 노드 i가 아닌 자식 노드라면, 현재 노드(i)와 해당 자식 노드(largest)의 값을 교환합니다. 교환 이후에는 다시 largest 위치에서 heapify를 진행합니다. 이렇듯 현재 노드가 heap 조건을 만족하도록 계속 내려주는 것을 재귀적으로 반복해줍니다.
- 만약 현재 노드 i의 자식 노드가 없거나 largest 노드가 현재 노드 i라면, 종료합니다.
// i번째 노드가 max-heap 조건을 만족하도록,
// 자식 노드와 비교하여 더 큰 노드가 현재 노드가 아니라면 계속 밑으로 내려가 주는 함수
출처: https://wus22.tistory.com/79 [공부기록:티스토리]
function heapify(arr[], n, i)
set largest = i // 최대 노드가 i번이라고 가정합니다.
set l = i * 2 // 왼쪽 자식 노드 번호입니다.
set r = i * 2 + 1 // 오른쪽 자식 노드 번호입니다.
if l <= n && arr[l] > arr[largest] // 왼쪽 자식이 크다면, 최대 번호를 수정합니다.
largest = l
if r <= n && arr[r] > arr[largest] // 오른쪽 자식이 크다면, 최대 번호를 수정합니다.
largest = r
if largest != i // 최대 노드가 자식 노드라면
swap(arr[i], arr[largest]) // 해당 자식과 현재 노드를 교환해준 뒤
heapify(arr, n, largest) // 내려간 위치에서 다시 heapify를 진행합니다.
// n개의 원소가 주어졌을 때, max-heap을 만들어 주는 함수
function build_heap(arr[], n)
for i = n / 2 ... i >= 1 // n / 2번째 원소부터 1번째 원소까지 돌며
heapify(arr, n, i) // heapify 과정을 진행하여 max-heap을 만들어줍니다.
힙의 삽입
- 완전 이진트리를 만족시킬 수 있게, 트리의 맨 끝에 값을 붙힙니다.
- 이후, 현재 삽입된 값을 기준으로 부모와 값을 계속 비교하며, 부모 값이 더 작다면 두 값을 교환해주는 것을 반복합니다.
function insert(arr[], n, x)
arr.append(x) // 가장 끝에 노드 x를 추가합니다.
set i = n + 1 // 마지막 노드에서 시작합니다.
while i > 1 and arr[i / 2] < arr[i] // 부모가 자식보다 값이 작은 경우라면
swap(arr[i], arr[i / 2]) // max-heap 조건에 어긋나므로, 두 값을 교환하고
i = i / 2 // 부모 위치로 올라갑니다.
힙의 삭제
- 힙은 루트에서만 값 삭제가 이루어지므로, 루트의 값을 삭제합니다.
- 완전 이진트리를 만족시킬 수 있게, 트리의 맨 끝 값을 루트로 올립니다.
- 이후, 힙의 특성을 만족하게 만들기 위해, heapify(1)을 수행합니다.
function remove(arr[], n)
arr[1] = arr[n] // 가장 끝에 있는 노드를 첫 번째 노드에 옮겨주고
delete arr[n] // 가장 마지막 노드를 삭제합니다.
heapify(arr, n - 1, 1) // 직후에 1번 노드를 기준으로 heapify를 진행하여, max-heap 상태를 계속 유지해줍니다.
시간복잡도
- 처음 max/min-heap을 만들 때 총 n/2개의 원소에 대해 heapify 과정을 거치게 되며, 각 노드별로 최대로 움직이게 되는 횟수를 고려하여 엄밀히 계산했을 때 시간은 O(N)이 소요됩니다.
- 이후, 특정 원소 하나를 삽입·삭제할 때는 원하는 heap 구조를 유지하기 위해 트리의 높이인 O(logN)만큼의 시간이 소요됩니다.
- 루트 노드에는 항상 최댓값/최솟값이므로, 주어진 수들 중 최댓값/최솟값을 구하는 데 O(1)이 소요됩니다.
만약, 최댓값/최솟값을 단 한 번만 찾아야하는 경우라면, heap을 만든 뒤 루트 노드를 봐야하므로 시간이 O(N)만큼 소요됩니다. 이러한 경우라면 순차탐색을 통해 O(N)에 최댓값을 찾는 것이 더 편리합니다.
따라서, 원소의 추가와 최댓값의 삭제가 빈번하게 일어나는 상황에서, 현재 남아있는 원소들 중 최댓값/최솟값을 빠르게 계속 얻는 경우에 유용합니다.
예시 문제
다음과 같은 최소 힙이 있을 때, 노드 1 ~ 노드 5까지의 삽입 연산 순서의 가능한 경우의 수는?
들어가야 할 순서가 정해지는 노드를 위주로 경우의 수를 생각해보겠습니다.
- 노드 5는 반드시 3번째 순서로 들어가야합니다. 왜냐하면, 1,2번째 순서로 들어가면 1의 왼쪽으로 내려갈 것이고, 4,5번째 순서로 들어간다면 2의 자식들 중 하나가 되었을 것이기 때문입니다.
- 5의 순서를 3번째로 고정시키고 나면, 나머지 1,2,3,4 노드로 4! = 24가지 경우의 수가 생깁니다.
- 노드 4는 절대로 5번째 순서에 들어갈 수 없습니다. 왜냐하면, 사이즈가 4짜리 힙이 만들어질 때, 이미 3이 부모 자식간 교환과정에서 2의 왼쪽으로 이동하고 더이상 이동하지 않기 때문입니다.
- 4가 5번째 순서로 들어가는 경우의 수는 3! = 6입니다.
따라서, 5가 3번째로 들어가고 4가 5번째로 들어가지 않는 전체 경우의 수는 24 - 6 = 18가지 입니다.
'Data Structure & Algorithm > 알고리즘(Algorithm)' 카테고리의 다른 글
| 07. 해싱 (0) | 2024.07.05 |
|---|---|
| 05. 스택, 큐, 덱 (0) | 2024.06.20 |
| 04. 이진탐색 (0) | 2024.06.18 |