Tree
무방향 그래프의 한 구조로 하나의 root 뿌리로부터 가지가 사방으로 뻗은 형태
하나의 데이터 뒤에 여러개의 데이터가 존재할 수 있는 비선형 구조
계층적으로 표현되고 아래로만 뻗어나가기 때문에 사이클이 없다.
용어
•
노드 Node : 트리 구조를 이루는 모든 개별 데이터
•
루트 Root : 트리 구조의 시작점이 되는 노드
•
부모 노드 Parent node : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
•
자식 노드 Child node : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
•
리프 Leaf : 트리 구조의 끝 지점이고 자식 노드가 없는 노드
•
깊이 depth : root로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있음, root의 깊이는 0
•
레벨 level : 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현. root는 level 1, 같은 레벨에 나란히 있는 노드를 형제 노드라고 함
•
높이 height : 리프 노드를 기준으로 루트까지의 높이를 표현, 각 리프 노드의 높이를 0으로 놓는다.
•
서브 트리 sub tree: root에서 뻗어나오는 큰 트리의 내부에 트리 구조를 갖춘 작은 트리
이진 트리
자식 노드를 최대 2개 가지는 트리
종류
•
정 이진트리 full binary tree : 각 노드가 0개 혹은 2개의 자식 노드를 갖음
•
완전 이진트리 complete binary tree : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 함
•
포화 이진트리 perfect binary tree : 정 이진 트리이면서 완전 이진트리인 경우. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.
트리 순회
전위 순회 Preorder
루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드 탐색
부모 - 왼쪽 - 오른쪽
중위 순회 Inorder
루트를 가운데 두고 순회. 제일 왼쪽 노드부터 순회하기 시작해 루트를 기준으로 왼쪽 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색
오른차순 정렬
왼쪽 - 부모 -오른쪽
후위 순회 Postorder
루트를 가장 마지막에 순회. 제일 왼쪽 끝의 노드부터 순회하여 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트 방문
왼쪽 - 오른쪽 - 부모
class Tree {
constructor(value) {
// constructor로 만든 객체는 트리의 Node가 됩니다.
this.value = value;
this.children = [];
}
// 트리의 삽입 메서드를 만듭니다.
insertNode(value) {
// 값이 어떤 이름으로 만들어지고 어느 위치에 붙는지 떠올리는 것이 중요합니다.
// TODO: 트리에 붙게 될 childNode를 만들고, children에 넣어야 합니다.
const childNode = new Tree(value);
this.children.push(childNode);
}
// 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드를 만듭니다.
contains(value) {
// TODO: 값이 포함되어 있다면 true를 반환하세요.
if (this.value === value) {
return true;
}
// TODO: 값을 찾을 때까지 children 배열을 순회하며 childNode를 탐색하세요.
for (let i of this.children) {
if (i.contains(value)) return true;
}
// 전부 탐색했음에도 불구하고 찾지 못했다면 false를 반환합니다.
return false;
}
}
JavaScript
복사
Binary Search Tree
자식 노드가 최대 두개인 노드들로 구성된 트리
이진 탐색 트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가짐
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 {
// TODO: 비어 있지 않다면 해당 노드로 이동하여 처음부터 다시 크거나 작은 것에 대한 조건을 물어보아야 할 것입니다.
// TIP: 재귀함수를 사용합니다.
this.left.insert(value);
}
// 보다 크다면, Node의 오른쪽이 비어 있는지 확인 후 값을 넣습니다.
} else if (value > this.value) {
if (this.right === null) {
this.right = new BinarySearchTree(value);
} else {
// TODO: 비어 있지 않다면 해당 노드로 이동하여 처음부터 다시 크거나 작은 것에 대한 조건을 물어보아야 할 것입니다.
// TIP: 재귀함수를 사용합니다.
this.right.insert(value);
}
//그것도 아니라면, 입력값이 트리에 들어 있는 경우입니다.
} else {
// 아무것도 하지 않습니다.
return;
}
}
// 앞서 구현했던 트리에 비해 이진 탐색 트리는 입력값과 트리 노드의 값의 크기를 비교하고 있습니다. 왜 그런 것일까요?
// 이진 탐색 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드를 만듭니다.
contains(value) {
// TODO: 값이 포함되어 있다면 true를 반환하세요.
if (this.value === value) {
return true;
}
// 입력값을 기준으로 현재 노드의 값보다 작은지 판별하는 조건문이 있어야 합니다.
if (value < this.value) {
// TODO: 현재 노드의 왼쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true를 반환합니다.
if (this.left !== null) {
if (this.left.value === value) {
return true;
}
this.left.contains(value);
}
// TODO:일치하지 않다면 왼쪽 노드로 이동하여 다시 탐색합니다.
}
// 입력값을 기준으로 현재 노드의 값보다 큰지 판별하는 조건문이 있어야 합니다.
if (value > this.value) {
// TODO: 현재 노드의 오른쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true를 반환합니다.
if (this.right !== null) {
if (this.right.value === value) {
return true;
}
this.right.contains(value);
}
// TODO:일치하지 않다면 오른쪽 노드로 이동하여 다시 탐색합니다.
}
// 없다면 false를 반환합니다.
return false;
}
/*
트리의 순회에 대해 구현을 합니다.
지금 만드려고 하는 이 순회 메서드는 단지 순회만 하는 것이 아닌, 함수를 매개변수로 받아 콜백 함수에 값을 적용시킨 것을 순회해야 합니다.
전위 순회를 통해 어떻게 탐색하는지 이해를 한다면 중위와 후위 순회는 쉽게 다가올 것입니다.
*/
// 이진 탐색 트리를 전위 순회하는 메서드를 만듭니다.
preorder(callback) {
callback(this.value);
if (this.left) {
this.left.preorder(callback);
};
if (this.right) {
this.right.preorder(callback);
};
}
// 이진 탐색 트리를 중위 순회하는 메서드를 만듭니다.
inorder(callback) {
//TODO: 전위 순회를 바탕으로 중위 순회를 구현하세요.
if (this.left) {
this.left.inorder(callback);
};
callback(this.value);
if (this.right) {
this.right.inorder(callback);
};
}
// 이진 탐색 트리를 후위 순회하는 메서드를 만듭니다.
postorder(callback) {
//TODO: 전위 순회를 바탕으로 후위 순회를 구현하세요.
if (this.left) {
this.left.postorder(callback);
};
if (this.right) {
this.right.postorder(callback);
};
callback(this.value);
}
}
JavaScript
복사
•
장점
•
단점 : 한쪽으로 서브트리가 계속 구성되어지는 경우, 자류가 많아질수록 트리의 높이가 커지므로 검색에 불리해지고 최악의 경우 노드를 탐색하는데 logn이 소요될 수 있다.
Balanced Binary Search Tree
트리에 노드의 삽입과 삭제가 일어나는 경우에 자동으로 그 높이를 작게 유지하도록 되어있음
AVL Tree, Red-Black Tree, B Tree, B+ Tree, B* Tree