Data Structure TIL 04

2021년 7월 22일에 작성된 문서 2번 입니다.
자료 구조 배운 내용을 정리했습니다.

Graph

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

• 하나의 점 : 정점(vertex)
• 하나의 선 : 간선(edge)

그래프의 실사용 예제

내비게이션 시스템

서울에 사는 A는 부산에 사는 B와 오랜 친구 사이입니다. 이번 주말에 부산에서 열리는 B의 결혼식에 참석하기 위해 A는 차를 몰고 부산으로 가려고 합니다. 대전에 살고 있는 친구 C도 B의 결혼식에 참석을 한다고 하여, A는 서울에서 출발하여 대전에서 C를 태워 부산으로 이동을 하려고 합니다.

• 정점: 서울, 대전, 부산
• 간선: 서울—대전, 대전—부산, 부산—서울

비가중치 그래프

• 추가 정보를 파악할 수 없는 그래프, 가중치(연결의 강도가 얼마나 되는지)가 적혀 있지 않은 그래프

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

//비가중치 그래프로 나타낸 서울, 대전, 부산 그래프

• 비가중치 그래프 : 각 정점간의 연결 유무만을 판단.
• 가중치 그래프 : 더 자세한 정보를 담는다.
  * 간선에 연결정도(거리 등)를 표현한 그래프 => 가중치 그래프

• 정점: 서울, 대전, 부산
• 간선: 서울—140km—대전, 대전—200km—부산, 부산—325km—서울

알아둬야 할 그래프 용어

• 무(방)향그래프(undirected graph): 앞의 내비게이션 예제는 무(방)향 그래프다. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는것도 가능하다.
• 진입차수(in-degree) / 진출차수(out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타낸다.
• 인접(adjacency): 두 정점간에 간선이 직접 이어져 있는 경우.
• 자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우. 다른 정점을 거치지 않는다.
• 사이클(cycle): 한 정점에서 출발해 다시 그 정점으로 돌아갈 수 있는 경우

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

인접 행렬

인접 행렬 : 서로 다른 정점들이 인접한 상태인지를 표시한 행렬 (2차원 배열의 형태)

• 인접 행렬을 사용하는 경우 :
  두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이.
  가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용.
  
  

인접 리스트

인접 리스트 : 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현한다.

• 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.
• 인접 리스트를 사용하는 경우 :
  메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용.
  인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지한다.

Tree

데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조

그래프의 여러 구조 중 무방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부릅니다.

• 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조다.
• 트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클이 없다.
• 트리구조는 깊이와 높이, 레벨 등을 측정할 수 있다.

용어정리

• 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
• 루트(Root) : 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• 리프(Leaf) : 트리 구조의 끝지점이고, 자식 노드가 없는 노드

깊이 (depth)

• 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)
• 루트 노드는 지면에 있는 것처럼 깊이가 0.

레벨(Level)

• 같은 깊이를 가지고 있는 노드
• 형제 노드(sibling Node): 같은 레벨에 나란히 있는 노드

높이(Height)

• 리프 노드를 기준으로 루트까지의 높이(height)
• 리프 노드와 직간접적으로 연결된 노드의 높이를 표현
• 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가진다.
• 트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 놓는다.

서브 트리(Sub tree)

• 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리

  
  
  

트리의 실사용 예제

컴퓨터의 디렉토리 구조

어떤 프로그램이나 파일을 찾을 때, 바탕화면 폴더나 다운로드 폴더 등에서 다른 폴더에 진입하고, 또 그 안에서 다른 폴더에 진입하면서 원하는 프로그램이나 파일을 찾습니다. 모든 폴더는 하나의 폴더(루트 폴더, /)에서 시작되어, 가지를 뻗어나가는 모양새를 띕니다.

Binary Search Tree

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

이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉩니다.

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

Written with StackEdit.