Data Structure

Data Structure

그래프 (Graph)

---

정의

그래프는 실제 세계의 현상이나 사물을 정점(Vertex)과 간선(Edge)으로 표현을 하기 위해 사용한다. 비선형 자료구조이다.

표현

그래프는 인접 행렬(Adjacency Matrix) 또는 인접 리스트(Adjacency List)로 표현할 수 있다.

이진트리 (Binary Tree)

---

정의

모든 노드의 차수를 2 이하로 정해 전체 트리의 차수가 2 이하가 되도록 만든 것이 이진트리이다.
이진트리의 왼쪽 자식 노드와 오른쪽 자식 노드 2개만을 가질 수 있으며, 공백노드도 이진트리의 노드로 취급한다.
이진트리의 서브트리 모두 이진트리이다.

종류

이진트리는 포화 이진 트리(full binary tree), 완전 이진트리(Complete binary tree), 편향 이진트리(Skewed binary tree) 3가지가 있다. 포화 이진 트리는 모든 레벨에 노드가 꽉찬 이진트리를 말하며, 공백 노드가 없다.
완전 이진트리는 노드 개수가 n개일 때, 노드의 위치가 포화 이진트리의 노드 1번부터 n번까지의 위치와 완전히 일치하는 이진트리이다. 편향이진트리는 트리 중 최소 개수의 노드를 가지면서 왼쪽이나 오른쪽 서브트리만 가지고 있는 트리이다.

순회

전위순회 순서 : 현재노드 방문 -> 현재노드의 왼쪽 서브트리 이동 -> 현재노드 오른쪽 서브트리 이동
중위순회 순서 : 현재노드의 왼쪽 서브트리 이동 -> 현재노드 방문 -> 현재노드 오른쪽 서브트리 이동
후위순회 순서 : 현재노드의 왼쪽 서브트리 이동 -> 현재노드 오른쪽 서브트리 이동 -> 현재노드 방문

이진탐색트리 (Binary Search Tree)

---

정의

모든 원소는 값이 존재하고, 서로 다른 유일한 키를 갖는다.
왼쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 값이 작다.
오른쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 값이 작다.
왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리이다.

성능

평균적으로 원소의 탐색, 삽입, 삭제에 있어서 O(logN) 의 성능을 보장한다. 최악의 경우(한쪽으로 치우친 경우) O(n) 의 성능이 나온다.

삽입

삽입할 값이 현재 값보다 작으면 좌측으로, 크면 우측으로 이동하다가 비어있는 지점에 삽입한다.

삭제

3가지이 경우 삭제가 있다.

1) Leaf, 즉 자식이 없는 경우
2) 자식이 하나만 있는 경우
3) 자식이 좌측, 우측 모두 있는 경우

여기서 2) 경우는 왼쪽 자식인지, 오른쪽 자식인지로 나뉜다. 그리고 3) 경우 현재 노드를 지우고 그 자리에 채워넣을 값을 찾기 위해 두 가지 방법을 사용할 수 있는데

1) 우측 서브트리에서 Leftmost, 즉 가장 좌측에 있는 값 (가장 작은 값)
2) 좌측 서브트리에서 Rightmost, 즉 가장 우측에 있는 값 (가장 큰 값)

두 가지 방법을 사용할 수 있다. 사실 이진 탐색 트리에는 중복이 없기 때문에 어느 방법을 사용해도 상관없다.

AVL Tree

---

정의

AVL 트리란 서브트리의 높이를 적절하게 제어해 전체 트리가 어느 한쪽으로 늘어지지 않도록 한 이진탐색트리의 일종이다. 트리의 높이가 h일 때 이진탐색트리의 계산복잡성은 O(h)이기 때문에 균형된 트리를 만들어 h를 줄이고자 하는 발상에서 비롯됐다.

AVL 트리의 핵심 개념 가운데 하나가 Balance Factor(BF) 이다. 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 것이다. 두 서브트리의 높이가 같거나 잎새노드라면 BF는 0이다(empty tree의 BF -1로 정의).

AVL 트리는 요소를 삽입(insert)하거나 삭제(delete)하는 과정에서 서브트리를 재구성해 트리 전체의 균형을 맞춘다. 삽입/삭제 연산시 BF가 일정 값 이상(보통 2) 혹은 이하(보통 -2)로 바뀐 노드를 기준으로 그 서브트리들의 위치를 rotation하는 방식을 취한다. rotation에는 두 가지 방식이 있는데 삽입 연산을 중심으로 살펴보자.

rotation 설명 링크 : https://ratsgo.github.io/data%20structure&algorithm/2017/10/27/avltree/

