[자료구조] Tree, Graph

 

 

목차

 

 

 

 

📌  자료구조

 

자료구조란 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것

데이터란? 문자, 숫자, 그림, 영상 등 실생활을 구설하고 있는 모든 값

데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있다.

 

 

📍Tree

 

(거꾸로 뒤집어 놓은)나무의 형태

단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태

컴퓨터의 디렉토리 구조가 가장 큰 예이다.

 

 

 

🔗 Tree의 특징

 

아래 그림과 같이 하나 이상의 데이터에 한 개의 경로와 하나의 방향으로만 연결된 계층적 자료구조

하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다.

🤷‍♂️싸이클(cycle)이란? 시작 노드에서 출발해 다른 노드를 거쳐 시작 노드로 돌아올 수 있다면 사이클이 존재한다라고 한다.

트리는 사이클이 없는 하나의 연결 그래프이다.

 

 

루트(Root)라는 하나의 꼭짓점 데이터 👉🏻 여러 개의 테이터를 간선으로 연결

각 데이터를 노드(Node)라고 하며, 두개의 노드가 상하 계층으로 연결되며 부모/자식 관계를 가진다.

EX) 위 그림에서 보면 D의 부모는 B이며, C의 자식은 F와 G이다.

 

 

• 깊이 (depth) : 루트로부터 하위 계층의 특정 노드까지의 깊이(루트노드의 깊이는 0이다.)
• 레벨(Level) : 같은 깊이를 가지고 있는 노드를 묶어서 레벨이라고 표현(같은 레벨의 노드는 형제 노드) 
• 높이(Height) : 리프 노드를 기준으로 루트까지의 높이를 표현(루트노드의 높이는 0이다.)
• 서브 트리(Sub tree) : 트리 구조를 갖춘 작은 트리를 서브 트리

 

🔗 Tree 수도코드

 

class Tree {
  //tree의 constructor를 구현합니다.
  //tree의 자식 노드들을 children으로 할당하여 노드의 자식 노드들을 담을 수 있게 설정합니다.
  constructor(value) {
    this.value = value;
    this.children = [];
  }
  //tree의 자식 노드를 생성 한 후에, 노드의 children에 push해 줍니다.
  insertNode(value) {
    const childNode = new Tree(value);
    this.children.push(childNode);
  }
  // tree에서 value값을 탐색합니다.
  // 현재 노드의 value 값이 찾는 값과 일치한다면 return합니다.
  contains(value) {
    if (this.value === value) {
      return true;
    }
    // 노드가 가진 자식 노드를 순회하는 반복문으로 노드의 children 배열을 탐색합니다.
    for (let i = 0; i < this.children.length; i += 1) {
      const childNode = this.children[i];
      if (childNode.contains(value)) {
        return true;
      }
    }
    return false;
  }
}

 

 

🔗 이진 트리(Binary Tree)

 

자식 노드가 최대 두개인 노드로 구성된 트리

자식 노드는 왼쪽 노드와 오른쪽 자식 노드로 나눈다.

자료의 삽입, 삭제 방법에 따라 정 이진 트리, 포화 이진 트리, 완전 이진 트리로 나눈다.

 

 

 

 

🔗 이진 트리 특징

 

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

 

 

이진 탐색 트리(Binary Search Tree)

 

🤷‍♂️이진 탐색이란? 정렬된 데이터 중에서 특정한 값을 찾기 위한 탐색 알고리즘 중 하나이다.

오름차순으로 정렬된 정수의 배열을 같은 크기의 두 부분 배열로 나눈 후, 두 부분 중 탐색이 필요한 부분만

탐색하도록 탐색 범위를 제한하여 원하는 값을 찾는다.

 

이진 탐색 트리 속성

 

이진 탐색 트리는 중위 순회 방식을 쓴다.

중간의 값을 지정해 오름차순으로 중간값과 크기를 비교하여 탐색한다.

중간값도 작으면 배열의 맨 앞부터 중간 값 전까지를 탐색하고 중간값보다 크다면 다음 값부터 맨 마지막까지 탐색한다.

값을 찾을 때 까지 반복, 값을 찾지 못하면 그대로 연산을 종료한다.

 

https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/

 

• 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
• 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다.
• 중복된 노드가 없어야 한다.
• 왼쪽 서브트리, 오른쪽 서브트리 또한 이진탐색트리이다.

 

즉, 이진 탐색 트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값은 루트나 부모보다 큰 값을 가지는 특징을 가지고 있다.

 

 

 

🔗 트리 순회

 

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 한다.

트리를 순회하는데는 전위, 중위, 후위 순회 세가지 방법이 있다.

 

