중위순회(in-order traversal) : (왼쪽 - 루트 - 오른쪽) 오름차순(작은 값에서 큰 값 순)으로 방문된다. 트리 정렬 시 사용되는 방법임 전위순회(pre-order traversal) : (루트 - 왼쪽 - 오른쪽) 자식 노드보다 노드 자신을 먼저 방문한다. 구조화된 문서를 출력할 때 많이 이용하는 방법 후위순회(post-order traversal) : (왼쪽 - 오른쪽 - 루트) 자식 노드를 노드 자신보다 먼저 방문 디렉토리와 서브 디렉토리의 파일 용량을 계산할 때 쓰는 방법 //in-order traversal 중위순회 (왼쪽 - 루트 - 오른쪽) inOrderTraverse(callback){ this.inOrderTraverseNode(this.root, callback); }..

기본 뼈대 작성 class Node{ constructor(key){ this.key = key; this.left = null; this.right = null; } } class BinarySearchTree{ constuctor(){ this.root = null; } } 우선 이진탐색트리 안에 들어가는 노드는 key, left, right로 구성된다. 이진탐색트리 안에는 루트노드가 있다. insert 메소드 class Node{ constructor(key){ this.key = key; this.left = null; this.right = null; } } class BinarySearchTree{ constuctor(){ this.root = null; } insert(key){ let ne..

이진 탐색 트리(Binary Search Tree) 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조 이진 탐색 트리의 특징 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 부모 노드보다 왼쪽 자식 노드가 작다 부모 노드보다 오른쪽 자식 노드가 크다 이진 탐색 트리의 데이터 조회 찾고자 하는 원소 : 37 [Step 1] 루트 노드부터 방문하여 탐색을 진행한다 현재 노드와 찾는 원소 37을 비교 찾는 원소가 더 크기 때문에 오른쪽 방문 [Step 2] 현재 노드와 값을 비교한다 현재 노드와 찾는 원소 37을 비교 찾는 원소가 더 작기 때문에 왼쪽 방문 [Step 3] 현재 노드와 값을 비교 현재 노드와 찾는 원소 37을 비교 원소를 찾았으므로 탐색을 종료 이처럼, 이진 탐색 트리를..

지금까지는 주로 순차적 자료구조를 살펴봤었음(비순차적 자료 구조는 해시 테이블이 유일함) 트리는 비순차적 자료구조 트리 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 트리 용어 루트 노드(root node) : 부모가 없는 최상위 노드 A 단말 노드(leaf node) : 자식이 없는 노드 K, L, F, G, M, I, J 크기(size) : 트리에 포함된 모든 노드의 개수 13 깊이(depth) : 루트 노드부터의 거리 A노드의 깊이: 0 B,C,D 노드의 깊이 : 1 E,F,G,H,I,J노드의 깊이 : 2 K,L,M 노드의 깊이 : 3 높이(height) : 깊이 중 최댓값 3 차수(degree) : 각 노드의 (자식 방향) 간선 개수 12 기본적으로 트리의 크기가 N일 때 전체 간선의 개수는..

🎈선형탐색법(linear probing) 새 원소 추가 시 인덱스가 이미 점유된 상태라면 인덱스+1 을 찾아보고, 인덱스+1도 점유됐다면 인덱스+2를 찾아보는 식으로 충돌을 회피하는 방법 🎀 앞서 기본적인 해시테이블을 구현할 때와 chaining으로 충돌을 해결했을 때에는 기본적으로 해시테이블의 constructor에서 테이블(배열)의 사이즈를 storageLimit으로 지정해놓았었는데, 선형탐색법 방법에서는 제한을 두지 않을 것이다. 🎁 다른 프로그래밍 언어에서는 배열의 크기를 미리 정하게 되어 있는데, 선형 탐색법에서 한 가지 신경쓰이는 부분이 배열 인덱스가 가능한 범위를 벗어났을 경우이다. 자바스크립트에서는 배열을 따로 크기를 지정해놓지 않아도 원소를 추가하면 자동으로 크기가 늘어나므로 전혀 고민할..

class ValuePair{ constructor(key,value){ this.key = key; this.value = value; } } class HashTable{ constructor(){ this.storageLimit = 10; this.table = new Array(this.storageLimit); } Hash(key){ let hash = 0; for(let i = 0; i < key.length; i++){ hash += key.charCodeAt(i); } return hash % this.storageLimit; } add(key,value){ const index = this.Hash(key); if(this.table[index] === undefined){ this.ta..