Graph, Tree

Graph

그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다.
출처

ADT

1. insertVertex : 정점을 추가한다.
2. insertEdge : 간선을 추가한다.
3. deleteVertex : 정점을 삭제한다. (연결된 간선도 함께)
4. deleteEdge : 간선을 삭제한다.
5. adjacent : 특정 노드에 인접한 모든 정점 반환

그래프는 다음과 같은 다양한 종류가 존재한다.
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

트리의 정의를 보기전에 간단한 용어 정리를 하자면

• Root node : 부모가 없는 노드, 단 하나만 존재한다.
• Leaf node : 자식이 없는 노드

  Tree는 Graph의 한 종류로써 다음과 같은 조건을 만족하는 그래프이다.

  1. 하나의 루트 노드를 갖는다.
  2. 루트 노드는 0개 이상의 자식노드를 갖는다.
  3. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.

특징

1. Tree안에 Tree(Subtree)가 있는 재귀적인 구조이다.
2. Loop를 가지지 않는다.
3. 모든 자식노드는 하나의 부모노드를 가진다.
4. 노드의 개수가 n이라면, 간선의 개수는 n-1개이다.
5. 루트노드에서 한 노드까지 가는 경로는 1개이다.

종류

• 편향트리 - 모든 노드들이 하나의 자식만 가지고 있는 트리
• 이진 트리 - 각 노드가 자식의 수가 2개 이하인 트리
• 균형 트리 - 추후 설명 예정
• 완전 이진 트리 - 마지막 레벨을 제외한 노드가 채워져있고, 마지막 레벨은 왼쪽에서 부터 차있는 트리
• 포화 이진 트리 - Leaf노드를 제외한 모든 노드들이 자식노드를 2개 갖는 노드

트리의 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 로 표현가능하다.

포화이진트리
완전 이진트리처럼 배열로 표현가능하다.
그 이유는 포화이진트리에서 마지막 레벨에 오른쪽에서 하나씩 빼면 그것이 완전이진트리이때문이다.

BST(binary Search Tree)

트리의 정의에서 다음과 같은 조건을 가진다.
1. 모든 원소는 다른 키를 갖는다. (같은 키를 가진 BST도 존재)
2. 왼쪽 서브트리에 있는 모든 키는 관찰 노드보다 작다.
3. 오른쪽 서브트리에 있는 모든 키는 관찰 노드보다 크다.
4. 서브트리가 재귀적으로 정의된다.

특징

• 전위순회시에 정련된 키를 조회가능
• 트리가 균형상태이면 O(logN) 비균형상태이면 O(N)의 시간복잡도로 특정 요소를 찾을 수 있다.

Red Black Tree

Red Black Tree는 자가 균형 이진 트리로써 다음과 같은 조건을 가진다.
1. 모든 노드는 black , red 중 하나의 상태를 가진다.
2. 루트노드는 반드시 black이다.
3. 모든 리프노드는 black이다.
4. red 노드의 자식은 black이다.
5. 리프노드에서 루트 노드까지 가는 경로에서 만나는 black 노드의 개수가 같다.

Red Black Tree가 균형을 맞추는 방법

1. 새로 추가하는 노드는 red이다. -> 4번 조건을 어길 수 있다.

만약 4번 조건을 어긴다면 (Double Red)
2가지 전략을 사용해 밸런스를 맞춘다.

설명에 필요한 변수 설명
N : 추가한 노드
P : N의 부모노드
G : P의 부모노드
U : N의 삼촌 노드

Restructuring

U 가 없거나 red일 경우 채택하는 방법

U : 부모의 형제 노드

N P G 를 정렬한 후 가운데 값을 black으로 변경후 이진트리에 정의에 맞게 배치하고 가운데 값의 자식들을 red로 변경한다.

이때 리프노드가 red처럼 될 수도 있는데, 실제로 Leaf노드는 nil을 자식 노드로 가지고 있고, 이는 balck이다.

Recoloring

U가 red일때 채택하는 방법

N P U를 black으로 바꾸고, G를 red로 변경한다.
G가 루트 노드라면 black으로 변경한다.
G를 red로 변경했을 때, 다시 double red가 발생한다면 Recoloring, Restructuring을 진행한다.

특징

1. Recoloring, Restructuring을 통해 균형트리가 보장된다.
   노드의 갯수를 N이라 하고 가장 긴 depth를 LD 가장 짧은 depth를 SD라고 했을 때,
   SD는 <= log N 이다. SD가 가장 긴 경우는 이진트리가 포화이진트리인 경우이기 때문이다.
   LD <= 2 x SD 이다. black depth는 같기 때문에 SD가 모두 검은색이라 해도, LD는 검은색 노드 사이 사이에 red가 껴져있는 상태이므로 2배를 넘을 수 없다.
   즉, SD <= LD <= 2 log N이므로 어떠한 방향으로 내려가서 찾아도 log N안에 검색이 가능하다.
2. 삭제, 삽입의 연산이 O(log n)의 시간복잡도를 가진다.
   최악의 경우는 루트노드까지 double red가 발생한다. 한번의 Recoloring과 Restructuring이 상수시간을 가지므로 로그 복잡도를 가진다.