• 전위 순회 : 가장 먼저 방문하는 노드는 루트, 루트에서 시작해 왼쪽 노드를 둘러본 뒤, 오른쪽 노드 탐색(복사 때 사용)
• 중위 순회 : 루트를 가운데 두고 순회, 왼쪽 끝 노드를 거쳐 오른쪽 끝 노드까지 이동하여 탐색(오름차순 값을 가져올 때)
• 후위 순회 : 루트를 마지막에 순회, 왼쪽 노드 끝 부터 오른쪽 노드 끝으로 이동해 순회한 뒤 마지막 루트 방문(삭제 때 사용)
• 레벨 순회 : 트리의 레벨을 기준으로 노드를 방문하는 순회 방법 동일 레벨의 여러 노드가 존재하는 경우 오른쪽 순서로 방문

🤷‍♂️순회 방식을 나누는 이유 : 트리구조 전체를 탐색할 때 조금 더 효율적으로 노드를 찾기 위해

 

 

 

📍Graph

 

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

마치 거미줄처럼 여러 개의 점이 선으로 이어져 있는 복잡한 네트워크망 같은 모습

 

 

Graph의 구조

 

• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.
• 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다.
• 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge)이라고 한다.

 

 

🔗 Graph의 표현 방식

 

인접행렬

 

두 정점을 이어주는 간선이 있다면 이 두 정점은 인접하다.

서로 다른 정점들이 인접한 상태인지 표시한 행렬로 2차원 배열의 형태로 나타난다.

예를 들어 max[i][j] 가 true라면 i -> j로의 간선이 있다는 뜻이다

 

if(간선 (i, j)가 그래프에 존재)
  max[i][j] = 1;
else
  max[i][j] = 0;

 

Quiz) 인접행렬로 표현해보기

 

 

A)

 

 

해결방안)

 

테이블의 0번째 row부터 순서대로 A, B, C, E라고 했을 때,

A(0)는 C와 E를 향하고 있으므로 테이블의 첫 번째 row는 0, 0, 1, 1

B(1)는 A를 향하고 있으므로 테이블의 두 번째 row는 1, 0, 0, 0

C(2)는 B를 향하고 있으므로 테이블의 세 번째 row는 0, 1, 0, 0

E(3)는 B를 향하고 있으므로 테이블의 네 번째 row는 0, 1, 0, 0

 

 

🔗 인접 행렬 수도 코드

 

// directed graph (방향 그래프)
// unweighted (비가중치)
// adjacency matrix (인접 행렬)
// 이해를 돕기 위해 기존 배열의 인덱스를 정점으로 사용합니다 (0, 1, 2, ... --> 정점)
class GraphWithAdjacencyMatrix {
  //graph의 constructor를 구현합니다.
  constructor() {
    this.matrix = [];
  }
  //vertex를 추가합니다.
  addVertex() {
    const currentLength = this.matrix.length;
    for (let i = 0; i < currentLength; i++) {
      this.matrix[i].push(0);
    }
    this.matrix.push(new Array(currentLength + 1).fill(0));
  }
  //vertex를 탐색합니다.
  //this.matrix에 vertex가 존재한다면 true를 리턴하고, 반대의 경우라면 false를 리턴합니다.
  contains(vertex) {
    return !!this.matrix[vertex];
  }
  //vertex와 vertex를 이어주는 edge를 추가합니다.
  addEdge(from, to) {
    const currentLength = this.matrix.length - 1;
    // 두 가지 인자 중, 어느 하나라도 undefined라면, 리턴합니다.
    if (from === undefined || to === undefined) {
      console.log("2개의 인자가 있어야 합니다.");
      return;
    }
    // from vertex와 to vertex가 전체 그래프의 범위를 벗어난다면, 리턴합니다.
    if (
      from > currentLength ||
      to > currentLength ||
      from < 0 ||
      to < 0
    ) {
      console.log("범위가 매트릭스 밖에 있습니다.");
      return;
    }
    // this.matrix[from][to]의 값을 1로 바꿔줘서 edge로 연결이 되어 있음을 표시합니다.
    this.matrix[from][to] = 1;
  }
  // from vertex와 to vertex 사이에 edge를 가지고 있는지 여부를 판단합니다.
  hasEdge(from, to) {
    return !!this.matrix[from][to];
  }
  // from vertex와 to vertex 사이에 관련이 없다면, edge를 제거 합니다.
  removeEdge(from, to) {
    const currentLength = this.matrix.length - 1;
    // 두 가지 인자 중, 어느 하나라도 undefined라면, 리턴합니다.
    if (from === undefined || to === undefined) {
      console.log("2개의 인자가 있어야 합니다.");
      return;
    }
    // from vertex와 to vertex가 전체 그래프의 범위를 벗어난다면, 리턴합니다.
    if (
      from > currentLength ||
      to > currentLength ||
      from < 0 ||
      to < 0
    ) {
      console.log("범위가 매트릭스 밖에 있습니다.");
      return;
    }
    // this.matrix[from][to]의 값을 0으로 바꿔줘서 관련이 없음을 표시합니다.
    this.matrix[from][to] = 0;
  }
}

 

 

