기본 자료구조 간단 정리

실제 동작 구현 : https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Data Structure Visualization

1. 선형 리스트

stack

한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO)

 

queue

먼저 집어 넣은 자료가 먼저 나오는 선형 구조(FIFO)

 

double-end queue(deque)

삽입/삭제가 양 끝에서 허용되는 선형 구조

scroll : 입력이 한쪽만 가능함

shelf : 출력이 한쪽 끝으로만 가능함

 

 

priority queue

우선 순위에 따라서 순서대로 처리하는 선형 구조

주로 heap으로 구현된다.

만약 우선 순위가 높은 데이터를 삭제할 경우(1삭제) 마지막 노드를 root 노드 자리로 옮긴 뒤 자식과 비교해서 정렬함

삽입할 경우, 가장 마지막 위치(leaf)에 추가하고 정렬

 

2. 연결 리스트

linked list

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조

 

doubly linked list

포인터가 2개가 있고 각각의 포인터는 앞, 뒤 노드를 가리킨다.

 

 

circular linked list

마지막 노드의 포인터는 처음 노드에 연결된다.

 

3. 트리

tree

서로 다른 두 노드를 잇는 길이 하나 뿐인 그래프(이진 트리)

 

avl tree

균형잡힌 이진 트리(balanced tree)

각각의 노드마다 좌우 sub-tree에 높이 차이에 대한 정보를 가지고 sub-tree의 높이 차이가 1보다 크지 않은 성질을 가짐

시간복잡도는 O(n)이지만 삽입/삭제할 때 원하는 노드를 찾기 위해서는 2개의 경로가 필요하기 때문에 자주 사용되지 않음

 

red-black tree

https://zeddios.tistory.com/237

 참고

 

조건

• Root property : root node는 black
• External property : external node는 black
• Internal property : red node의 자식은 black(no double red)
• Depth property : 모든 leaf node에서 black depth는 같다.(root->leaf node 가는 경로에 만나는 black node의 수는 같다)
• 삽입 node는 무조건 Red

 

Double Red 해결 전략

z : 자기 자신(삽입된 node)

v : 부모 node

w : 형제 node

• Restructuring(w가 black일때)

나(z)와 내 부모(v), 내 부모의 부모(Grand Parent)를 오름차순으로 정렬

무조건 가운데 있는 값을 부모로 만들고 나머지 둘을 자식으로 만든다.

올라간 가운데 있는 값을 검정(Black)으로 만들고 그 두자식들을 빨강(Red)로 만든다. 

 

• Recoloring(w가 red일때)

현재 inset된 노드(z)의 부모와 그 형제(w)를 검정(Black)으로 하고 Grand Parent(내 부모의 부모)를 빨강(Red)로 한다.

Grand Parent(내 부모의 부모)가 Root node가 아니었을 시 Double Red가 다시 발생 할 수 있다.

   

(끝나지 않고 Root까지 반복해야할 수 있음)

Propagation(번식) : Recoloring의 경우 부모의 부모를 Red로 바꾸다보면 Root까지 갈 수 있다. 위의 예제처럼 4의 부모가 Red라면 다시 Recoloring, Restructuring을 실행한다.

 

b-tree

이진 트리를 학장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조

https://www.cs.usfca.edu/~galles/visualization/BTree.html

 

heap

최대, 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조

부모 node가 자식보다 크면 최대 heap, 반대는 최소 heap

node마다 대소관계는 부모자식 간에만 성립되며 형제 사이에는 대소관계가 없음.

heap property : A가 B의 부모 노드이면, A와 B 사이에 대소관계가 성립한다.

 

huffman code

주어진 문자열을 트리를 이용해 2진수로 압축하는 알고리즘. heap을 사용한다.(무손실 압축에 쓰인다)

문자들의 발생 빈도수에 따라 가변 길이 코드를 생성, 고정 길이로 사용할 때보다 데이터 양이 줄어든다는 섀넌-파노 원리를 이용함.

 

알고리즘

• 초기화 : 모든 기호를 출현 빈도수에 따라 나열
• 축소
1. 발생 확률이 가장 낮은 두 개의 심볼을 결합
2. 결합된 노드와 나머지 낮은 심볼과 결합
3. 두 개의 심볼이 남을때까지 반복
•  
• 확장
1. 최종 두 개의 심볼에 0, 1을 할당
2. 축소 과정의 반대 방향으로 확장하면서 0, 1을 할당
3. 소스 심볼의 개수까지 반복

 

 

4. 그래프

DFS

깊이 우선 탐색. 대표적 알고리즘은 백트리킹

 

BFS

너비 우선 탐색

 

spanning tree

그래프에서 루프 발생을 방지하기 위해 사용된 알고리즘(그래프 내의 모든 정점을 포함하는 tree)

 

5. 검색

hashing

하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것