[자료구조] Graph / Tree / BST

Graph

노드(Node)와 그 노드를 연결하는 간선(Edge)을 하나로 모아놓은 자료구조

비가중치 그래프

let isConnected = {
  seoul: {
    busan: true,
    daejeon: true
  },
  daejeon: {
    seoul: true,
    busan: true
  },
  busan: {
    seoul: true,
    daejeon: true
  }
}

console.log(isConnected.seoul.daejeon) // true
console.log(isConnected.daejeon.busan) // true

알아둬야 할 그래프 용어들

• 무향그래프(undirected graph)
  양방향으로 모두 갈 수 있는 그래프
• 단방향 그래프(directed graph)
  한 방향으로만 갈 수 있는 그래프
• 진입차수(in-degree) / 진출차수(out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.
• 인접(adjacency)
  두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점.
• 자기 루프(self loop)
  정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현. 다른 정점을 거치지 않는다는 것이 특징.
• 사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아 가는 것.

그래프의 표현 방식: 인접 행렬 & 인접 리스트

인접 행렬

인접 행렬은 정점들간의 인접함을 표시해 주는 행렬으로 2차원 배열의 모습을 가지고 있다.
만약 A라는 정점과 B라는 정점이 이어져 있다면 1, 이어져 있지 않다면 0으로 표시하는 일종의 표와 같은 모습이다

• A의 진출차수는 1개 입니다: A —> C
  [0][2] === 1
• B의 진출차수는 2개 입니다: B —> A, B —> C
  [1][0] === 1
  [1][2] === 1
• C의 진출차수는 1개입니다: C —> A
  [2][0] === 1

인접 리스트

인접 리스트는 각 정점이 어떤 정점과 인접한지 리스트의 형태로 볼 수 있는 표현 방식.
각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트에는 자신과 인접한 다른 정점들이 담겨 있다.

❓ B는 A와 C로 이어지는 간선이 두개가 있는데, 왜 A가 C보다 먼저죠? 이 순서는 중요한가요?
: 간선의 순서는 중요하지 않다.

우선 순위를 다뤄야 한다면 더 적합한 자료구조(ex. queue, heap)를 사용하는 것이 합리적이다

Tree

그래프의 여러 구조 중 일방향 그래프의 한 구조. 하나의 뿌리로부터 가지가 사방으로 뻗은 형태. 노드로 이루어진 자료구조
트리는 계층 모델 이다.

• 트리는 하나의 루트(Root) 노드를 갖음
• 루트 노드는 0개 이상의 자식 노드(Child Node)를 갖음
• 그 자식 노드 또한 0개 이상의 자식 노드를 갖고, 이는 반복적으로 정의.
• 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(leaf Node)라 함.
• 높이와 깊이를 잴 수 있다.

BST(Binary Search Tree)

이진 트리(binary tree) : 자식 노드가 최대 두 개인 노드들로 구성된 트리를 이진 트리라고 정의함.
이진 탐색 트리(binary search tree) : 모든 왼쪽 자식들은 루트나 부모보다 작은 값이고, 모든 오른쪽 자식들은 루트나 부모보다 큰 값인 특징을 가지고 있는 이진 트리를 이진 탐색 트리라고 정의

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