B-Tree

---

정의

전산학에서 B-트리는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 노드내 최대 데이터 수가 2개라면 2차 B-Tree, 3개라면 3차 B-Tree 라고 말한다.

성립 조건

노드의 데이터 수가 n개라면 자식 노드의 개수가 n+1 개입니다.
노드의 데이터는 반드시 정렬된 상태여야 한다.
노드의 자식 노드 데이터들은 노드 데이터를 기준으로 데이터보다 작은 값은 왼쪽 서브 트리에 큰 값들은 오른쪽 서브 트리에 이루어져야 한다.
Root 노드가 자식이 있다면 2개 이상의 자식을 가져야 한다.
Root 노드를 제외한 모든 노드는 적어도 M / 2 개의 데이터를 갖고 있어야 한다.
Leaf 노드로 가는 경로의 길이는 모두 같아야 한다. 즉, Leaf 노드는 모두 같은 레벨에 존재해야 한다.

탐색

B-Tree는 이진트리와 마찬가지로 작은 값은 왼쪽 서브트리, 큰 값은 오른쪽 서브트리에 이루어져 있다. 탐색하고자 하는 값을 root 노드부터 시작해 하향식으로 탐색해 나간다.

삽입

차수에 따라 B-Tree 알고리즘이 다르다. 3차(홀수) B-Tree를 예시로 들어보자.

초기 삽입시에는 root 노드를 생성한다
데이터를 탐색해 해당하는 Leaf 노드에 데이터를 삽입한다.
Leaf 노드 데이터가 가득 차 있으면 노드를 분리한다. [ if(노드 데이터 개수 == M(차수)) ]
-> insert7 에서 노드가 1, 5, 7로 가득 찼다.
-> 정렬된 노드를 기준으로 중간 값을 부모 노드로 해서 트리를 구성한다.
분리한 서브트리가 B-Tree 조건에 맞지 않는다면 부모 노드로 올라가며 merge한다.
-> insert12에서 [9, 7, 12]를 서브트리로 분리했지만 B-Tree 조건에 맞지 않는다.
-> Leaf 노드가 모두 같은 레벨에 존재하지 않는다.
-> Root 노드와 merge로 조건을 만족시켰다.

삭제

삭제는 크게 Leaf 노드인 경우와 Leaf 노드가 아닌 경우로 나누어진다.

예시1 (Leaf 노드)

Leaf 노드에서 1을 삭제하면 B-Tree 구조가 깨진다.
삭제한 노드의 부모 노드로 올라가며 데이터를 가져온다.
1의 부모 노드와 형제 노드를 merge 한다. 부모 노드에서 자식 노드로 값을 가져오고, 자식 노드의 형제 노드와 merge한다.
root 노드까지 올라가며 B-Tree 조건에 맞을 때까지 이 작업을 반복한다.

예시2 (Leaf 노드 아님)

먼저, 노드에서 데이터를 삭제하고 왼쪽 서브트리에서 최대 값을 노드에 위치시킨다.
같은 방식으로 부모 노드에서 자식 노드로 값을 가져오고, 형제노드와 merge하며 B-Tree 조건이 맞을 때까지 반복한다.

예시3

RB Tree (Red-Black Tree)

---

정의

RB 트리는 다음 다섯가지 속성을 만족하는 이진탐색트리의 일종이다.

1) 모든 노드는 빨간색, 검은색 둘 중 하나다.
2) 루트 노드는 검은색이다.
3) 모든 잎새노드(NIL)는 검은색이다.
4) 어떤 노드가 빨간색이라면 두 개 자식 노드는 모두 검은색이다. (따라서 빨간색 노드가 같은 경로 상에 연이어 등장하지 않는다)
5) '각 노드~자손 잎새 노드 사이의 모든 경로'에 대해 검은색 노드의 수가 같다.

노드의 높이 h는 해당 노드로부터 잎새노드에 이르는 가장 긴 경로의 엣지 수를 가리킨다.
임의의 노드 x의 Black-height는 x부터 잎새 노드에 이르는 경로 상에 있는 검은색 노드의 수로 bh(x)라고 표기한다.
x가 검은색 노드일 경우 1을 빼주며 잎새노드(NIL)의 bh는 0이다. h와 bh를 계산하는 예시는 다음과 같다.

삽입

RB 트리의 삽입 연산은 이진탐색트리의 삽입과 동일하다. 하지만 삽입 후에도 RB 트리의 다섯 가지 속성을 유지하고 있어야 하기 때문에 몇 가지 작업을 수행해준다. (이진탐색트리의 연산을 기본으로 하되 이후 추가 작업을 수행해준다는 점에서 AVL 트리와 유사하다)

