Tree 🌲
그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태.
트리는 계층적 자료 구조 = 데이터가 바로 아래에 있는 하나이상의 데이터에 한 개의 경로와 하나의 방향으로만 연결됨.
트리는 비선형 구조 = 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있다.
트리구조는 계층적이며 아래로만 뻗어 나가기 때문에 사이클이 없는 하나의 연결 그래프이다.
(사이클이 존재한다 = 시작 노드에서 출발해 다른 노드를 거쳐 시작 노드로 돌아올 수 있다)
위와 같이 트리를 여러가지 방식으로 설명해볼 수 있는데,
트리는 깊이, 레벨, 높이를 가진다.
깊이는 루트 노드를 0으로 해서 아래로 내려갈수록 1씩 증가한다.
레벨은 루트 노드를 1로 해서 아래로 내려갈수록 1씩 증가하는데, 같은 레벨에 있는 노드들을 '형제 노드'라고 한다.
높이는 자식 노드가 없는 Leaf Node를 기준으로 측정할 수 있는데, 다른 깊이나 레벨을 가진 노드라도 Leaf Node이면 높이가 0이 된다.
이렇게 되면 어떤 부모 노드는 높이가 다른 자식 노드들을 가지게 되는데, 부모 노드의 높이는 자식 노드들 중 가장 높은 높이에 +1을 한 값을 높이로 가지게 된다.
트리 구현
class Tree {
constructor(value) {
// constructor로 만든 객체는 트리의 Node가 됨.
this.value = value; // 입력 데이터를 담는 value
this.children = []; // 하위 노드를 저장할 수 있는 배열 타입의 children
}
// 트리의 삽입 메서드 : 입력받은 value를 Tree에 계층적으로 추가할 수 있어야 한다.
insertNode(value) {
const childNode = new Tree (value) ;
this.children.push(childNode);
}
// 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드
contains(value) {
//현재 노드에서 해당 값이 포함되어 있다면 true
if (this.value === value) {
return true;
}
//값을 찾을 때까지 children 배열을 순회하며 childNode를 탐색한다.
for (let i = 0; i < this.children.length; i += 1) {
const childNode = this.children[i];
if (childNode.contains(value)) {
return true;
}
}
// 전부 탐색했음에도 불구하고 찾지 못했다면 false를 반환한다.
return false;
}
}예시
컴퓨터의 디렉토리 구조, 월드컵 토너먼트 대진표, 가계도(족보), 조직도 등
트리 탐색 🔎
이진 트리 (Binary Tree)
자식 노드가 최대 두 개인 노드들로 구성된 트리로 자료의 삽입, 삭제 방법에 따라
정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉨.
- 정 이진 트리(Full binary tree) : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다.
- 포화 이진 트리(Perfect binary tree) : 정 이진 트리이면서 완전 이진 트리인 경우. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리.
- 완전 이진 트리(Complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 함.
이진 트리는 이진 탐색 트리와 이진 힙 구현에 사용되며, 효율적인 검색과 정렬을 위해 사용됨.
이진 탐색 트리 (Binary Search Tree)
이진 탐색과 연결 리스트를 결합한 이진트리.
이진 탐색의 효율적 탐색 능력을 유지하면서 빈번한 자료 입력과 삭제 가능하도록.
- 각 노드에 중복되지 않는 Key가 있음
- 루트 노드의 왼쪽 서브트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어짐.
- 루트 노드의 오른쪽 서브트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어짐.
- 좌우 서브트리도 모두 이진 탐색 트리.
즉 이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있음.
이진 탐색을 이용해 어떤 값을 찾을 때
루트 노트와의 비교 동일하면 탐색 종료
=> 아닌 경우 찾는 값이 루트 노드보다 작으면 왼쪽 서브 트리로 탐색 || 크면 오른 쪽 서브 트리로 탐색 진행
위와 같은 과정을 거쳐 찾는 값을 찾을 때까지 반복함.
값을 찾지 못하면 그대로 연산을 종료함.
이런 탐색 과정을 거치면 무조건 트리 높이(h) 이하만큼 탐색을 진행한다.
트리 안에 찾고자 하는 값이 없어도 최대 h번의 연산 및 탐색이 진행된다.
이진 탐색 트리 구현
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 {
}
}
// 이진 탐색 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드
contains(value) {
//값이 포함되어 있다면 true를 반환.
if (this.value === value) {
return true;
}
// 입력값을 기준으로 현재 노드의 값보다 작은지 판별한다.
if (value < this.value) {
return !!(this.left && this.left.contains(value));
//현재 노드의 왼쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true를 반환.
//일치하지 않다면 왼쪽 노드로 이동하여 다시 탐색한다. (재귀 이용)
}
// 입력값을 기준으로 현재 노드의 값보다 큰지 판별한다.
//이하 동일
if (value > this.value) {
return !!(this.right && this.right.contains(value));
}
}
/*
트리의 순회에 대한 구현.
이 순회 메서드는 단지 순회만 하는 것이 아닌,
함수를 매개변수로 받아 콜백 함수에 값을 적용시킨 것을 순회하도록 함.
*/
// 이진 탐색 트리를 전위 순회하는 메서드
//루트 노드 탐색 => 자식노드 탐색
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);
}
}트리 순회 🎡
특정 목적을 위해 모든 노드를 한 번씩 방문하는 것
트리 구조는 계층적 구조라는 특별한 특징을 가지기 때문에, 모든 노드를 순회하는 방법엔 크게 세 가지가 있음.
트리 순회는 트리 탐색에 비해 좀 더 복잡한데, 순회의 경우 모든 노드를 방문해야 하고, 이렇게 모든 노드 방문을 위해서는 일정 조건이 필요함.
트리 구조를 유지보수하거나 특정 목적을 위해서도 순회 방법에 대한 정의 필수적으로 필요함.
전위 순회 (preorder traverse)
: 가장 먼저 루트 노트 방문. 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색. 즉 부모 노드가 제일 먼저 방문되는 순회 방식.
전위 순회는 주로 부모 노드가 먼저 생성되어야 하는 트리를 복사할 때 사용.
중위 순회 (inorder traverse)
: 루트를 가운데에 두고 순회합니다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색. 부모 노드가 서브 트리의 방문 중간에 방문되는 순회 방식. 중위 순회는 이진 탐색 트리의 오름차순으로 값을 가져올 때 쓰임.
후위 순회 (prostorder traverse)
: 루트를 가장 마지막에 순회. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문. 후위 순회는 트리를 삭제할 때 사용. (자식 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있음.)
Graph
여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
- 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있으나, 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어짐.
- 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge)이라고 함.
예시
포털 사이트의 검색 엔진, SNS에서 사람들의 관계, 내비게이션(길 찾기) 등에서 사용.
수 많은 정점을 가지고 있고, 서로 관계 있는 정점은 간선으로 이어져있는 구조.
표현 방식
인접 행렬
두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접한데, 이 인접한 상태를 표시한 행렬로 2차원 배열의 형태로 나타냄.
A 정점과 C 정점이 이어져 있으면 1(true), 아니면 0(false)로 표시한 일종의 표.
위 이미지와 같은 경우 아래와 같은 배열로 행렬을 만들 수 있다.
[
[0, 0, 1]
[1, 0, 1]
[1, 0, 0]
]
연결의 강도가 추가된 '가중치 그래프'의 경우에는 1으로 표시하는 대신에 의미 있는 값을 저장할 수도 있다고 함.
이런 인접 행렬은 두 정점 사이에 관계가 있는지 없는지 확인하는 데 용이함.
인접 행렬 구현
- Class로 구현
//배열의 인덱스를 정점(vertex)로 사용할 것임.
class GraphWithAdjacencyMatrix {
constructor() {
this.matrix = [];//matrix가 행렬을 뜻한다
}
//정점을 추가하는 매서드
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));
}
//특정 정점이 있는지 확인하는 매서드
contains(vertex) {
return !!this.matrix[vertex]
}
//간선 추가하는 매서드
addEdge(from, to) {
const currentLength = this.matrix.length -1;
//시작하는 정점과 도착하는 정점을 둘 중 하나라도 받지 못하면 아무 일도 일어나지 않는다.
if (from === undefined || to === undefined) {
console.log("2개의 인자가 있어야 합니다.");
return;
}
//인자가 입력되었더라도 간선을 추가할 수 없는 상황에서는 추가하지 않는다.
//없는 정점들 (정점들이 담긴 배열의 길이보다 크거나, 0보다 작은 경우)
if (from > currentLength || to > currentLength || from < 0 || to < 0) {
console.log("범위가 매트릭스 밖에 있습니다.");
return;
}
//위의 모든 경우에 걸리지 않았다면 간선을 추가함.
this.matrix[from][to] = 1
}
//두 정점 사이에 간선이 있는지 확인하는 매서드
hasEdge(from, to) {
return !!this.matrix[from][to]
}
//정점 사이의 간선을 지우는 매서드
removeEdge(from, to) {
const currentLength = this.matrix.length -1;
if (from === undefined || to === undefined) {
console.log("2개의 인자가 있어야 합니다.");
return;
}
//간선을 지울 수 없는 상황에서는 지우지 않는다.
if (from > currentLength || to > currentLength || from < 0 || to < 0) {
console.log("범위가 매트릭스 밖에 있습니다.");
return;
}
//간선을 지운다.
this.matrix[from][to] = 0
}
}- 배열로 구현
//edges에는 각각 간선의 시작 정점, 간선의 도착 정점, 방향성(undirected, directed)가 담긴 배열이 전달 인자로 전달된다.
//undirected는 양방향, directed는 단방향을 말한다
function createMatrix(edges) {
// 행렬의 크기를 구한다.
// max 변수를 0으로 할당하고, edges를 전부 순회해 제일 큰 숫자를 max에 할당함.
// max보다 크지 않을 경우엔 바꾸지 않는다.
let max = 0;
for (let i = 0; i < edges.length; i++) {
// edges의 한 요소에는 숫자 이외에 방향성도 있으니, 숫자까지만 slice를 하여 비교합니다.
const curMax = Math.max(...edges[i].slice(0, 2));
curMax > max ? (max = curMax) : null;
}
// matrix의 뼈대 잡기 (0을 이용)
// max로 구한 최대값에 1을 더하여 array를 만들고(0번째부터 있음) 전부 0으로 채운 뒤
// map을 사용해 각 요소마다 배열로 바꿔주는데,배열의 크기를 이번에도 최대값에 1을 더한 뒤, 0으로 채운다.
const result = new Array(max + 1).fill(0).map((row) => new Array(max + 1).fill(0));
// edges를 순회하며 무향(양방향인)곳에는 각각의 간선에 1로 바꾸어 주고,
//방향이 있는 간선엔 해당 간선에만 1로 바꾸어 준다.
edges.forEach((edge) => {
const [row, col, direction] = edge;//구조분해할당 써서 변수처럼 활용할 수 있음
if (direction === "undirected") {
result[col][row] = 1;
}
result[row][col] = 1;
});
// result를 반환합니다.
return result;
}
인접 리스트
인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현. 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있음.
인접 리스트는 메모리를 효율적으로 사용하고 싶을 때 사용하는데, 인접 행렬의 경우 가능한 모든 수를 저장하기 때문에 상대적으로 메모리를 많이 쓰는 편.
위 이미지는 인접 행렬에서 사용한 Graph를 인접 리스트 형식으로 바꾼 것.
인접 리스트 구현
class GraphWithAdjacencyList {
constructor() {
this.vertices = {};//정점과 간선을 담을 수 있는 객체로 만들어진다.
}
//정점을 추가하는 매서드
addVertex(vertex) {
// 넘겨받은 인자(정점)은 키가 되며, 빈 배열을 값으로 할당한다.
// 이미 존재하는 정점이라면, 덮어 씌워지지 않아야 함.
this.vertices[vertex] === undefined ? this.vertices[vertex] = [] : null
}
//정점이 존재하는지 확인하는 매서드
contains(vertex) {
return !!this.vertices[vertex];
}
//간선을 추가하는 매서드
addEdge(fromVertex, toVertex) {
// fromVertex의 인접 리스트에 toVertex를 추가하고
// toVertex의 인접 리스트에 fromVertex를 추가한다.
//인자로 받은 정점들이 존재하는지 확인
if (!this.contains(fromVertex) || !this.contains(toVertex)) {
return;
}
//둘 사이에 간선이 존재하지 않으면 from 정점 인접 리스트에 to 정점을 추가해준다
if (!this.hasEdge(fromVertex, toVertex)) {
this.vertices[fromVertex].push(toVertex)
}
//둘 사이에 간선이 존재하지 않으면 to 정점 인접 리스트에 from 정점을 추가해준다
if (!this.hasEdge(toVertex, fromVertex)) {
this.vertices[toVertex].push(fromVertex)
}
}
//간선이 존재하는지 확인하는 매서드
hasEdge(fromVertex, toVertex) {
// 만약 정점(fromVertex)이 존재하지 않는다면
if (!this.contains(fromVertex)) {
// false를 반환.
return false;
}
// 존재한다면 해당 정점의 리스트에 toVertex가 포함되어있는지 반환.
return !!this.vertices[fromVertex].includes(toVertex);
}
//간선을 삭제하는 매서드
removeEdge(fromVertex, toVertex) {
// 인자로 넘겨받은 두 정점이 모두 존재한다면
// fromVertex의 인접 리스트에 있는 toVertex를 삭제하고
// toVertex의 인접 리스트에 있는 fromVertex를 삭제함.
// 추가하는 것과 동일한 방식
if (!(this.contains(fromVertex)) || !(this.contains(toVertex))) {
return;
}
if (this.hasEdge(fromVertex, toVertex)) {
const index = this.vertices[fromVertex].indexOf(toVertex);
this.vertices[fromVertex].splice(index, 1);
}
if (this.hasEdge(toVertex, fromVertex)) {
const index = this.vertices[toVertex].indexOf(fromVertex);
this.vertices[toVertex].splice(index, 1);
}
}
//정점을 삭제하는 매서드
removeVertex(vertex) {
// 인자로 넘겨받은 정점(A)이 존재한다면
// 이 정점(A)을 삭제하고
// 다른 모든 정점들의 리스트를 순회하며 넘겨받은 정점(A)과 이어져 있는 간선을 제거한다.
if (this.contains(vertex)) {
// 연결된 간선들부터 지우고
while (this.vertices[vertex].length > 0) {
this.removeEdge(this.vertices[vertex][0], vertex);
}
// 해당 정점을 삭제합니다
delete this.vertices[vertex];
}
}
}
그래프 탐색 🔎
BFS (Breadth-First-Search) 너비 우선 탐색
두 정점 사이의 최단 경로를 찾을 때 사용.
가까운 정점부터 탐색한 뒤 더는 탐색할 정점이 없을 때 그 다음 떨어져 있는 정점을 순서대로 방문함.
경로 탐색 시 가장 먼저 찾아지는 해답이 곧 최단거리.
경로를 하나씩 전부 방문한다면 최악의 경우에는 모든 경로를 다 살펴보아야 함.
DFS (Depth-First-Search) 깊이 우선 탐색
하나의 경로를 끝까지 탐색한 후, 다음 경로로 넘어가서 탐색함.
하나의 노선을 끝까지 탐색하므로 운이 좋다면 단 몇 번 만에 경로를 찾을 수 있음.
한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용.
BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있음.
DFS와 BFS는 모든 정점을 한 번만 방문한다는 공통점을 가짐.