인접리스트

 

그래프로 표현하는 가장 일반적인 방법이다.

모든 정점을 인접 리스트에 저장한다. 각 정점이 어떤 정접과 인접하는지를 리스트의 형태로 표현

가 정점마다 하나의 리스트르 가지고 잇고, 이 리스트는 자신과 인접한 다른 정점을 갖고 있다.

리스트의 순서는 중요하지 않다.

 

 

Quiz) 인접리스트로 표현해보기

 

A)

 

해결방안)

 

0번 노드는 1, 2, 3과 모두 이어져 있으므로 [0, *] -> [1, *] -> [2, *] -> [3, null]

1번 노드는 0과 2에 이어져 있으므로 [1, *] -> [0, *] -> [2, null]

2번 노드는 0과 1과 3에 이어져 있으므로 [2, *] -> [0, *] -> [1, *] -> [3, null]

3번 노드는 0과 2에 이어져 있으므로 [3, *] -> [0, *] -> [2, null]

 

 

🔗 인접 행렬과 인접 리스트의 사용

 

인접 리스트 : 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프의 경우

 

1. 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용한다.
    - 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지한다.

 

인접 행렬 : 그래프에 간선이 많이 존재하는 밀집 그래프의 경우

 

1. 한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이하다.
    - 예를 들어, A에서 B로 진출하는 간선이 있는지 파악하기 위해선 0번째 줄의 1번째 열에 어떤 값이 저장되어있는지 바로 확인할 수 있습니다.
2. 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용된다.
    - 최단 경로를 구하는 과정(BFS)에서는 그래프 탐색이 빈번하게 발생하는데, 이때 인접행렬이 인접리스트에 비해 조회 성능이 우수합니다. 
인접행렬의 경우 인덱스를 직접 접근하여 조회가 O(1)로 이루어지기 때문이다. 
반면, 인접리스트의 경우 각 row를 선형 조회해야 하므로 노드의 수가 N일 경우 O(N)의 시간이 소요된다.
정리하자면, 인접리스트의 경우 A 노드에서 B 노드로 이동하는 경우만 해도 O(N)의 시간이 소요되며, 더불어 최단 경로를 구하는 과정 자체에서도 시간이 많이 소요되기 때문에 
인덱스를 통한 직접 접근이 가능한 인접행렬이 최단경로를 찾는 데 더 유리한 측면이 있다는 것이다.

 

 

📍 BFS와 DFS

그래프의 탐색은 하나의 정점에서 시작해 모든 정점을 한 번씩 방문하는 것이 목적

BFS와 DFS방법 또한 모든 정점 탐색 방법 중 하나이다.

 

 

🔗Breathed First Search

 

너비를 먼저 탐색하는 방법, 즉 너비 우선 탐색

최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

인접한 노드를 먼저 탐색 , 최단 경로를 찾고 싶을 때 사용한다.

 

출처 https://developer-mac.tistory.com/64

만약 한국에서 미국 가는 방법을 탐색한다며 최단 경로를 찾을 때 BFS 방식을 사용합니다.

💁‍♂️ 왜 사용할까? BFS는 현재 있는 노드에서 가까운 곳부터 탐색

 

 

🔗 DFS(Depth First Search)

 

깊이를 먼저 탐색하는 방법, 깊이 우선 탐색

최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동

 

 

출처 https://developer-mac.tistory.com/64

 

 

EX) 비행기 티켓이 없다면 어떤 비행기가 미국으로 가는지는 알수 없다. 이 때 비행기를 타고 여러 나라를 방문하면서,

마지막 미국에 도착하는 경로를 찾을 때, 하나의 경로를 끝까지 탐색한 후, 미국 도착이 아니라면 다음 경로로 넘어가 탐색해야 한다.

이 때 BFS보다는 오래 걸리지라도 모든 노드를 완전히 탐색할 수 있다. 

 

 

🔗 BFS와 DFS 비교

 

 

DFS(깊이우선탐색)	BFS(너비우선탐색)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐를 이용해서 구현