삽입할 새 요소 z는 빨간색으로 둔다. z와 검정색 부모 노드를 공유하는 형제노드(sibling node)를 y라고 두겠다.

case 1

(case 1-1) y가 빨간색이면서 z가 left child인 경우이다. 아래 그림에서 z가 삽입되면서 빨간색 노드가 연이어 등장하게 됐다. RB 트리의 네 번째 속성에 위배된다. 이 경우 노드의 색을 바꿔서 다시 칠해준다.

(case 1-2) y가 빨간색이면서 z가 right child인 경우에도 색을 바꿔서 다시 칠해준다.

case2, case3

(case2) y가 검은색이면서 z가 right child인 경우에도 빨간색 노드가 연이어 등장해 RB 트리의 네 번째 속성에 위배된다.
case2인 경우 double rotation을 수행해준다.

(case3) y가 검은색이면서 z가 left child인 경우에도 single rotation을 수행해준다.

delete

RB 트리에서 검정색 노드를 삭제할 때는 삭제 연산으로 RB 트리의 속성이 깨지지 않도록 해야 한다.
이는 삽입 연산 때 고려했던 것과 유사한 방식으로 rotation을 구현함으로써 해결할 수 있다.
다만 빨간색 노드를 삭제할 때는 그냥 삭제를 수행하면 된다.

계산복잡성

RB 트리 전체 높이를 h라고 할 때 삽입, 삭제, 검색 등 RB 트리의 계산복잡성은 O(h)이다.
RB 트리의 노드 수가 n개라면 높이 상한은 2logn + 1 이다.
따라서 RB 트리의 계산복잡성은 O(logn)이다

정리

시나리오별 rotation 수행은 다음과 같이 한다. 삽입된 노드가 꺾여 있는 형태면 rotation을 한 번 수행해 이것을 펴주고, 펴진 형태의 노드에 대해 rotation을 한 번 더 수행한다. 이미 펴져있는 형태로 노드가 삽입된 경우라면 rotation을 한 번만 수행한다.

힙 (Heap)

---

정의

A가 B의 부모 노드(parent node)이면, A의 키(key)값과 B의 키값 사이에는 대소 관계가 성립한다.
힙에는 두 가지 종류가 있으며 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙을 '최대 힙', 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙을 '최소 힙' 이라고 부른다.
키 값의 대소 관계는 오로지 부모-자식 노드 간에만 성립하며, 형제 사이에는 대소 관계가 정해지지 않는다.
각 노드의 자식 노드 최대 개수는 힙의 종류에 따라 다르지만, 대부분의 경우는 자식 노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용한다.
힙에서는 가장 높은(혹은 낮은) 우선순위를 가지는 노드가 항상 뿌리 노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

우선순위 큐 (Priority Queue)

---

정의

컴퓨터 과학에서 우선순위 큐는 큐나 스택과 비슷한 축약 자료형이고, 각 원소들이 우선순위를 갖고 있다.
우선순위 큐에서 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다.
만약 두 원소가 같은 우선순위를 가진다면 그들은 큐에서 그들의 순서에 의해 처리된다.
우선순위 큐가 힙이라는 것은 널리 알려진 오류이다. 우선순위 큐는 "list"나 "map"과 같은 추상적인 개녕미다.
마치 list는 연결 리스트나 배열로 구현될 수 있는 것과 같이, 우선순위 큐는 힙이나 다른 방법을 이용해 구현될 수 있다.
우선순위 큐는 최소한 다음의 연산이 지원되어야 한다.

1) insert_with_priority : 하나의 원소를 우선순위를 지정해 큐에 추가한다.
2) pull_highest_priority_element : 가장 높은 우선순위를 가진 원소를 큐에서 제거하고 이를 반환한다.

해시 테이블 (Hash Table)

---

정의

Key값에 Value를 저장하는 구조로 key 값을 통해 데이터에 접근한다.
그렇기에 데이터 접근 시간 복잡도가 O(1)이 되어 탐색이 빠르다는 장점을 갖는다.

문제

이 때 해시 테이블의 문제가 발생할 수 있는데 충돌에 관한 문제이다.
만약 다수의 Value 중 Key값이 겹치는 Value들이 존재하면 충돌이 발생한다.
이를 해결할 수 있는 방법은 다양하다.

해결

첫째로 Chaining 방식은 Linked List를 이용하는 방법으로 저장하려는 해시 테이블에 같은 키 값의 데이터가 존재할 경우,
노드를 추가해 다음 노드를 가리키는 방식으로 체인을 이어서 해시 테이블을 구성하는 방식이다.

