Graph, Tree, BST(Binary Search Tree)

Taeseon Kim·2021년 4월 25일

아유 어제 했던 것 처럼 하면 되겠지~ 하고 덤볐던 오늘의 스프린트,
자료 구조다.

컴퓨터 과학에서 자료구조는 데이터의 효율적인 접근을 위해서 조직되는 자료 구조라고 한다.(위키피디아, 데이터 구조)

컴퓨터에서 효율이란 메모리를 최소한으로 사용하며 최소의 시간을 사용하는 것을 말하는 것이라고 생각하는데, 관련한 문제를 풀면 풀수록 효율적인 것이 맞나 싶다.

Graph, Tree, BST

이름부터 웅장하다. 오늘 나는 이 웅장한 친구들에게 두드려 맞았다.
개념은 어렵지 않으나 활용면에서 어려우니 정리하면서 다시금 다져보려한다.
내가 이해한 이 세 자료구조형의 특징은 크게 3가지의 요소로 나눌 수 있다.

정점(Vertex)

간선(Edge)

인접 리스트(Adjacency List)

이 3가지의 요소를 통해 차이점과 특징에 대해 알아보려 한다.

1. Graph

우리가 흔히 접하던 x, y축의 꼬불꼬불한 그래프?
아니다. 여기에서 그래프는 다르다.

자바스크립트 Graph 자료 구조형은 여러 점들이 서로 복잡하게 연결되어 있는 구조이다. 따라서 뒤에서 다룰 Tree와 다르게 계층이 존재하지 않고, 사이클이 존재할 수 있다.

1. 정점

위 그림에는 파란 점들과 노란 점들이 있다. 저 점들 하나 하나를 Graph에서는 정점 이라고 한다.
인접 리스트에서는 {정점 : [인접한 정점, 인접한 정점]}의 형태로 나타낼 수 있다.
그래프에서는 인덱스에 정점을 할당하여 나타낸다.

2. 간선

위 그림에는 점과 점을 잇는 회색 선들이 있는데, 이를 간선이라고 한다.
간선은 방향을 가지고 있으며 일방적일 수도, 쌍방적일 수도 있다.
인접 리스트에서는 {0 : [1, 2]} 의 형태에서 0에서 1과 2로 접근할 수 있음을 나타낸다.
그래프에서는 각 2차원 배열의 값이 간선을 나타낸다.

3. 인접 리스트

인접 리스트는 각 정점의 간선이 어느 정점으로 향하는지 표현하는 객체이며, 모든 정점의 연결 상태에 접근할 수 있다.

*4. 그래프

그래프는 배열의 값으로 간선에 접근하고, index로 정점에 접근하는 2차원 배열이다. 모든 정점의 간선 연결 상태에 접근할 수 있다.

*Graph 예시

let adj = {
	0:[1,3],
  	1:[2,3],
	2:[0,1,3],
	3:[1]
	}
let matrix = [
	[0, 1, 0, 0],
	[0, 0, 1, 0],
	[0, 0, 0, 1],
	[0, 1, 0, 0],
	] //이 그래프와 인접리스트는 0, 1, 2, 3으로 정점이 총 4개이며,
//0 => 1, 1 => 2, 2 => 3, 3 => 1의 간선으로 이루어져 있다.

2. Tree

트리는 그래프와 유사하지만 데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결되는 계층적 자료구조이다. 그래프와 차이점은 계층이 존재한다는 점이며 간선이 아래로만 뻗기 때문에(일방적) 사이클이 없다.

1. 정점(노드)

위 그림에는 동그라미들이 있다. 저 점들 하나 하나를 Tree에서는 정점(노드) 이라고 한다.
인접 리스트에서는 {value: 정점, children : [{value: 인접한 정점, children : []}, {value: 인접한 정점, children: []}]}의 형태로 나타낼 수 있다.

2. 간선(루트)

위 그림에는 점과 점을 잇는 회색 선들이 있는데, 이를 간선(루트)이라고 한다.
간선은 방향을 가지고 있으며 일방적이다.
인접 리스트에서는 {value: 0, children : [{value: 1, children : []}, {value: 2, children: []}]} 의 형태에서 0에서 1과 2로 접근할 수 있음을 나타낸다.

3. 인접 리스트

인접 리스트는 각 정점(노드)의 간선(루트)이 어느 정점으로 향하는지 표현하는 객체이며, 모든 정점(노드)의 연결 상태에 접근할 수 있다.

Tree 예시

let tree = {value: 0, children:[
  {value: 1, children: [
    {value: 3, chlidren: []}],
  {value: 2, children: []}
  };
 //이 인접리스트는 0이라는 노드의 자식 노드로 1,2가 있으며, 1의 자식 노드로 3이 있다.

3. BST

BST는 트리의 구조를 이용한 자료구조로, 이진 탐색 트리 구조라고한다.

다른 것보다 예시로 구현을 해보자면,

class BST{
  constructor(value){ //value라는 값을 받은 이진 트리는
    this.value = value; //값을 value로 갖고,
    this.left = null; //앞으로 넣어줄 값들이 value보다 작다면 left로,
    this.right = null;//크다면 right로 넣어줄 것이다.
  }
  insert(something){//something이라는 인자를 갖는 insert메서드가 실행될 때,
    if(something < this.value){//something이 현재 값보다 작다면, left값과 비교를 하는데,
      if(this.left === null){//만약 left가 비어있다면,
        this.left = new BST(something);//left에 something을 value로 하는 새로운 이진트리를 생성한다.
      } else {//만약 이미 값이 존재한다면,
        this.left.insert(something);//그 값과 비교하는 insert메서드를 재귀적으로 실행한다.
      }
    } else if(something > this.value) {//something값이 현재 값보다 크다면, right와 비교를 하는데,
      if(this.right === null){//right가 비어있다면,
        this.right = new BST(something);//right에 something을 값으로 갖는 새로운 이진트리를 생성한다.
      } else { //만약 이미 값이 존재한다면,
        this.right.insert(something);//그 값과 비교하는 insert메서드를 재귀적으로 실행한다.
      }
    } //만약 현재 트리 내에 something값이 이미 존재한다면, 아무것도 실행되지 않는다.
  }
}