Tree
(level1) 이진트리
모든 노드가 두개 이하의 자식노드를 가질 때, Binary Tree라고 부른다.
(level2) 이진탐색트리
이진트리인데, 자료의 검색, 삭제, 삽입, 정렬 등에 효율적인 트리 자료구조임. 부모노드의 키값의 대소에 따라 자식노드를 삽입함. —
(level3) 포화이진트리
모든 레벨이 꽉 찬 이진 트리
(level3) 완전이진트리
위에서 아래, 왼쪽에서 오른쪽으로 순서대로 노드가 차곡차곡 쌓인 트리
(level3) 균형이진트리
이진탐색트리로 삽입할 때, 계속 부모노드보다 작은 수가 나온다면, 높이가 한없이 늘어남. 그러면 탐색할 때 최악의 경우, 시간복잡도가 O(N). 그래서 삽입/삭제할 때마다 재정렬(rotation)을 통해 높이의 불균형을 없애주는 균형이진트리가 등장함. —
(level4) 이진 힙
- 이진 힙은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조. 그래서 루트가 최대/최소 값을 가지고 있도록 고안함.
- 우선순위 큐 : 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조.
- 이진탐색트리는 key중복이 안되는데 이진 힙은 중복된 key가 허용된다.
우선순위 큐와 이진 힙은 같지 않다. 우선순위 큐는 힙 외에도 배열이나 연결 리스트로도 구현 가능하다.
- 시간복잡도
최악 : 삽입 -> O(log2N) 추출 -> O(1) - 우선순위 큐를 구현하는 방법들(배열/이진힙)
(level4) AVL트리
AVL트리는 트리의 전체 레벨을 비슷하게 맞추기 위해 다음의 재정렬 알고리즘을 사용함.
4가지(LL, RR, LR, RL) 불균형이 발생할 수 있으며 각 상황마다 rotation에 방향을 달리하여 트리의 균형을 맞춤. 삽입한 곳에서 거꾸로 올라가면서 정렬함.
- LL : right 회전
- (부모 노드 기준) 왼쪽 높이 - 오른쪽 높이 > 1
- (왼쪽 자식 노드 기준) 왼쪽 높이 > 오른쪽 높이
- RR : left 회전
- (부모 노드 기준) 오른쪽 높이 - 왼쪽 높이 > 1
- (오른쪽 자식 노드 기준) 오른쪽 높이 > 왼쪽 높이
- LR : left -> right 회전
- (부모 노드 기준) 왼쪽 높이 - 오른쪽 높이 > 1
- (왼쪽 자식 노드 기준) 오른쪽 높이 > 왼쪽 높이
- RL : right -> left 회전
- (부모 노드 기준) 오른쪽 높이 - 왼쪽 높이 > 1
- (오른쪽 자식 노드 기준) 왼쪽 높이 > 오른쪽 높이
- 시간복잡도 최악/최선 모두 O(log2N) 정렬에 추가시간이 소모됨.
(level4) 레드-블랙트리
RBT트리는 트리의 전체 레벨을 비슷하게 맞추기 위해 다음의 재정렬 알고리즘을 사용함.
- 루트는 항상 black
- 어떤 노드의 색깔이 red라면 두 개의 children 의 색깔은 모두 black 이다
- 각 노드에 대해서 노드로부터 descendant leaves 까지의 단순 경로는 모두 같은 수의 black nodes 들을 포함하고 있다. 이를 해당 노드의 Black-Height라고 한다.
- 시간복잡도 최악/최선 모두 O(log2N). 단지 AVL보다 더 balancing되어 있지는 않음. 정렬에 추가시간이 소모됨. 하지만 AVL보다는 조금 더 빠름. 색깔만 바꾸면 되기때문에.
(Other) B 트리
하나의 노드에 여러 엔트리(값)들을 갖을 수 있음 노드 내부 엔트리들은 항상 정렬된 상태를 유지 —
AVL vs RBT
- 서칭 속도 : AVL 이 더 빠름. 더 balance 있는 균형트리이기 때문.
- 삽입/삭제 속도 : RBT가 더 빠름. 로테이션이 AVL에 비해 덜 일어나기 때문.
AVL tree 같은 경우 삽입할때 무조건 페런트 노드를 차례대로 하나씩 비교하여 리밸런싱 하는 과정이 포함되기 때문에 평균, 최악의 경우 둘다 O(log n)의 시간복잡도를 지니지만 RB Tree의 경우 color가 추가 되었기 때문에 무조건 트리를 회전하는 것이 아니라 색깔만 바꾸는 등의 방법으로 좀 더 느슨하게 리밸런싱 하므로 트리 회전 횟수가 감소된다.
GST(Generalized Search Tree)
- 보통 이진트리는 자식이 두개 이하임. 하지만 얘는 자식이 여러개 있는 트리. Postgres가 이방식으로 데이터 관리함.
정렬
최악이 O(N^2) 정렬
- 선택 정렬
1~n비교, 1에 가장 작은 수 삽입 2~n비교, 2에 … n-1~n비교, n-1에 … 최악 : O(n^2) -> 역순으로 정렬되어 있을 때
- 삽입 정렬
2~1비교정렬 3~1비교정렬 n~1비교정렬 최악 : O(n^2) -> 역순으로 정렬되어 있을 때
- 버블 정렬( 정렬이 되어있는 상태면 O(1) )
1과2비교정렬, 2와3비교정렬, … n-1와 n비교정렬. 1과2비교정렬, 2와3비교정렬, … n-2와 n비교정렬. … 최악 : O(n^2) -> 역순으로 정렬되어 있을 때 54321 -> 45321 -> 43521 -> 43251 -> 43215(5고정됨) 43215 -> 34215 -> 32415 -> 32145 (4고정됨) …
최악이 O(NlogN) 정렬
- 병합 정렬
참조 지역성이 잘 반영됨. 반 씩 나눠서 더 분리 안될때까지 다 분리함. 하나씩 정렬하기 시작함.(순서를 유지한 채로)
- 힙 정렬
배열을 하나씩 꺼내면서 힙 트리에 삽입 및 정렬. 이후에 정렬된 힙 트리에서 루트노드 하나씩 꺼내면서 리스트에 삽입.
- 퀵 정렬
- 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
- 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
- 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다. 최악 : O(n^2) -> 역순으로 정렬되어 있을 때(피벗의 왼/오른쪽에 전체 값들이 몰리도록 하도록 피벗을 설정할 시)
순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
시간복잡도
Hash Table
해시 테이블은 Key를 해싱해서 해당 버켓에 Value를 삽입함. 그래서 값을 찾을 때 바로 찾을 수 있음.
- 해시(Hash)값이 충돌하는 경우
- 체인 방법 같은 버켓에 들어가게 되면, linked list로 체이닝함. Java8은 이렇게 Hash테이블이 이렇게 이루어져있음
- 개방 주소법 추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법
Java의 HashMap(해시맵)과 HashTable(해시테이블) 차이
HashTable은 동기화 지원. HashMap은 동기화 지원 X.
그래프
Minimum Spanning Tree
그래프 G 의 spanning tree 중 edge weight 의 합이 최소인 spanning tree를 말한다. 여기서 말하는 spanning tree란 그래프 G 의 모든 vertex 가 cycle 이 없이 연결된 형태를 말한다. 구현은 여러 알고리즘으로 할 수 있음(Kruskal, Prim)
- Kruskal MST Algorithm
- 초기화 작업으로 edge 없이 vortex 들만으로 그래프를 구성한다. 그리고 weight 가 제일 작은 edge 부터 검토한다.
- 가장 작은 weight 에 해당하는 edge 를 추가하는데 추가할 때 그래프에 cycle 이 생기지 않는 경우에만 추가
- 모든 vertex 들이 연결된 상태로 종료
시간 복잡도 : O(ElogE) E=엣지개수
- Prim MST Algorithm
- 시작 정점을 MST 집합에 포함
- MST 집합에 인접한 정점들 중에서 가장 작은 weight로 연결된 정점을 선택하여 트리를 확장
- 2.를 트리가 (N-1)개의 간선을 가질 때까지 반복한다.
시간 복잡도 : O(E log V) E=엣지개수, V=정점개수