둘째로 Open addressing 방식은 index에 대한 충돌 처리에 대해서 Linked List와 같이 추가적인 메모리 공간을 사용하지 않고, 해시 테이블의 배열 중 빈 공간을 사용한다.
이를 구현하는 방법은 다양한데 간단한 Linear Probing을 보겠다.

Linear Probing 방식은 index에 대해 충돌이 발생했을 경우 index의 바로 뒤 버킷 중에서 빈 버킷을 찾아 데이터를 삽입한다.
그러므로 후에 key에 맞는 index를 접근했을때 키 값이 옳지 않으면 뒤로 한 칸씩 검색을 하면서 일치하는 키 값을 찾아낸다. (상황이 좋지 않으면 효율이 매우 떨어질 수 있다)

맵 (map)

---

정의

map의 자료 구조는 "트리(tree)"이다. (RB Tree)
map은 많은 자료를 정렬해 저장하고 있고, 빠른 검색을 필요로 할 때 자주 사용한다.
map은 자료를 중복해서 저장할 수 없다.
map과 hash_map의 다른 점은 map은 자료를 자동으로 정렬하고, hash_map은 자동으로 정렬하지 않는다는 점이다.

map은 아래 조건일 때 사용하면 좋다.

1) 정렬해야 한다.
2) 많은 자료를 저장하고, 검색이 빨라야 한다.
3) 빈번하게 삽입, 삭제하지 않는다.

사용 방법

map< key 자료 타입, value 자료 타입> 변수 이름 -> map<int, int> map1
value는 저장할 자료이고, key는 value를 가리키는 역할이다.

정렬의 대상은 key이고, 기본은 오름차순이다. 정렬 기준을 바꾸고 싶으면 다음과 같이 비교 함수를 추가한다.
map< key 자료 타입, value 자료 타입, 비교 함수> 변수 이름

주요 멤버

멤버	설명
begin	첫 번째 원소의 랜덤 접근 반복자를 반환
clear	저장하고 있는 모든 원소를 삭제
empty	저장 하고 있는 요소가 없으면 true 반환
End	마지막 원소 다음의(미 사용 영역) 반복자를 반환
erase	특정 위치의 원소나 지정 범위의 원소들을 삭제
Find	key와 연관된 원소의 반복자 반환
insert	원소 추가
lower_bound	지정한 key의 요소를 가지고 있다면 해당 위치의 반복자를 반환
operator[]	지정한 key 값으로 원소 추가 및 접근
rbegin	역방향으로 첫 번째 원소의 반복자를 반환
rend	역방향으로 마지막 원소 다음의 반복자를 반환
size	원소의 개수를 반환
upper_bound	지정한 key 요소를 가지고 있다면 해당 위치 다음 위치의 반복자 반환

세트 (set)

---

정의

set은 원하는 key를 신속하게 찾고, 이 key가 정렬되기를 원할 때 사용한다. (key : 저장할 자료)
map과 비슷하지만 다른 점은 map은 key와 값이 한 쌍으로 저장되지만, set는 key만 저장한다.
map과 똑같이 set도 key를 중복으로 저장할 수 없다. key를 중복으로 사용하고 싶다면 multiset을 사용해야 한다.
set은 map과 똑같이 이진 탐색 트리 자료구조를 사용한다

set는 아래 조건일 때 사용하면 좋다.

1) 정렬해야 한다.
2) key가 있는지 없는지 알아야 한다.
3) 많은 자료를 저장하고, 검색 속도가 빨라야 한다.

사용 방법

set< key 자료 타입> 변수 이름 -> set set1;
set< key 자료 타입, 비교 함수> 변수 이름

주요 멤버

멤버	설명
begin	첫 번째 원소의 랜덤 접근 반복자를 반환
clear	저장하고 있는 모든 원소를 삭제
empty	저장 하고 있는 요소가 없으면 true 반환
end	마지막 원소 다음의(미 사용 영역) 반복자를 반환
erase	특정 위치의 원소나 지정 범위의 원소들을 삭제
find	key와 연관된 원소의 반복자 반환
insert	원소 추가
lower_bound	지정한 key의 요소를 가지고 있다면 해당 위치의 반복자를 반환
operator[]	지정한 key 값으로 원소 추가 및 접근
rbegin	역방향으로 첫 번째 원소의 반복자를 반환
rend	역방향으로 마지막 원소 다음의 반복자를 반환
size	원소의 개수를 반환
upper_bound	지정한 key 요소를 가지고 있다면 해당 위치 다음 위치의 반복자 반환