keicoon15

트리 ( tree ) 는 부모와 자식간의 관계로 이뤄진 구조이다. 여기서 이진 트리 ( binary tree ) 는 이진 ( 2 ) 개의 자식으로 이뤄진 트리 구조이며, 왼쪽의 자식 ( child ) 는 왼쪽 부분 트리 ( left subtree ), 오른쪽 부분 트리 ( right subtree ) 로 부른다. 정의 ( definition ) 을 보면 아래와 같다. 순서가능집합 ( ordered set ) 에 속한 구성 ( item ) 으로 구성된 이진 트리이며 아래 조건을 만족해야 한다. 각 마디는 하나의 키만 가지고 있다 여기서 키는 노드가 대표하는 값 ( id ) 이다 주어진 마디의 왼쪽 부분트리에 있는 키는 그 마디 ( 부모 ) 의 키보다 작거나 같다 주어진 마디의 오른쪽 부분트리에 있는 키는 ..

이분검색 ( Binary Search ) Time : O ( logN ) Space : O ( n ) 탐색을 요구하는 대상은 정렬이 필요하다 ( "오름차순" 이 아니여도 상관없다. 방향에 따른 pivot 위치만 바꾸면 된다 ) ( 정렬은 다른 포스팅에서 다루기로 한다 ) 정렬된 대상의 중간 값으로 찾는 값의 크고 작음을 이분하여 다음 순서에 탐색하는 공간을 반씩 줄여간다. 전체 공간을 반씩 줄여가기 때문에 탐색 공간이 log(2) 로 줄어든다. 탐색 공간이 더 이상 없으면 ( low > high ) 탐색에 실패한다. function search(arr, x) { const length = arr.length; let low = 0; let high = length; let mid; let idx = 0;..

순차검색 ( Sequential Search ) Time : O ( n ) Space : O ( n ) Iterator 를 순회하며 Index 를 증가시킨다. 순회 도중에 값과 일치하는 Value 의 Index 를 찾는다. function search(arr, x) { let idx = 0; // result const length = arr.length; while (idx < length && arr[idx] != x) { idx += 1; } // fail to find. if (idx == length) { return -1; } // success return idx; }