최솟값/최댓값 찾기 (min(), max()) 이진탐색트리에서 최솟값은 맨 왼쪽 노드값이고, 최댓값은 맨 오른쪽 노드값이다. 그러므로 최솟값을 구하는 메소드 min(), 최댓값을 구하는 메소드 max()는 다음과 같이 구현할 수 있다. //최솟값 찾기 min(){ return this.minNode(this.root); } minNode(node){ if(node){ while(node && node.left !== null){ node = node.left; } return node.key; } return null; } //최댓값 찾기 max(){ return this.maxNode(this.root); } maxNode(node){ if(node){ while(node && node.right !=..

중위순회(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일 때 전체 간선의 개수는..

[해시] 완주하지 못한 선수 문제 출처: 프로그래머스(programmers.co.kr/learn/courses/30/lessons/42576?language=javascript) 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 2..