*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.
*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)
1. 트리(Trees)란?
트리는 우리가 아는 나무를 거꾸로 뒤집어 놓은 형태를 생각하면 쉽다. 가장 위는 뿌리인 Root, 그리고 아래로 가지를 치면서 뻗어 내려온다.
2. 바이너리 트리(Binary Trees)
바이너리 트리는 각 노드가 하나 혹은 2개의 자식 노드만을 가지고 있는 상태의 트리구조이다. 하나의 노드는 아래와 같은 코드가 된다.
function BinaryTreeNode(value) {
this.value = value;
this.left = null;
this.right = null;
}Linked List와 무척 유사하다.
# Perfect Binary Trees
자식 노드가 없는 leaves를 제외한 모든 노드가 2개의 노드를 가지고 있으며, Tree의 맨 마지막 layer의 모든 element가 값이 채워져 있는 형태의 바이너리 트리를 Perfect Binary Tree라고 한다.
*Full Binary Tree : 각 element의 child가 0개이거나 2개인 바이너리 트리. 1개만 있는 경우 Full Binary Tree가 아니다.
이러한 Perfect Binary Tree는 아주 효율적이다.
1) 각 level에서 한 단계 아래 layer로 내려가면 노드의 수는 정확하게 2배가 된다. 1개 > 2개 > 4개 > 8개 > ...
2) 마지막 level의 모든 노드 수의 총합은 그 이전 level까지의 모든 노드의 수의 총합 + 1이다. 바꿔말하면, 마지막 level에 전체 노드의 절반이 있다는 의미이다.
3. O(log N)
Level 0: 2^0; // 1개의 노드
Level 1 : 2^1; // 2개의 노드
Level 2 : 2^2; // 4개의 노드
Level 3 : 2^3; // 8개의 노드위처럼 perfect binary tree의 경우 각 level의 노드의 수를 아는 방법은 '2^(h-1)'(h는 height, 즉 레벨을 의미한다) 인데, 따라서 노드 수에 로그를 씌우면 몇번째 level인지 알 수 있다.
O(log N)은 모든 노드를 다 iterating 하면서 살펴보는 것이 아니라, 특정 조건에 의거하여 왼쪽 또는 오른쪽을 선택해서 level을 내려가는 것을 반복하는, Divide and Conquer의 개념이다. 전화번호부를 살펴보는 것과 유사하다. 처음부터 끝까지 다 보는 것이 아니라, 알파벳에 의거하여 특정 알파벳으로 간 후, 거기서 또 조건에 의거하여 찾아보게 된다.
이 방식으로 접근할 경우 시간 복잡도는 O(log N)이 되며, O(log N)은 O(n), Linear Time보다도 더 빠르다. Trees 자료구조에서 O(log N) 시간복잡도가 가능한 가장 대표적인 사례가 바로 Binary Search Trees이다.
4. Binary Search Tree
특정 값을 찾을 때 아주 유용한 자료구조인 Binary Search Tree이다. 이 자료구조가 Hash Table보다 더 나은 이유는 무엇일까?
해쉬 테이블은 데이터 간의 관계가 존재하지 않는다. 단지 키와 밸류만 존재할 뿐이다. 그러나 Binary Search Tree는 노드들 간의 관계에 의거하여 자료가 분류되어 있다. (컴퓨터의 폴더와 같이 생각하면 좋다. 하나의 폴더 아래에 특정 기준으로 분류된 서브 폴더가 존재하고, 각 서브폴더 또한 다른 서브폴더를 포함하고 있다.)
# Binary Search Tree의 규칙
1. 현재 노드의 오른쪽에 있는 노드는 반드시 현재 노드보다 큰 값을 가지고 있다. 반대로 왼쪽에 있는 노드는 현재 노드보다 작은 값이다.
2. 각 노드는 최대 2개의 노드만 가질 수 있다.(Binary)
- 장점 : searching, lookup에 아주 빠르다. 예를 들어 37이란 숫자를 찾고자 할 경우, 37이 root보다 작으므로 왼쪽으로 가고, 33보단 크므로 오른쪽으로 가게 되는데, 이 방식을 취함으로써 모든 노드를 iterating 하지 않고도 특정 값을 빠르게 찾을 수 있다. 배열에서 찾는다고 생각해보면, 모든 요소를 iterating하기 때문에 worst 케이스에서 O(n)이 될 수 밖에 없다.
insert와 delete의 경우, 마찬가지로 현재 노드보다 큰지 작은지를 기반으로 삭제/추가 해야 하는 값의 위치로 이동하게 된다. 그런데 만약 위 그림에서 105를 지우면, 이 자리를 대체할 값을 찾아야 하고 144가 105의 자리를 대체하게 된다. 만약 노드의 level이 아주 깊다고 할 경우에는 하단의 모든 level의 값을 하나씩 위로 올려야 하기 때문에 해쉬 테이블에서 값을 삭제할 때의 시간복잡도 O(1)보다 느릴 수 밖에 없다.
5. Balanced vs. Unbalanced BST
만약 현재 노드보다 큰 값만 계속 추가하게 될 경우에는 위 사진처럼 오른쪽으로만 치우진 불균형한 Binary Search Tree가 된다.이 경우에는 searching이나 lookup도 모든 요소를 iterating하는 배열과 다를 바가 없으므로 O(n)이 된다. 따라서 Binary Search Tree는 균형을 맞추는 것이 중요하다.
# Trees 메소드 구현
class Node {
constructor(value){
this.left = null;
this.right = null;
this.value = value;
}
}
class BinarySearchTree {
constructor(){
this.root = null;
}
insert(value){
const newNode = new Node(value);
if (this.root === null) {
this.root = newNode;
} else {
let currentNode = this.root;
while(true){
if(value < currentNode.value){
//Left
if(!currentNode.left){
currentNode.left = newNode;
return this;
}
currentNode = currentNode.left;
} else {
//Right
if(!currentNode.right){
currentNode.right = newNode;
return this;
}
currentNode = currentNode.right;
}
}
}
}
lookup(value){
if (!this.root) {
return false;
}
let currentNode = this.root;
while(currentNode){
if(value < currentNode.value){
currentNode = currentNode.left;
} else if(value > currentNode.value){
currentNode = currentNode.right;
} else if (currentNode.value === value) {
return currentNode;
}
}
return null
}
remove(value) {
if (!this.root) {
return false;
}
let currentNode = this.root;
let parentNode = null;
while(currentNode){
if(value < currentNode.value){
parentNode = currentNode;
currentNode = currentNode.left;
} else if(value > currentNode.value){
parentNode = currentNode;
currentNode = currentNode.right;
} else if (currentNode.value === value) {
//We have a match, get to work!
//Option 1: No right child:
if (currentNode.right === null) {
if (parentNode === null) {
this.root = currentNode.left;
} else {
//if parent > current value, make current left child a child of parent
if(currentNode.value < parentNode.value) {
parentNode.left = currentNode.left;
//if parent < current value, make left child a right child of parent
} else if(currentNode.value > parentNode.value) {
parentNode.right = currentNode.left;
}
}
//Option 2: Right child which doesnt have a left child
} else if (currentNode.right.left === null) {
currentNode.right.left = currentNode.left;
if(parentNode === null) {
this.root = currentNode.right;
} else {
//if parent > current, make right child of the left the parent
if(currentNode.value < parentNode.value) {
parentNode.left = currentNode.right;
//if parent < current, make right child a right child of the parent
} else if (currentNode.value > parentNode.value) {
parentNode.right = currentNode.right;
}
}
//Option 3: Right child that has a left child
} else {
//find the Right child's left most child
let leftmost = currentNode.right.left;
let leftmostParent = currentNode.right;
while(leftmost.left !== null) {
leftmostParent = leftmost;
leftmost = leftmost.left;
}
//Parent's left subtree is now leftmost's right subtree
leftmostParent.left = leftmost.right;
leftmost.left = currentNode.left;
leftmost.right = currentNode.right;
if(parentNode === null) {
this.root = leftmost;
} else {
if(currentNode.value < parentNode.value) {
parentNode.left = leftmost;
} else if(currentNode.value > parentNode.value) {
parentNode.right = leftmost;
}
}
}
return true;
}
}
}
}
const tree = new BinarySearchTree();
tree.insert(9)
tree.insert(4)
tree.insert(6)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)
tree.remove(170)
JSON.stringify(traverse(tree.root))
// 9
// 4 20
//1 6 15 170
function traverse(node) {
const tree = { value: node.value };
tree.left = node.left === null ? null : traverse(node.left);
tree.right = node.right === null ? null : traverse(node.right);
return tree;
}
# AVL Trees + Red Black Trees
AVL Trees와 Red Black Trees는 균형이 맞지 않는 트리의 균형을 맞춰주는 알고리즘이 반영되어 있는 트리 구조이다. 대부분 라이브러리를 이용하기 때문에 구체적인 로직보다는, 왜 균형을 맞추는 작업이 필요한지를 이해하는 것이 중요하다.
AVL Trees 관련 링크1, AVL Trees 관련 링크2
Red Black Trees 관련 링크1, Red Black Trees 관련 링크2
6. Binary Heap
Binary Heap은 Tree의 종류 중 하나이다. 특징은 상위 layer에서 아래로 내려갈 수록 값이 작아진다는 특징이 있다. 위쪽이 크면 max heap, 위쪽이 최소값이믄 min heap이다. 이 경우 왼쪽이 작고 오른쪽이 큰 것이 아니기 때문에 어떤 기준에 의거해서 divide and conquer가 불가능하다. 따라서 Binary Heap의 경우 lookup은 O(n)이 된다.
하지만 Binary Heap은 Compartive Opeartion을 할 때 아주 유용하다. 예를 들어 33보다 큰 값을 찾길 원할 때 아주 쉽게 값을 찾을 수 있다. 값을 추가할 때에는 왼쪽에서 오른쪽으로 비어있는 곳에 그냥 순서대로 넣기 때문에 메모리 효율성이 높고 언제나 꽉 찬 binary tree가 된다. 하지만 값의 크기에 따라서 level 변환이 일어나기 때문에 O(log n)이 된다.
7. Priority Queue
Binary Heap은 Priority Queue 같은 곳에서 아주 유용하게 사용된다. Priority Queue는 모든 element가 priority, 우선순위를 가지고 있는 형태이다. 특정 element는 다른 element보다 높은 우선순위를 가지고 있으며, 우선순위가 높을수록 먼저 out되게 된다. 놀이동산에서 줄 서서 기다리는데 비싼 티켓을 구매한 프리패스 고객이 먼저 들어가서 롤러코스터를 타는 것이다.
이렇게 우선순위를 가진 이들이 바로 더 높은 value를 가진 노드가 되며, 이들은 Binary Heap에서 value가 높을수록 상위에 위치하므로 priority queue의 우선순위에 의거해서 위쪽 level로 옮겨가게 된다.
# Binary Heap 결론
- 장점 : Better than O(n), Priority, Flexible Size, Fast Insert
- 단점 : Slow lookup
대부분 바이너리 힙은 최댓값을 찾거나 최솟값을 찾는 경우에 사용되면 좋다. O(1)이기 때문이다.
8. Trie
Trie는 element가 text인 경우에 searching 작업을 수행할 때 주로 쓰이는 트리 자료구조의 한 종류이다. 주로 시작 root는 비어 있고, 아래 자식 노드에 다양한 텍스트가 들어가있다.
Trie는 만약 K로 시작하는 값을 찾을 경우, 다른 모든 노드에 접근할 필요 없이 K노드만 찾아서 아래로 내려가면 된다. 그렇기 때문에 사전 또는 검색어 자동완성 같은 알고리즘에 사용되는 자료구조이다. K를 입력하는 순간 Katze가 자동으로 완성되는 것이다.
그렇기 때문에 Trie 구조에서 searching을 할 경우, 찾고자 하는 단어의 길이만 알면 되기 때문에 O(length of word)가 된다. 속도도 빠르고 메모리 공간도 효율적이다. 왜냐하면 상위 부모 노드가 prefix가 되기 때문이다. 예를 들어 B의 경우 Bauer와 Baum이라는 단어가 아래에 존재하는데, B가 두 개의 단어에 존재하지만 부모 노드 하나만 B를 가짐으로써 B를 여러 메모리 공간에 저장하지 않고 한 곳에만 저장할 수 있다.
'Javascript 공부 > Data Structure + Algorithms(-)' 카테고리의 다른 글
| 자바스크립트 알고리즘 : 재귀함수란? (0) | 2019.11.01 |
|---|---|
| 자바스크립트의 자료구조 6 : 그래프(Graphs) (1) | 2019.11.01 |
| 자바스크립트의 자료구조 4 : 스택(Stack), 큐(Queue) (0) | 2019.10.08 |
| 자바스크립트의 자료구조 3 : 연결 리스트(Linked List) (0) | 2019.10.08 |
| 자바스크립트의 자료구조 2 : 해쉬 테이블(Hash Table) (0) | 2019.10.08 |
댓글