Tree & Graph

Tree

• 나무형태를 가지고 있는 단방향 그래프의 한 구조, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태
• 하나 이상의 데이터에 한 개의 경로와 하나의 방향으로만 연결된 계층적 자료 구조
• 하나의 데이터 아래에 여러개의 데이터가 존재하는 비선형 구조
• 시작 노드에서 출발해 다른 노드를 거쳐 시작 노드로 돌아올 수 있는 사이클이 존재하며 사이클이 없는 하나의 연결그래프

tree 계층적 자료구조

 

 

Tree 구조와 특징

• 트리구조는 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결함.
• 각 데이터를 노드(Node)라고 하며 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 맺음 (e.g. D는 Parent Node, H는 Child Node)
• 자식이 없는 노드는 리프 노드(Leaf Node) (e.g. J) 

➡️ 자료구조 Tree는 깊이, 높이, 레벨 등을 측정할 수 있음

서브트리 (Sub tree) : 루트에서 뻗어 나오는 큰 트리 내부에 트리구조를 갖춘 작은 트리 (e.g. D,H,I / B,D,E / C,F,G,J)

 

노드(Node) : 트리구조를 이루는 모든 개별 데이터

루트(Root) : 트리 구조의 시작점이 되는 노드

부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드

자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드

리프(Leaf) : 트리 구조의 끝 지점, 자식 노드가 없는 노드

 

 

이진트리 (Binary tree)

➡️ 자식 노드가 최대 두 개인 노드로 구성된 트리, 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있음

(자료의 삽입 / 삭제 방법에 따라 정 이진트리 / 완전 이진트리 / 포화 이진트리로 나뉨)

 

 

• 정 이진트리(Full binary tree) : 각 노드가 0개 혹은 2개의 자식 노드를 가짐
• 포화 이진트리(Perfect binary tree) : 정 이진트리이면서 완전 이진트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리
• 완전 이진트리(Complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 함

 

이진 탐색 트리 (Binary Search Tree)

➡️ 정렬된 데이터 중에서 특정한 값을 찾기 위한 탐색 알고리즘 중 하나이며 오름차순으로 정렬된 정수의 배열을 같은 크기의 두 부분 배열로 나눈 후 두 부분 중 탐색이 필요한 부분에서만 탐색하도록 범위를 제한하여 원하는 값을 찾음

(트리 안에 찾고자 하는 값이 없어도 트리의 높이만큼 연산 및 탐색 진행)

 

이진 탐색 트리

 

1.  루트 노드의 키와 찾고자 하는 값을 비교. 찾고자하는 값이면 탐색 종료

2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색

3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색

(e.g. 5를 찾고자 할 때, 루트 노드인 10보다 작으므로 왼쪽 서브트리로 탐색하여 7 → 5 찾고자 하는 값이므로 탐색 종료)

 

 

트리 순회

➡️ 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문 (전위 순회, 중위 순회, 후위 순회)

 

• 전위 순회 (preorder traverse) : 가장 먼저 방문하는 노드 루트. 루트에서 시작해 왼쪽의 노드들을 순차적으로 본 뒤 왼쪽 노드 탐색이 끝나면 오른쪽 노드 탐색. 부모 노드 제일 먼저 방문 (주로 트리를 복사할 때 사용)
  (e.g. 10 → 7 → 5 → 3 → 6 → 9 → 12 → 11 → 15 → 14)
• 중위 순회 (inorder traverse) : 루트를 가운데 두고 순회. 제일 왼쪽 끝에 있는 노드부터 순회 시작해서 루트 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 탐색. 부모 노드가 중간에 방문 (이진 탐색 트리의 오름차순으로 값을 가져올 때 사용)
  (e.g. 3 → 5 → 6 → 7 → 9 → 10 → 11 → 12 → 14 → 15)
• 후위 순회 (postorder traverse) : 루트를 가장 마지막에 순회. 제일 왼쪽 끝에 있는 노드부터 순회 시작해서 오른쪽으로 이동해 순회하고 제일 마지막에 루트 방문. 자식 노드가 먼저 삭제 되어야 상위 노드 삭제 (트리를 삭제할 때 사용)
  (e.g. 3 → 6 → 5→ 9 → 7 → 11 → 14 → 15 → 12 → 10)

레벨 순회 (levelorder traverse) : 레벨 기준 노드 방문 순회방법. 루트 노드의 레벨이 1이라고 했을 때 아래로 내려갈 수록 레벨은 증가

---

Graph 

➡️ 여러 개의 점이 서로 복잡하게 연결된 관계를 표현한 자료 구조

 

 

• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있음
• 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어짐
• 하나의 점을 그래프에서는 정점이라고 표현, 하나의 선은 간선이라고 함

 

 

Graph의 표현 방식

인접행렬 

➡️ 두 정점을 바로 이어주는 간선이 있으면 인접하다고 함. 2차원 배열 형태로 나타내며 A와 B가 이어져 있으면 1(true), 이어져 있지 않다면 0(false). 가중치 그래프라면 1대신 관계에서 의미있는 값을 저장

 

A의 진출차수 1개 : A → C

[0][2] === 1 // A([0])는 C([2])로 가는 진출차수가 있다(1)

B의 진출차수 2개 : B → A, B → C

[1][0] === 1 // B([1])는 A([0])로 가는 진출차수가 있다(1)
[1][2] === 1 // B([1])는 C([2])로 가는 진출차수가 있다(1)

 

C의 진출차수 : C → A

[2][0] === 1 // C([2])는 A([0])로 가는 진출차수가 있다(1)

 

 

인접 리스트

➡️ 각 정점이 어떤 정점과 인접하는지 리스트 형태로 표현. 정점마다 리스트를 가지고 있으며 리스트는 자신과 인점한 다른 정점을 담고 있음

(순서는 중요하지 않음)

 

 

 

 

Graph 용어

• 정점 (vertex) : 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
• 간선 (edge) : 정점을 이어주는 선
• 인접 정점 (adjacent vertex) : 하나의 정점에서 간선에 의해 직접 연결된 정점
• 가중치 그래프 (weighted Graph) : 연결의 강도(추가적인 정보, ex. 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀 있는 그래프
• 비 가중치 그래프 (unweighted Graph) : 연결의 강도가 적혀 있지 않는 그래프
• 무향(무방향) 그래프 (undirected graph) : 단방향 그래프. 두 지점이 일방통행 도로로 이어져있다면 단방향 간선으로 표현
• 진입차수 (in-degree) / 진출차수 (out-degree) : 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냄
• 인접 (adjacency) : 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점
• 자기 루프 (self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 '자기 루프를 가졌다'라고 표현. 다른 정점을 거치지 않는다는 것이 특징
• 사이클 (cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 '사이클이 있다'고 표현. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울로 이동이 가능하므로, 사이클이 존재하는 그래프

---

BFS (Breadth-First Search)

➡️ 최단경로를 찾으려면 가장 가까운 정점부터 탐색후 탐색할 정점이 없을 때 그 다음 떨어져 있는 정점을 순서대로 방문. 너비를 먼저 탐색하는 방법이며 너비 우선 탐색이라고 함. 

 

DFS (Depth-First Search)

➡️ 하나의 경로를 끝까지 탐색 후 도착지가 아니면 다음 경로로 넘어가 탐색. 깊이 우선 탐색이라하며 한 정점에서 시작해서 다음 경로로로 넘어가기 전 해당 경로를 완벽하게 탐색. BFS보다 탐색시간은 오래걸리지만 완전히 탐색할 수 있음