[자료구조 기초] Data Structure 3
이번 시간에는 그래프에 대해 간단히 말씀드린 뒤, 자료구조 중 그래프의 ‘트리(Tree)’형태로 구현이 되는 ‘힙(Heap)’과 ‘이진 탐색 트리(Binary Search Tree)’에 대해 간단히 설명드리겠습니다.
그래프의 경우 시각화가 되는 편이 좋으므로 개인적으로는 알고리즘 도감 앱의 애니메이션을 참조하시면 좋지만 이번 자료구조 두개는 유료버전(3,900원)으로 해제되므로 적극 추천을 못해드리는…ㅠㅠ
1. Graph, Tree
CS(Computer Science)나 이산수학에서 그래프는 각 지점이 되는 ‘정점(node)’과 이를 연결하는 ‘간선(link)’으로 각 데이터와 연결관계들을 표현합니다.
예를 들어 라우터를 정점으로 한 네트워크 관계와 같은 데이터들을 표현할 때 편리합니다.
그림 출처 : https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/
그래프에서 간선에는 아무런 덧붙임 없이도 단순한 선으로 각 정점을 연결할 수 있지만 위의 그림과 같이 ‘가중치(cost)’나 ‘방향성’을 부여할 수도 있습니다.
‘가중치’는 기존 간선으로 표현되는 ‘연결되거나’ ‘연결되지 않거나’ 두 속성에 더해 ‘연결 정도’를 추가하게
되지만, 이로서 표현되는 ‘정도’의 의미는 그래프로 표현하고자 하는 자료에 따라 달라지게 됩니다.
(더 심화하여 정점에도 가중치를 부여하는 경우들이 있습니다.)
예를 들어 위에서 예시로 든 네트워크 관계 그래프의 경우 간선의 가중치를 통신시간으로 하면 네트워크 통신시간을 표현하는 그래프로 바꿀 수 있습니다.
또한 ‘방향성’을 간선에 부여해 ‘방향성 그래프’를 만드는 것으로 기존 데이터에 새로운 의미를 부여할 수 있습니다. 위의 첫번째 그래프(G)의 경우 일방통행 방향이 부여되어 s정점과 w정점사이 이동이 s→w만 가능한 것으로 바뀝니다.
이런 그래프의 정점, 간선, 가중치, 방향성이 잘 정리된 자료들은 주로 경로문제와 같은 문제상황을 정리하는데 효율성을 높일 수 있습니다.
Tree
Tree(트리)는 위의 그림처럼 폐로(閉路, 시점과 종점이 같은 경로)가 없어 아래같이 나무를 뒤집은 형태로 나타낼 수 있는 그래프입니다.
그림 출처 : https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/
위와 같이 폐로가 없는 형태로 인해 깊이나 층(Level) 표현이 가능하며, 각 데이터 노드 사이 ‘부모-자식’의 상관관계를 표현할 수 있어 CS에서 자료구조를 표현하는데 자주 사용됩니다.
가장 꼭대기의 노드는 ‘root’라고도 표현하며 가장 말단의 자식 노드들은 ‘leaf’라고도 표현합니다.
(가장 위가 root여서 위에서 나무를 뒤집었다고 표현했습니다.)
특히 트리에서 모든 부모 노드들이 가질 수 있는 최대 자식 노드 수가 2개로 제한되는 형태를 ‘이진 트리(Binary Tree)’라고 표현하며 오늘 말씀드릴 ‘힙’이나 ‘이진 탐색 트리’가 이에 속합니다.
2. Heap
Heap(힙)은 앞에 Queue의 응용형으로 ‘Priority Queue(우선순위 큐)’를 구현하는데 사용하는 자료구조라는 이야기를 잠시 언급했습니다.
힙은 이진트리의 형태로 구현되는 자료구조로 루트 노드가 최솟값으로 시작하는 Min Heap(최소 힙)과 역으로 최댓값으로 시작하는 Max Heap(최대 힙)으로 나뉩니다.
또한 힙의 트리는 데이터가 위에서부터, 같은 Level에서는 왼쪽에서부터 채워져 나갑니다.
아래는 최대 힙의 예시 그림으로서 배열에 어떻게 자리잡는지도 함께 보여줍니다.
그림 출처 : https://www.zerocho.com/category/Algorithm/post/582de223d4416a001860e763
힙은 최대 힙이냐 최소 힙이냐에 따라 다르지만 각각 최댓값과 최솟값을 자주 추출해나가는 형태의 알고리즘에서 잘 사용됩니다. 대표로 항상 최솟값 순서로 추출되는 우선순위 큐 구현, 힙 정렬 등이 있습니다.
루트 노드가 항상 최댓값 혹은 최솟값을 유지하기에 이들을 추출하는 시간은 다음과 같습니다.
최솟값(최소 힙) 혹은 최댓값(최대 힙) 추출 : O(1)
그리고 이렇게 데이터가 추출되거나 혹은 새로 추가된 경우 힙의 구조를 유지하고 다음 추출을 대비하기 위해 재정렬이 이뤄져야 합니다. 재정렬은 각각 다음 순서를 따릅니다.
데이터 추가 (아래(추가 데이터) → 위 체크)
1. 우선 빈 자리 노드에 새로운 데이터를 추가합니다. (위에서부터, 같은 레벨은 왼쪽부터)
2. 부모 노드와 비교해 힙 조건이 맞지 않으면 서로를 교환합니다. (최대 힙: 부모가 커야함)
3. 2의 부모-자식 교환처리를 조건이 다 맞을 때까지 반복하며 올라갑니다.
기존 힙 데이터의 부모 자식간 대소관계는 정리되어 있기에, 새로 추가된 데이터와 그 부모 노드 사이의 관계만 체크해 나가면 됩니다. (최대 힙을 예로, 새 데이터가 부모노드와 교환되어도 이는 기존 부모노드 보다 크다는 것이기에 자식이 된 기존 노드와 관계체크를 할 필요가 없습니다.)
데이터 추출 후 재정렬 (위 → 아래 체크)
1. 최하단 + 제일 오른쪽(=최후미)의 노드를 추출 후 비어있는 루트노드로 이동합니다.
2. 자식 노드 중 최대 힙은 더 큰, 최소 힙은 더 작은 값의 노드와 교환합니다.
3. 1의 최후미 노드를 기준으로 2를 힙조건에 맞을 때까지 계속 반복합니다.
힙은 부모 자식간의 대소관계 유지만으로 후보 관리를 함으로 위 방법을 통해 구조를 유지할 수 있습니다.
이렇게 힙은 재구축 과정이 트리의 각 level의 부모-자식간 대소 비교가 위→아래(추출 후 재구축) 혹은 아래→위(추가 후 재구축) 방향으로 최대 한 번 씩 발생합니다.
그리고 이진 트리 구조기 때문에 트리의 총 높이 즉 level은 전체 데이터 수 n에 대해 밑이 2인 로그값을 (log n) 취합니다.
따라서 힙의 재구축 시간을 빅오로 표현하면 다음과 같습니다. (빅오에서 로그의 밑은 무시됨)
힙 재구축 시간 : O(log n)
힙의 최소 혹은 최댓값 추출은 O(1)이고 재구축에 걸리는 시간은 O(log n)로
힙은 구현은 어려우나 O(n log n)정렬 등이 가능한 시간효율이 매우 뛰어난 자료구조입니다.
3. Binary Search Tree
Binary Search Tree(이진 탐색 트리)는 추후 포스팅할 탐색 알고리즘에서 이진 탐색 개념을 트리형태의 자료구조로 만든 것입니다.
이진 탐색(Binary Search)에 대해 잠시 간단히 설명드리면 배열 탐색의 하나로, 순차 정렬이 이뤄져 있는 배열에서 현 탐색범위의 정중앙의 값과 탐색값을 비교해 범위를 절반씩 줄여가는 탐색 알고리즘입니다.
이를 이진 트리 형태의 자료구조로 만들기 위해 각 부모 노드는 왼쪽 자식보다는 크고 오른쪽보다는 작은 대소관계를 갖습니다. 이진 탐색 트리의 노드 특징은 좀 더 정리하면 다음과 같습니다.
1. 부모 노드의 값은 왼쪽 자식노드보다 크고 오른쪽보다 작습니다.
2. 각 노드는 자신의 왼쪽 가지에서 뻗어나간 어떤 노드의 값보다도 큽니다.
3. 각 노드는 자신의 오른쪽 가지에서 뻗어나간 어떤 노드의 값보다도 작습니다.
그림 출처 : https://www.crocus.co.kr/446
따라서 이 트리 자료구조를 다음과 같은 특징으로 최소, 최대 노드를 탐색할 수 있습니다.
1. 루트노드에서부터 왼쪽 가지만 나아가다보면 최솟값이 나옵니다.
이때, 자식노드가 남아도 오른쪽 가지로 가면 안됩니다. (위 그림에서 1)
2. 루트노드에서부터 오른쪽 가지만 나아가다보면 최대값이 나옵니다.
마찬가지로 자식노드가 남아도 왼쪽 가지로 가면 안됩니다. (위 그림에서 14)
또한 이진 탐색 개념을 구현한 구조인 만큼 특정 탐색 값에 대해 루트 노드부터 대소 비교를 하며 차례로
다음 레벨로 넘어가면 이진 탐색에서 절반씩 후보지를 지워가며 탐색하는 효과를 얻을 수 있습니다.
(탐색 값이 현재 노드 값보다 작으면 왼쪽 크면 오른쪽으로)
따라서 데이터 집합 전체를 이진 탐색 트리 구조로 처음 정렬하여 균형을 유지한 형태를 취한 경우
이진 탐색 트리 형태가 균형을 갖췄을 때 임의의 값 탐색시간 : O(log n)
의 효율을 뽑을 수 있습니다.
하지만 일반적인 이진 탐색 트리는 밑에 설명할 데이터의 추가, 삭제 후 각 노드 사이 조건이 충족되어도 균형이 어긋나 한쪽으로 치우치게 될 수 있으며, 이럴 경우 탐색 효율이 떨어져 최악의 경우
이진 탐색 트리가 직선에 가까운 형태를 취할 경우 탐색시간 : O(n)
의 탐색 시간을 갖게 될 수 있습니다.
따라서 이진 탐색 자료구조에서 데이터의 수정이나 추가가 자주 일어나는 경우는 ‘자가 균형 이진 탐색 (self-balancing binary search tree)’ 등의 확장형 자료구조를 찾아 구현하여 탐색효율을 유지하는 것도 고려해야 합니다.
마지막으로 이진 탐색 트리에서 데이터의 추가와 삭제에 대해 설명드리고 이번 포스팅을 마치겠습니다.
일반적인 이진 탐색 트리의 데이터 추가는 매우 간단합니다.
1. 추가 데이터를 루트노드의 값부터 대소 비교하며 내려갑니다.(작으면 왼쪽 크면 오른쪽)
2. 1를 비교 이동을 추가 데이터가 최하단 leaf 노드자리를 차지할 때까지 반복합니다.
데이터 삭제의 경우는 다음과 같이 처리합니다.
1. leaf를 삭제하는 경우 해당 노드의 삭제만 하면 됩니다.
2. 중간의 노드를 삭제할 경우 해당 노드 왼쪽 가지 아래 영역의 최댓값을 가져와 메꿉니다.
(각 노드는 왼쪽 가지 모든 값보다 크고 오른쪽 가지보다 작아야하므로)
3. 2의 과정에 빈 공간이 생긴다면(옮긴 노드가 자식이 있다면) 재귀적으로 2를 반복합니다.
이로서 자료구조 기초 포스팅을 마칩니다. 다음 시간부터는 기초적인 정렬 알고리즘을 다뤄보겠습니다.
언제나 읽어주셔서 감사합니다.^^
개인 공부용 블로그입니다.
잘못된 부분에 언제든지 댓글이나 메일로 지적해주시면 감사하겠습니다.
Leave a comment