Graph Tree BST

Graph

무방향 그래프

그래프는 노드(Node, 정점 -vertex-)와 노드와 노드를 연결하는 간선(edge)로 구성된다.

간선은 방향가질수도, 무방향(undirected)일 수 있다.

 

진입 차수 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)

진출 차수(out-degree): 방향 그래프에서 외부로 향하는 간선의 수 (외차수 라고도 부름)

방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)

 

인접 행렬 방식

abcd는 노드, 1은 간선을 의미한다

NxN 불린 행렬(Boolean Matrix)로써 matrix[i][j]가 true라면 
i -> j로의 간선이 있다는 뜻이다.

V개의 노드를 표현하기 위해 V*V 만큼의 크기가 필요하므로
공간복잡도는 O(V^2)

 

인접 리스트 방식

각 노드에서 간선이 어떤 노드와 연결되어있는지 연결리스트로 표현한다

모든 정점(혹은 노드)을 인접 리스트에 저장한다. 
즉, 각각의 정점에 인접한 정점들을 리스트로 표시한 것이다.

무방향 그래프(Undirected Graph)에서 (a, b) 간선은 두 번 저장된다.

트리에선 특정 노드(루트 노드)에서 모든 노드로 접근 가능 => Tree 클래스 불필요
그래프에선 특정 노드에서 모든 노드에 접근 불가능 => Graph 클래스 필요

V개의 리스트(노드)에 간선 개수만큼의 원소가 들어있으므로
공간복잡도는 O(V+E)

일상생활 예시) 지도, 지하철 노선도 최단경로, 전기회로 소자들, 도로 등

Tree

노드로 구성된 계층적 자료구조.

최상위 노드(루트)를 만들고, 루트 노드의 child를 추가하고,
그 child에 또 child를 추가하는 방식으로 트리 구조를 구현할 수 있다.

간선(edge) : 노드와 노드를 연결하는 선

잎(leaf) : 자식이 없는 (말단)노드   
*최하단 노드라는 의미가 아님

깊이(depth) : 루트를 기준으로 특정 노드까지의 거리(간선의 개수) ex)  (위그림에서) 0, 1, 2, 3

높이(height) : 루트를 기준으로 최하단 계층의 leaf 노드까지의 거리 ex) (위그림에서) 3

레벨(level) : 깊이가 같은 노드끼리의 집합

 

그래프 구현 방식 중 인접 행렬 방식과 인접 리스트 방식의 차이는 무엇인가?


트리와 그래프의 차이점은 무엇인가?

트리는 방향 그래프, 그래프는 방향, 무방향 모두 가능.

트리는 사이클 불가능(비순환 그래프),

그래프는 사이클, 자체간선(self-loop)가능, 순환그래프, 비순환그래프 모두 존재.

트리는 루트노드 존재, 그래프는 루트노드가 없다.

트리는 계층모델, 그래프는 네트워크 모델.

트리는 노드가 n개일 때 항상 n-1의 간선을 가짐.

그래프는 그래프에 따라 간선의 수가 다름. (없을수도 있다)


일상생활 예시) 이진트리, 이진탐색 트리, 균형 트리, 이진힙 등

 

 

BST

Binary Search Tree

이진 탐색 트리는 최대 2개의 자식만을 갖는다.

트리구조는 재귀적이므로, 각 자식 노드 역시 2개의 자식만을 갖는다.

노드의 값보다 작으면 왼쪽 자식으로,
노드의 값보다 크면 오른쪽 자식으로 삽인된다.

깊이 우선 탐색은 무엇인가?

루트노드에서 시작해서 현재 노드의 첫번째 자식부터, 그리고 그 자식의 자식부터 
우선적으로 탐색하는 방법. 
탐색이 끝나면 백트래킹으로 탐색하지 않은 노드를 찾는다.


이진 탐색 트리의 탐색 방법 3가지

전위 순회(Preorder Traversal): 부모 → 좌 → 우
중위 순회(Inorder Traversal): 좌 → 부모 → 우
후위 순회(Postorder Traversal): 좌 → 우 → 부모


이진 탐색 트리의 종류

전 이진 트리(Full Binary Tree)

모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리.

 

완전 이진 트리(Complete Binary Tree)

트리의 마지막 레벨을 제외한 모든 레벨의 노드가 꽉 차 있는 이진 트리.
마지막 레벨의 노드는 반드시 왼쪽부터 채워져야 한다. 
왼쪽은 있고 오른쪽은 없어도 된다.

포화 이진 트리(Perfect Binary Tree)

전 이진 트리면서 완전 이진 트리인 경우.

모든 노드가 두 개의 자식 노드를 갖는다.
모든 말단 노드는 같은 높이에 있어야 하며, 마지막 단계에서 노드의 개수가 최대가 되어야 한다.

이진 탐색 트리(BST)에서 왼쪽과 오른쪽 자식의 총 깊이가 
1 초과 만큼 차이가 난다면 비틀어 재 정렬 한다. 
그래야 find 할 때 O(n) 이하의 가질 수 있다. 

재정렬하며 구조를 갖추면 find 할 때 O(log n)의 시간 복잡도를 갖는다.

정렬된 배열에서도 같은 시간복잡도를 갖는다.
그럼에도 정렬된 배열 대신 트리를 사용하는 이유는 

배열은 메모리에서 연속된 공간을 차지하는 반면,
트리는 링크드 리스트로 구현했을 때 비연속적인 메모리 공간을 차지하기 때문에
메모리 효율 부분에서 더 효율적이기 때문이다.

 

참고링크 :

gmlwjd9405.github.io/2018/08/13/data-structure-graph.html
gmlwjd9405.github.io/2018/08/12/data-structure-tree.html