그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다.
출처
그래프는 다음과 같은 다양한 종류가 존재한다.
1. 무방향 그래프 - 간선에 방향이 없는 그래프
2. 방향 그래프 - 모든 간선에 방향이 있는 그래프
3. 완전 그래프 - 한 정점에 모든 정점으로 가는 간선이 있는 즉 간선의 수가 최대인 그래픈
4. 가중 그래프 - 간선에 가중치가 있는 그래픔
5. 연결 그래프 - 한 정점에 다른 정점까지 갈수 있는 정점 즉 떨어져 있는 정점이 없는 그래프
이러한 그래프를 구현하는 방법도 2가지 존재한다.
그래프의 연결관계를 이차원배열을 통해 나타내는 방법
출처
- 장점 : 두 노드의 인접관계를 찾기 위해 O(1)
- 단점 : 공간 복잡도 O(V ^ 2)
- 단점 : 특정 노드와 연결된 노드들을 찾기위해 O(n) (n은 정점의 수)
동적배열을 사용해 차수만큼 정점의 배열을 할당하여 표현하는 방법
출처
- 장점 : 공간복잡도 O(V + E)
- 장점 : 특정 노드와 연결된 노드들을 찾기위해 O(1)
- 단점 : 두 노드의 인접관계를 찾기 위해 O(n) (n은 간선의 수)
Dense Graph vs Sparse Graph
Dense Graph : 간선의 수가 최대간선의 수에 가까운 그래프 출처
Sparse Graph : 간선이 얼마 없는 그래프 출처Dense Graph는 간선이 많기 때문에 인접행렬로 구현하는 것이 유리하다.
간선이 최대에 가깝기 때문에 공간복잡도가 비슷하고, 특정 노드에 연결된 노드들을 순회할 시 비슷한 시간복잡도를 같는다. 이때 두 노드의 인접관계를 구하는 시간복잡도는 상수시간 vs 선형시간이기 때문에 유리하다.반대의 이유로 Sparse Graph는 간선이 적기 때문에 인접리스트가 유리하다.
트리의 정의를 보기전에 간단한 용어 정리를 하자면
Tree는 Graph의 한 종류로써 다음과 같은 조건을 만족하는 그래프이다.
- 하나의 루트 노드를 갖는다.
- 루트 노드는 0개 이상의 자식노드를 갖는다.
- 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.
트리의 height vs depth
height : leaf node는 height이 0이며, 관찰 노드의 자식중 height이 가장 높은 수 + 1
depth : 관찰 노드를 제외한 조상 노드의 개수
선형 자료구조 vs 비선형 자료구조
선형 자료구조 : 자료간의 앞뒤관계가 1 : 1 인 구조
ex ) 스택, 큐, 배열 ...
비선형 자료구조 : 자료간의 앞뒤관계가 1 : N 인 구조
ex ) 그래프, 트리
완전 이진트리의 구현
완전 이진트리는 노드는 배열로 구현이 가능하다.
루트 노드를 인덱스 1이라고 가상으로 부여한다.
자식 노드 = 부모 노드 x 2 + 1 or 부모노드 x 2 로 표현가능하다.
포화이진트리
완전 이진트리처럼 배열로 표현가능하다.
그 이유는 포화이진트리에서 마지막 레벨에 오른쪽에서 하나씩 빼면 그것이 완전이진트리이때문이다.
트리의 정의에서 다음과 같은 조건을 가진다.
1. 모든 원소는 다른 키를 갖는다. (같은 키를 가진 BST도 존재)
2. 왼쪽 서브트리에 있는 모든 키는 관찰 노드보다 작다.
3. 오른쪽 서브트리에 있는 모든 키는 관찰 노드보다 크다.
4. 서브트리가 재귀적으로 정의된다.
특징
Red Black Tree는 자가 균형 이진 트리로써 다음과 같은 조건을 가진다.
1. 모든 노드는 black , red 중 하나의 상태를 가진다.
2. 루트노드는 반드시 black이다.
3. 모든 리프노드는 black이다.
4. red 노드의 자식은 black이다.
5. 리프노드에서 루트 노드까지 가는 경로에서 만나는 black 노드의 개수가 같다.
만약 4번 조건을 어긴다면 (Double Red)
2가지 전략을 사용해 밸런스를 맞춘다.
설명에 필요한 변수 설명
N : 추가한 노드
P : N의 부모노드
G : P의 부모노드
U : N의 삼촌 노드Restructuring
U 가 없거나 red일 경우 채택하는 방법
U : 부모의 형제 노드
N P G 를 정렬한 후 가운데 값을 black으로 변경후 이진트리에 정의에 맞게 배치하고 가운데 값의 자식들을 red로 변경한다.
이때 리프노드가 red처럼 될 수도 있는데, 실제로 Leaf노드는 nil을 자식 노드로 가지고 있고, 이는 balck이다.
U가 red일때 채택하는 방법
N P U를 black으로 바꾸고, G를 red로 변경한다.
G가 루트 노드라면 black으로 변경한다.
G를 red로 변경했을 때, 다시 double red가 발생한다면 Recoloring, Restructuring을 진행한다.