[1] 트리 (Tree)
- 방향 그래프의 일종으로 정점을 가리키는 간선이 하나밖에 없는 구조를 가짐
- 하나의 루트에서 하위로 뻗어나가는 구조
- ex) 조직도, 디렉터리 구조, ...
트리의 특징
- 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가짐
- 정점이 N개인 트리는 반드시 N-1개의 간선을 가짐
- 루트에서 특정 정점으로 가는 경로는 유일
이진트리
- 각 정점이 최대 2개의 자식을 가지는 트리를 의미
- 특징
- 정점이 N개인 이진 트리는 최악의 경우 높이가 N이 될 수 있음
- 정점이 N개인 포화 또는 완전 이진트리의 높이는 logN
- 높이가 n인 포화 이진 트리는 2ⁿ - 1개의 정점을 가짐
- 일반적인 이진트리를 사용하는 경우는 많지 않음. 다음 자료구조에 응용됨
- 이진 탐색 트리, 힙, AVL 트리, 레드 블랙 트리, ... 등을 구현하기 위해 사용되는 경우가 많음
트리의 구현 방법
- 그래프와 마찬가지로 인접 행렬, 인접 리스트 두가지 방식으로 트리를 표현할 수 있음
이진 트리의 구현 방법
- 배열 혹은 요소에 링크가 2개 존재하는 연결 리스트로 구현할 수 있음
- 자식의 수가 2개 이하로 제한되는 특징 때문에 좀 더 최적화된 방식으로 구현 가능
JavaScript에서 사용법
-> 구현할 이진 트리
이진 트리를 배열(Array)로 구현
// 0번 인덱스는 편의를 위해 비워둠
// Left = Index*2
// Right = Index*2 + 1
// Parent = floor(Index / 2)
const tree = [
undefined,
// 1
9,
// 1*2, 1*2+1
3, 8,
//2*2, 2*2+1, 3*2, 3*2+1
2, 5, undefined, 7,
//4*2, 4*2+1, 5*2, 5*2+1
undefined, undefined, undefined, 4
];이진 트리를 연결 리스트(Linked List)로 구현
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class Tree {
constructor(node) {
this.root = node;
}
display() {
// Level Order
const queue = new Queue();
queue.enqueue(this.root);
while(queue.size) {
const currentNode = queue.dequeue();
console.log(currentNode.value);
if(currentNode.left) queue.enqueue(currentNode.left);
if(currentNode.right) queue.enqueue(currentNode.right);
}
}
}
const tree = new Tree(new Node(9));
tree.root.left = new Node(3);
tree.root.right = new Node(8);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(7);
tree.root.left.right.right = new Node(4);[2] 힙 (Heap)
우선순위 큐
- FIFO인 큐와 달리 우선순위가 높은 요소가 먼저 나가는 큐
-> 우선순위 큐는 자료 구조가 아니라 개념
(우선순위 큐를 구현하는 방법은 다양하게 존재할 수 있음)
힙
- 우선순위 큐를 구현하기 위한 가장 적합한 방법 (우선순위 큐 != 힙)
- 이진트리 형태를 가지며, 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제될 때 바로 정렬되는 특징이 있음
- 특징
- 우선순위가 높은 요소가 먼저 나가는 특징을 가짐 (우선순위가 높은 것을 루트로 두고, 항상 루트가 먼저 나감 )
- 루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 루트가 가장 작은 값이 되는 최소 합(Min Heap)이 있음
- 아쉽게도 자바스크립트에선 직접 구현해 사용해야 함
힙(Heap) 요소 추가
힙 요소 추가 알고리즘
- 요소가 추가될 때는 트리의 가장 마지막에 정점에 위치
- 추가 후 부모 정점보다 우선순위가 높다면, 부모 정점과 순서를 바꿈
- 이 과정을 반복하면 결국 가장 우선순위가 높은 정점이 루트가 됨
- 완전 이진트리의 높이는 log N이기에 힙의 요소 추가 알고리즘은 O(log N) 시간복잡도를 가짐
( 요소는 항상 이진트리의 마지막에 추가되기 때문에, 힙은 항상 완전이진트리)
힙(Heap) 요소 제거
힙 요소 제거 알고리즘
- 요소 제거는 루트 정점만 가능
- 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치
- 루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꿈
- 두 자식 정점이 우선순위가 더 낮을 때까지 반복
- 완전 이진 트리의 높이는 logN이기 때문에 힙 요소 제거 알고리즘은 O(log N) 시간복잡도를 가짐
JavaScript에서 사용법
힙 요소 추가
class MaxHeap {
constructor() {
this.heap = [null];
}
push(value) {
this.heap.push(value);
let currentIndex = this.heap.length - 1;
let parentIndex = Math.floor(currentIndex / 2);
while (parentIndex !== 0 && this.heap[parentIndex] < value) {
const temp = this.heap[parentIndex];
this.heap[parentIndex] = value;
this.heap[currentIndex] = temp;
currentIndex = parentIndex;
parentIndex = Math.floor(currentIndex / 2);
}
}
}
const heap = new MaxHeap();
heap.push(45);
heap.push(36);
heap.push(54);
heap.push(27);
heap.push(63);
console.log(heap.heap);
// Result : [ null, 63, 54, 45, 27, 36 ]힙 요소 제거
class MaxHeap {
constructor() {
this.heap = [null];
}
push(value) {
this.heap.push(value);
let currentIndex = this.heap.length - 1;
let parentIndex = Math.floor(currentIndex / 2);
while (parentIndex !== 0 && this.heap[parentIndex] < value) {
const temp = this.heap[parentIndex];
this.heap[parentIndex] = value;
this.heap[currentIndex] = temp;
currentIndex = parentIndex;
parentIndex = Math.floor(currentIndex / 2);
}
}
pop() {
const returnValue = this.heap[1];
this.heap[1] = this.heap.pop();
let currentIndex = 1;
let leftIndex = 2;
let rightIndex = 3;
while (
this.heap[currentIndex] < this.heap[leftIndex] ||
this.heap[currentIndex] < this.heap[rightIndex]
) {
if (this.heap[leftIndex] < this.heap[rightIndex]) {
const temp = this.heap[currentIndex];
this.heap[currentIndex] = this.heap[rightIndex];
this.heap[rightIndex] = temp;
currentIndex = rightIndex;
} else {
const temp = this.heap[currentIndex];
this.heap[currentIndex] = this.heap[leftIndex];
this.heap[leftIndex] = temp;
currentIndex = leftIndex;
}
leftIndex = currentIndex * 2;
rightIndex = currentIndex * 2 + 1;
}
return returnValue;
}
}
const heap = new MaxHeap();
heap.push(45);
heap.push(36);
heap.push(54);
heap.push(27);
heap.push(63);
console.log(heap.heap);
// Result : [ null, 63, 54, 45, 27, 36 ]
const array = [];
array.push(heap.pop());
array.push(heap.pop());
array.push(heap.pop());
array.push(heap.pop());
array.push(heap.pop());
console.log(array);
//Result : [ 63, 54, 45, 36, 27 ] - Heap Sort![3] 트라이 (Trie)
- 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
- 특징
- 검색어 자동완성, 사전 찾기 등에 응용될 수 있음
- 문자열을 탐색할 때, 단순하게 비교하는 것보다 효율적으로 찾을 수 있음
- L이 문자열을 길이일 때, 삽입은 O(L)만큼 걸림
- 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장공간을 더 많이 사용함
트라이(Trie) 생성하기
트라이 구조
- 루트는 비어있음
- 각 간선(링크)은 추가될 문자를 키로 가짐
- 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가짐
- 해시 테이블과 연결 리스트를 이용하여 구현할 수 있음
JavaScript에서 사용법
트라이 구성
class Node {
constructor(value = "") {
this.value = value;
this.children = new Map();
}
}
class Trie{
constructor() {
this.root = new Node();
}
insert(string) {
let currentNode = this.root;
for(const char of string) {
if(!currentNode.children.has(char)) {
currentNode.children.set(
char,
new Node(currentNode.value + char)
);
}
currentNode = currentNode.children.get(char);
}
}
has(string) {
let currentNode = this.root;
for(const char of string) {
if(!currentNode.children.has(char)) {
return false;
}
currentNode = currentNode.children.get(char);
}
return true;
}
}
const trie = new Trie();
trie.insert("cat");
trie.insert("can");
console.log(trie.has("cat")); // true
console.log(trie.has("can")); // true
console.log(trie.has("cap")); // false[4] 정렬(Sort)
- 요소들을 일정한 순서대로 열거하는 알고리즘
- 특징
- 정렬 기준은 사용자가 정할 수 있음
- 크게 비교식과 분산식 정렬로 나눌 수 있음
- 대부분의 언어가 빌트인으로 제공해줌
- 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재
비교식 정렬
버블 정렬
- 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘
- O(n²) 시간복잡도를 가짐
선택 정렬
- 선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘
- O(n²) 시간복잡도를 가짐
삽입 정렬
- 선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘
- O(n²) 시간복잡도를 가짐
- 복잡하지만 어느정도 정렬이 되어있다는 과정 하에 퀵 정렬보다도 빠른 성능을 보여줌
분산식 정렬
분할 정복
- 문제를 작은 2개의 문제로 분리하고 더 이상 분리가 불가능할 때 처리한 후 합치는 전략
- 다양한 알고리즘에 응용됨
합병 정렬
- 분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬 알고리즘
- O(n log n) 시간복잡도를 가짐
큌 정렬
- 분할 정복 알고리즘을 이용한 매우 빠르지만, 최악의 경우가 존재하는 불안정 정렬
- O(n log n) 시간복잡도를 가짐
JavaScript에서 정렬 사용법
sort
const array = [5, 9, 10, 3, 8, 3, 2];
// 다음과 같이 그냥 정렬하면 ASCII 문자 순서대로 정렬되어
// 우리가 원하는 숫자 크기대로 정렬되지 않음
array.sort();
console.log(array); // [ 10, 2, 3, 3, 5, 8, 9 ]
// 10이 먼저 나오는 이유는 ASCII 문자 '1'이 '2'보다 작기 때문
array.sort((a, b) => a-b); // 오름차순 정렬
console.log(array); // [ 2, 3, 3, 5, 8, 9, 10 ]
array.sort((b, a) => a-b); // 내림차순 정렬
console.log(array); // [ 10, 9, 8, 5, 3, 3, 2 ]
[5] 이진 탐색 (Binary Search)
선형 탐색
- 순서대로 하나씩 찾는 알고리즘
- O(n) 시간복잡도가 걸림
이진 탐색
- 정렬되어있는 요소들을 반씩 제외하며 찾는 알고리즘
- O(log n) 만큼의 시간복잡도가 걸림
- 특징
- 반드시 정렬이 되어있어야 사용할 수 있음
- 배열 혹은 이진 트리를 이용하여 구현할 수 있음
- O(log n) 시간복잡도인 만큼 상당히 빠름
배열을 이용한 구현 방법
이진 탐색 트리를 이용한 구현 방법
이진 탐색 트리
- 이진 탐색을 위한 이진 트리로, 왼쪽 서브 트리는 루트보다 작은 값이 모여있고, 오른쪽 서브 트리는 루트보다 큰 값이 모여있음
이진 탐색 트리 요소 추가
이진 탐색 트리 요소 삭제
단말 정점을 삭제하는 경우
- 별다른 처리 없이 부모 정점과의 연결을 끊으면 됨
하나의 서브 트리를 가지는 경우
- 제거되는 정점의 부모 간선을 자식 정점을 가르키게 바꾸면 됨
두 개의 서브 트리를 가지는 경우
- 왼쪽 서브 트리의 가장 큰 값 혹은 오른쪽 서브 트리의 가장 작은 값과 교체하면 됨
- 이 경우, 교체된 정점의 좌우 자식이 없다면, 제거되는 정점의 링크로 대체됨
이진 탐색 트리의 문제점
-
최악의 경우 한쪽으로 편향된 트리가 될 수 있음
-
그런 경우 순차 탐색과 동일한 시간복잡도를 가짐
-
이를 해결하기 위해 다음과 같은 자료구조를 이용할 수 있음
- AVL 트리, 레드-블랙 트리
JavaScript에서 정렬 사용법
Array
const array = [1, 1, 5, 124, 400, 599, 1004, 2876, 8712];
function binarySearch(array, findValue) {
let left = 0;
let right = array.length - 1;
let mid = Math.floor((left + right) / 2);
while (left < right) {
if(array[mid] === findValue) {
return mid;
}
if(array[mid] < findValue) {
left = mid + 1;
} else {
right = mid - 1;
}
mid = Math.floor((left + right) / 2);
}
return -1;
}
console.log(binarySearch(array, 2876)); // 7
console.log(binarySearch(array, 1)); // 1
console.log(binarySearch(array, 500)); // -1Binary Search Tree
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySerachTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new Node(value);
if(this.root === null) {
this.root = newNode;
return;
}
let currentNode = this.root;
while (currentNode !== null) {
if(currentNode.value < value) {
if(currentNode.right === null) {
currentNode.right = newNode;
break;
}
currentNode = currentNode.right;
} else {
if(currentNode.left === null) {
currentNode.left = newNode;
break;
}
currentNode = currentNode.left;
}
}
}
has(value) {
let currentNode = this.root;
while(currentNode !== null) {
if(currentNode.value === value) {
return true;
}
if(currentNode.value < value) {
currentNode = currentNode.right;
} else {
currentNode = currentNode.left;
}
}
return false;
}
}
const tree = new BinarySerachTree();
tree.insert(5);
tree.insert(4);
tree.insert(7);
tree.insert(8);
tree.insert(5);
tree.insert(6);
tree.insert(2);
console.log(tree.has(8)); // true
console.log(tree.has(1)); // false
안녕하세요