Array vs Linked List
Array
- 논리적 저장 순서와 물리적 저장 순서가 일치
- 인덱스로 해당 원소에 접근할 수 있다.
- random access가 가능하다
- 추가/삭제시, shift 연산이 필요
Linked List
- Array의 문제점을 해결하기 위한 자료구조
- 삽입/삭제 과정에서의 shitf 연산이 필요없다
- 탐색 과정에서 첫번째 원소부터 확인해야된다 = 탐색시간이 오래걸린다.
- 탐색 과정 때문에 삽입/삭제 과정에서 O(n)의 시간이 추가 발생하게 된다.
stack
- Last In First Out : LIFO
Queue
- First In First Out : FIFO
Tree
- 비선형자료구조
- 계층적 구조
Node (노드) : 트리를 구성하고 있는 각각의 요소를 의미한다.
Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다.
Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드를 의미한다.
Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다.
Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.
Binary Tree :이진트리
두 개의 서브 트리 모두 이진트리여야한다.
level : 각 층별 숫자 [ root level : 0 ]
height : 최고 레벨
parent : i/2 [ root index : 1 ]
left_child : i*1 [ root index : 1 ]Perfect Binary Tree : 포화 이진 트리
Complete Binary Tree : 완전 이진 트리
Full Binary Tree : 정 이진 트리
Binary Search Tree : BST
- 효율적인 탐색을 위한 저장 방법
- 탐색 연산 : O(log n) => 최악의 경우[편향이진트리 ], O(n)
규칙
1. 이진 탐색 트리의 노드에 저장된 키는 유일하다
2. 부모의 키가 왼쪽 자식 노드의 키보다 크다
3. 부모의 키가 오른쪽 자식노드의 키보다 작다
4. 왼쪽 오른쪽 서브트리도 이진 탐색 트리이다.
Rebalencing 기법
- O(n)의 탐색기간이 걸리는 경우를 해결
- 균형을 잡기 위해 트리 구조의 재조정을 하는 기법
- ex. Red-Black Tree
Binary Heap
- 자료구조의 일종, Tree 의 형식
- Complete Binary Tree
- Max Heap / Min Heap
Red Black Tree
- BST를 기반으로 하는 트리형식의 자료구조
- 탐색, 입력, 삭제 => O(log n)
- BST의 삽입,삭제 연산과정에서 발생할 수 잇는 문제점을 해결하기 위해 만드렁진 자료구조
정의
1. 각 노드의 red or black이라는 색깔을 가진다
2. root node의 색깔은 Black이다
3. 각 leaf node는 black이다
4. 어떤 노드의 색깔이 red라면 두 개의 children의 색깔은 모두 blackc이다
5. 각 노드에 대해서 노드로부터 descendant leaves까지의 단순 경로는 모두 같은 수의 black node들을 포함하고 있다. 이를 해당 노드의 black-height라고 한다.특징
1. Binary Search Tree이므로 BST의 특징을 모두 갖는다
2. Root nodeㅂ터 leaf node까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다. : balanced 상태
3. 노드의 child가 없을 경우, child를 가리키는 포인터는 NULL값을 저장한다. 이러한 NULL들은 leaf node로 간주된다.삽입
1.BST의 특성을 유지하면서 노드를 삽입
2. 삽입된 노드를 red로 지정 : black-height를 최소화하기 위해서
3. RBT의 특성 위배시, 노드의 색깔을 조정한다
4. Black-Height가 위배되었을 경우, rotation을 통해 height 조정한다삭제
1. BST의 특성을 유지하면서 노드를 삭제
2. 삭제될 노도의 child의 개수에 따라 rotation방법이 다라진다.
2-1. 지워진 노드의 색깔이 black이라면 black-height가 1 감소한 경로에 black node가 1개 추가될도록 rotation하고 색깔을 조정한다.
2-2. 지워진 노드의 색깔일 red라면 violation이 발생하지 않으므로 RBT가 그대로 유지한다.
Hash Function
- Hash Function의 결과값 : hashcode
- collision : 서로 다른 두개의 키가 같은 인덱스로 hashing되면 같은 곳에 저장할 수 없게 된다.
- 무조건 1:1로 만드는 것보다는 collision을 최소화하는 방향으로 설계 & collision 발생시, 대응 방법을 선택하는 것이 중요
- 1:1로 만드는 경우는 거의 불가능하고 만들어도 array와 다를바가 없어 메모리가 너무 커진다.
- Collision이 많아질 수록 O(1) -> O(n)으로 변경
- hash function이 매우 중요함.
Resolve Conflict
- Open Address : 개방 주소법
- 충돌이 발생하면, 다른 해시버킷에 해당 자료에 삽입하는 방식
- Separate Chaining : 분리연결법
2-1. 연결리스트를 사용하는 방식
2-2. tree[RBT]를 사용하는 방식해시버킷 동적확장
일정 개수 이상이 되면[임계점 : 75%], 해시버킷의 개수를 2배 늘린다.
Graph
- 정점과 간선의 집합
- Undirected Graph / Directed Graph
- Degree : 각 정점에 연결되 edge의 개수
- Weight Graph : 가중치 있음
- Sub Graph : 본래의 그래프이 일부 정점 및 간선으로 이루어진 그래프
구현방식
인접행렬 : 정방행렬 사용
인접리스트 : 연결리스트 사용
그래프 탐색
DFS 깊이 우선탐색 O(V+E)
BFS 너비 우선탐색 O(V+E)
MST Minimum Spanning Tree
Kruskal O(E log E)
Prim O(E log V)
