[JS] 자료구조(2) 그래프 & 트리구조 & 이진탐색(BST)
그래프(Graph)
그래프는 객체 간의 연결을 시각적으로 표현한 것이다. 자세히 알아보기 전에 기본적인 용어부터 알아보자.
- 정점(vertex) : 그래프를 형성하는 노드다.
- 간선(edge) : 그래프에서 노드 간의 연결을 말한다. 그림상으로 간선은 정점간에 ‘선’이다.
- 무지향성 그래프(undirected graph) : 간선 간에 방향이 없는 그래프다. 간선은 두 노드 간에 방향없이 상호 연결을 암시한다.
- 진입차수(in-degree) / 진출차수(out-degree) : 한 정점에 진입하고 진출하는 간선의 개수를 말한다.
- 인접(adjacency) : 두 정점 간에 간선이 직접 이어져 있는지 나타낸다.
- 자기루프(self loop) / 사이클(cycle) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다라고 표현한다. 한 정점에서 출발해 다시 해당 정점으로 돌아갈 수 있도록 정점과 간선이 이어져 있다면 사이클이 있다고 표현한다. 둘의 차이점은 다른 정점을 거치는지 유무이다.
// 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;
}
}
트리(Tree)
이전에 DOM 포스팅에서 트리구조에 대해 간략하게 설명했는데, 좀 더 자세하게 살펴보자.
일반적인 트리 구조
일반적인 트리구조는 자식을 얼마든지 가질 수 있다. 코드로는 다음과 같다.
function TreeNode(value) {
this.value = value;
this.children = [];
}
이진트리
이진트리는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리자료구조로 삭제 방법에 따라 정 이진트리(Full binary tree), 완전 이진트리(Complete binary tree), 포화 이진트리(Perfect binary tree)로 나눈다.
function BinaryTreeNode(value) {
this,value = value;
this.left = null;
this.right = null;
}
- 정 이진 트리(full binary tree): 모든 트리의 자식은 0개나 2개다.
- 포화 이진 트리(perfect binary tree): 모든 리프 노드의 높이가 같고 리프 노드가 아닌 노드는 모두 2개의 자식을 갖는다. 이진 트리에서 리프 높이의 최대치가 n일 때 가장 많이 존재할 수 있는 노드의 수는 2n-1개인데 포화 이진 트리는 이 개수를 모두 채운 이진 트리라고도 볼 수 있다. 또한, 모든 포화 이진 트리는 정 이진 트리이다.
- 완전 이진 트리(complete binary tree): 모든 리프 노드의 높이가 최대 1 차이가 나고, 모든 노드의 오른쪽 자식이 있으면 왼쪽 자식이 있는 이진트리이다. 다시 말해 트리의 원소를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간 형태이다. 포화 이진 트리는 완전 이진 트리의 부분집합이다. 단, 포화 이진 트리가 아닌 완전 이진 트리는 정 이진 트리일 수도 있고 아닐 수도 있다.
이진 트리 순회 방법
- 전위 순회(Pre-order traversal): 자신, 왼쪽 자손, 오른쪽 자손 순서로 방문하는 순회 방법.
- 중위 순회(In-order traversal): 왼쪽 자손, 자신, 오른쪽 자손 순서로 방문하는 순회 방법. 이진 탐색 트리를 중위 순회하면 정렬된 결과를 얻을 수 있다.
- 후위 순회(Post-order traversal): 왼쪽 자손, 오른쪽 자손, 자신 순서로 방문하는 순회 방법.
맨 위의 트리구조를 순회하면 다음과 같다.
- 전위 순회(Pre-order traversal): 8 7 2 6 5 11 5 9 4
- 중위 순회(In-order traversal): 2 7 5 6 11 2 5 9 4
- 후위 순회(Post-order traversal): 2 5 11 6 7 4 9 5 2
이진 탐색 트리(Binary Search Tree, BST)
이진 트리와 마찬가지로 왼쪽과 오른쪽 두 개의 자식 노드가 있다. 하지만 이진 검색 트리의 경우 왼쪽 자식이 부모보다 작고 오른쪽 자식이 부모보다 크다.
이진 탐색 트리는 균형잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있다.
다음 코드를 참고해보고 공부하자.
class BinarySearchTree {
constructor(value) {
// constructor로 만든 객체는 이진 탐색 트리의 Node가 됩니다.
this.value = value;
this.left = null;
this.right = null;
}
// 이진 탐색 트리의 삽입하는 메서드를 만듭니다.
insert(value) {
// 입력값을 기준으로, 현재 노드의 값보다 크거나 작은 것에 대한 조건문이 있어야 합니다.
// 보다 작다면, Node의 왼쪽이 비어 있는지 확인 후 값을 넣습니다.
if (value < this.value) {
if (this.left === null) {
this.left = new BinarySearchTree(value);
} else {
this.left.insert(value)
}
// 보다 크다면, Node의 오른쪽이 비어 있는지 확인 후 값을 넣습니다.
} else if (value > this.value) {
if (this.right === null) {
this.right = new BinarySearchTree(value);
} else {
this.right.insert(value)
}
//그것도 아니라면, 입력값이 트리에 들어 있는 경우입니다.
} else {
return; // 아무것도 하지 않습니다.
}
}
// 앞서 구현했던 트리에 비해 이진 탐색 트리는 입력값과 트리 노드의 값의 크기를 비교하고 있습니다. 왜 그런 것일까요?
// 이진 탐색 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드를 만듭니다.
contains(value) {
if (value === this.value) {
return true;
}
// 입력값을 기준으로 현재 노드의 값보다 작은지 판별하는 조건문이 있어야 합니다.
if (value < this.value) {
if (this.left !== null && value === this.left.value){ // 노드의 왼쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true를 반환합니다.
return true
}
this.contains(this.value) // 일치하지 않다면 왼쪽 노드로 이동하여 다시 탐색합니다.
}
// 입력값을 기준으로 현재 노드의 값보다 큰지 판별하는 조건문이 있어야 합니다.
if (value > this.value) {
if (this.right !== null && value === this.right.value){ // 현재 노드의 오른쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true를 반환합니다.
return true
}
this.contains(this.value) // 일치하지 않다면 오른쪽 노드로 이동하여 다시 탐색합니다.
}
return false// 없다면 false를 반환합니다.
}
/*
트리의 순회에 대해 구현을 합니다.
지금 만드려고 하는 이 순회 메서드는 단지 순회만 하는 것이 아닌, 함수를 매개변수로 받아 콜백 함수에 값을 적용시킨 것을 순회해야 합니다.
전위 순회를 통해 어떻게 탐색하는지 이해를 한다면 중위와 후위 순회는 쉽게 다가올 것입니다.
*/
// 이진 탐색 트리를 전위 순회하는 메서드를 만듭니다.
preorder(callback) {
callback(this.value);
if (this.left) {
this.left.preorder(callback);
};
if (this.right) {
this.right.preorder(callback);
};
}
// 이진 탐색 트리를 중위 순회하는 메서드를 만듭니다.
inorder(callback) {
if (this.left) {
this.left.inorder(callback);
};
callback(this.value);
if (this.right) {
this.right.inorder(callback);
};
}
// 이진 탐색 트리를 후위 순회하는 메서드를 만듭니다.
postorder(callback) {
if (this.left) {
this.left.postorder(callback);
};
if (this.right) {
this.right.postorder(callback);
};
callback(this.value);
}
}