Graph, Tree, Binary Search Tree

elenaJEL

Published in

els_products

8 min readMar 29, 2020

Data Structure in JavaScript 자바스크립트 자료구조

Stack, Queue, Linked List, Hash Table에 이어서 오늘은 Graph, Tree, Binary Search Tree 자료구조에 대해서 알아보도록 하겠다.

🕸Graph

Graph는 서로 연결된 노드들의 집합 (Collection)이다. 웹 페이지들이 서로 어떻게 연결되어 있는지, social networks, navigation systems 등 다양한 분야에서 가장 활용성이 뛰어난 자료구조이다.

구성을 살펴보면,

vertex(복수형: vertices): 각 노드를 vertex라고 부르고
edge(s): 노드들은 edge로 연결되어 있다.

■ Direction & weight of a Graph 그래프의 방향과 가중치

Graph는 이렇게 edge가 방향성을 가질 수 있는데, 이런 그래프는 Directed Graph라고 부른다. 방향이 없는 그래프는 Undirected/ Unordered Graph 라 부른다.

각 edge에는 weight, 가중치가 붙을 수 있다. cost라고 부르기도 한다. cost가 의미하는 것은 당연히 어떤 데이터를 저장하냐에 따라서 다르지만 예를 들면, 어떠한 과제를 수행하는데 걸리는 시간이나, 파이프의 반지름의 크기 (반지름이 클 수록 전달되는 물의 양의 클 것), 제한 속도 등이 될 수 있다.

■ Path & Cycle of a Graph

노드들 간의 순서를 Path 라고 하고, 모든 노드들 간에 Path가 있으면 Graph가 연결되어있다고 얘기한다.

Path의 시작 노드와 마지막 노드가 같은 경우 Path를 Cycle이라고 하고 뒤에 설명할 Tree 자료구조는 Graph의 한 종류인데, 시작 노드와 모든 노드를 연결하는 Path가 있지만 Cycle은 없는 Graph이다.

■ 그래프의 2가지 구현 방법

Graph class가 vertices와 edges를 담는 방법은 대표적으로 두가지가 있다.
- Adjacency List
- Adjacency Matrix

1. Adjacency List

Adjancey List의 개념은, 우선 모든 vertex를 담은 Master List가 있고, 각 노드에 인접한 모든 vertex들을 또 리스트로 만들어서 연결해준다. 구현할 수 있는 방법은 여러가지가 있다.

vertex 객체를 만들고, 인스턴스로 각 vertex 객체를 만든다. vertex 클래스는 vertex의 identifier나 인접한 verteces의 identifier를 담은 배열을 property로 가질 수 있다.

또 다른 예시로는, 모든 vertex를 담은 master list 배열이 있고, 각 노드에 인접한 이웃 노드들을 Linked List로 연결해줄 수 있다.

ES6의 new Map()을 활용할 수도 있다.
https://www.geeksforgeeks.org/implementation-graph-javascript/

Adjacency List는 공간효율성이 좋다. vertex들 간의 edge가 많지 않은 경우 더 유용하다. edge의 수가 vertex의 수에 비해 많다면, edge를 하나하나 찾아야해서 시간복잡도가 올라가는 단점이 있다.

2. Adjacency Matrix

두번째 방법인 Adjacency Matrix에서는 행과 열에 모든 vertex가 들어가고 두 vertex 사이에 edge가 있다면 교차하는 칸에 1을 넣는다. 방향이 없는 undirected graph라면 점선을 기준으로 symmetry가 발생한다. A → B 가 있으면 B→A 도 있기 때문이다.

구현은 2D array를 활용할 수 있다. Vertex 클래스를 만들고, 각 vertex를 인스턴스로 만든다. 그리고 vertex들 간의 edge를 2d array로 표현할 수 있다.

두 vertices 사이에 edge가 있는지 판단하려면 array lookup을 사용하면 되니까 시간복잡도가 O(1)일 것이다. 하지만, 공간 활용 측면에서는 edge가 별로 없는 graph에는 효율적이지 않다. 대부분의 칸이 비어있을 테니. 또한, undirected graph라면 symmetry로 인해 똑같은 정보가 두번 저장되는것이 된다.

■ Methods of a Graph

addVertex(v) : 그래프에 vertex 를 추가한다.
removeVertex(v) : 그래프에서 해당 vertex를 제거한다.
addEdge(v1, v2) : vertex v1과 v2사이에 edge를 추가한다.
removeEdge(v1, v2) : v1과 v2 사이에 edge를 제거한다.
hasEdge(v1, v2) : v1과 v2 사이에 edge가 있는지 확인한다.
contains(v) : 그래프가 주어진 v를 포함하고 있는지 확인한다.
forEachVertex(callback) : callback함수를 그래프의 모든 vertex에 실행한다. (배열의 map과 같은 원리)

■ 순회 방법

순회하는 방법은 두가지가 있다. 자세한건 영상 참고.

깊이 우선 탐색 (DFS — Depth First Search): 시작 vertex 부터 가장 깊은 (혹은 먼) 곳까지 탐색 후 탐색할 vertex가 없으면 새로 탐색할 vertex가 나올 때까지 다시 뒤로가서 새로 탐색한 그 vertex부터 다시 깊이 우선 탐색을 하고, 이 과정을 한번도 탐색하지 않은 vertex가 없을 때 까지 반복한다. Stack을 사용할 수 있다.
너비 우선 탐색 (BFS — Breadth First Search): 시작 vertex에서 갈 수 있는 이웃 vertex를 모두 탐색 후 다음 깊이를 검사한다. Queue를 사용할 수 있다.

🌲Tree

Tree는 graph 자료구조의 한 종류로, 노드간에 부조와 자식이 존재하고, 시작 노드부터 아래로 가능 방향을 가진 비순환 그래프이다.

구성을 살펴보자.

Root: 가장 위에 있는 노드, 한 tree당 한개의 root만 존재하고 root에서 다른 어떤 노드로 가는 path는 한개만 존재한다.
Parent: root를 제외한 모든 노드는 부모 노드를 가진다.
Child: 아래로 향하는 edge로 연결되어 아래에 있는 노드는 자식 노드.
Leaf: 자식이 없는 노드
Subtree: 한 노드의 후손 tree
Levels: 노드의 세대를 나타냄.

■ 다양한 Tree 종류

Binary Tree: 자식을 두개까지만 가질 수 있는 Tree
Balanced Tree: 노드가 양쪽으로 균형있게 있는 Tree
Unbalanced tree: 노드가 한쪽으로 만 있는 Tree

■ Properties and Methods of a Tree

property

children: subtree들을 담은 배열

methods

addChild( ): value를 받아서 자식 노드로 추가한다.
contains( ): value를 받아서 해당 value를 가진 노드가 있는지 여부를 Boolean값으로 리턴한다.

🌵Binary Search Tree

Binary Search Tree는 특별한 규칙을 가진 Tree이다. 노드의 왼쪽 자식 노드는 부모 노드보다 value가 작아야하고 노드의 오른쪽 자식 노드는 부모 노드보다 value가 커야한다. 규칙을 가지고 저장된 tree인 만큼 값을 찾을 때 빠르다는 장점이 있다.
사전에서 단어를 검색 할 때 사용할 수 있다.

■ Properties and Methods of a Binary Search Tree