💻 자료구조와 알고리즘
트리 순회
배열을 순회하는 것은 간단하다. 인덱스를 사용해 트리를 접근한 다음 인덱스가 크기 제한에 도달할 때까지 인덱스를 증가한다. 트리의 경우 트리의 모든 항목을 방문하기 위해 왼쪽 포인터와 오른쪽 포인터가 존재한다. 물론 순회를 위한 다양한 방법이 존재한다. 가장 널리 사용되는 순회 기법으로 선순위 순회(pre-order), 중순위 순회(in-order), 후순위 순회(post-order), 단계 순위 순회(level-order)가 있다.
이진 탐색
이진 탐색 트리
왼쪽과 오른쪽에 두 개의 자식이 있다. 왼쪽 자식이 부모보다 작고 오른쪽 자식이 부모보다 크다. 이유는 검색과 삽입, 특정 값을 지닌 노드 제거의 시간 복잡도가 O(log2(n))이기 때문.이진 탐색 트리는 루트 노드(가장 상위 노드)가 있다. 루트 노드는 최초에 null로 초기화 된다.(다른 항목이 삽입되기 전)
-
삽입
이진 검색 트리에 노드를 삽입하는 것은 두 단계로 구성된다. 첫째 루트가 빈 경우 루트가 신규 노드가 된다. 루트가 비어 있지 않다면 while 루프를 사용해 조건이 만족될 때까지 이진 검색 트리를 순회한다. 각 루프 반복 시 신규 노드가 현재 루트보다 크거나 작은지 확인한다.
- 시간 복잡도(균형 트리): O(log2(n))
- 시간 복잡도(불균형 트리): O(n)
-
삭제
우선 삭제하고자 하는 값을 지닌 노드를 찾기 위해 트리를 순회한다. 노드를 찾은 경우 세 가지의 경우가 있다.
- 노드에 자식이 없다 : 가장 간단한 경우. 노드에 자식이 없는 경우 null을 반환한다.
- 노드에 자식이 하나 있다 : 노드에 자식이 하나 있는 경우 현재 자식을 반환한다. 해당 자식이 위 단계로 올라가 부모를 대체한다.
- 노드에 자식이 두 개 있다 : 노드에 자식이 두 개 있는 경우 왼쪽 하위 트리의 최대치를 찾거나 오른쪽 하위 트리의 최소치를 찾아서 해당 노드를 대체한다.
- 시간 복잡도(균형 트리): O(log2(n))
- 시간 복잡도(불균형 트리): O(n)
-
검색
이진 검색 트리의 경우 노드의 왼쪽 자식이 부모보다 항상 작고 오른쪽 자식이 부모보다 항상 크다는 특성을 사용해 검색을 수행할 수 있다. 현재 루트가 검색 값보다 작거나 큰지 확인함으로써 트리를 순회할 수 있다. 현재 루트가 검색 값보다 작은 경우 오른쪽 자식을 방문한다. 현재 루트가 검색 값보다 큰 경우 왼쪽 자식을 방문한다.
트라이
트라이는 탐색과 삽입을 지원하는 노드로 구성된 트리이다. 탐색은 키 문자열과 연관된 값을 반환하고, 삽입은 문자열(키)과 그 값을 삽입한다. 키의 길이가 n일때 탐색과 삽입 모두 O(n) 시간에 수행된다.
자동완성에 대한 구현 참고 : 링크
트리를 이용하여 전위 순회, 중위 순회, 하위 순회 구현
/*
트리 예시
1
/ \
2 3
/ \ / \
4 5 6 7
*/
class Node {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
class Tree {
constructor(node) {
this.root = node;
this.PreOrderResult = [];
this.InOrderResult = [];
this.PostOrderResult = [];
}
PreOrder(node) {
if (!node) {
return;
} else {
this.PreOrderResult.push(node.val);
this.PreOrder(node.left);
this.PreOrder(node.right);
return this.PreOrderResult;
}
}
InOrder(node) {
if (!node) {
return;
} else {
this.InOrder(node.left);
this.InOrderResult.push(node.val);
this.InOrder(node.right);
return this.InOrderResult;
}
}
PostOrder(node) {
if (!node) {
return;
} else {
this.PostOrder(node.left);
this.PostOrder(node.right);
this.PostOrderResult.push(node.val);
return this.PostOrderResult;
}
}
}
const MyTree = new Tree(new Node(1));
MyTree.root.left = new Node(2);
MyTree.root.right = new Node(3);
MyTree.root.left.left = new Node(4);
MyTree.root.left.right = new Node(5);
MyTree.root.right.left = new Node(6);
MyTree.root.right.right = new Node(7);
console.log("전위 순회 결과값 :", MyTree.PreOrder(MyTree.root));
console.log("중위 순회 결과값 :", MyTree.InOrder(MyTree.root));
console.log("후위 순회 결과값 :", MyTree.PostOrder(MyTree.root));트라이를 이용하여 자동 완성 코드 구현
class Node {
constructor(val = ''){
this.val = val;
this.end = false;
this.child = {};
}
}
class Trie {
constructor(){
this.root = new Node();
}
Insert(str){
let CurrentNode = this.root;
for(let i = 0; i <str.length ; i++) {
const CurrentChar = str[i];
if(CurrentNode.child[CurrentChar] === undefined) {
CurrentNode.child[CurrentChar] = new Node(CurrentNode.val + CurrentChar);
}
CurrentNode = CurrentNode.child[CurrentChar];
}
CurrentNode.end = true
}
Search(str) {
let CurrentNode = this.root;
for(let i = 0; i <str.length ; i++) {
const CurrentChar = str[i];
if(CurrentNode.child[CurrentChar]) {
CurrentNode = CurrentNode.child[CurrentChar];
} else {
return '';
}
}
return CurrentNode.val;
}
}
const MyTrie = new Trie();
MyTrie.Insert("hel");
MyTrie.Insert("hell");
MyTrie.Insert("hello");
MyTrie.Insert("wor");
MyTrie.Insert("world");
console.log("찾기 :", MyTrie.Search("hell"));
console.log("찾기 :", MyTrie.Search("hello"));
console.log("찾기 :", MyTrie.Search("hep"));
console.log("찾기 :", MyTrie.Search("help"));
console.log("찾기 :", MyTrie.Search("helloworld"));Trie 자동 완성 코드 참고 : 링크
회고🥲
오늘은 자료구조와 알고리즘 중심으로 공부를 하였고 트리, 트라이로 구현을 했다.
트라이는 거의 보고 베낀 수준...다른 알고리즘보다 재밌다고 느껴지는데 트리 종류도 많고 순회 방식, 이진 탐색 트리 이해가 가서 그런지 확실히 재밌었다. 트라이에 대해서는 아직 이해도가 부족하고 다시한번 정리 해볼 생각이다. 누워서 읽는 알고리즘 책은 사실 주말동안 읽어보려 했으나 약속이 있어서 제대로 읽어보지 못했다😓 조만간 읽어서 후기를 제대로 남겨야겠다. 내일은 모던 자바스크립트와 자료구조 공부를 할 생각이다.
