Disjoint Set 서로소 집합 처리 - 교집합이 공집합인(=서로소인) 다수의 집합들을 처리하는 자료구조이다. - 집합을 만들고, 특정 원소가 속한 집합을 찾아내고, 두 집합을 합치는 연산을 지원한다. - 서로소 집합을 처리하는 데는 Linked List 혹은 Tree로 구현하여 추상화한다. Operations (연산) - 집합을 만들고, 특정 원소가 속한 집합을 찾아내고, 두 집합을 합치는 연산을 지원한다. - 교집합이 없으므로, 교집합 연산 및 차집합 연산은 지원할 필요가 없다. Make-Set(x) - 원소 x로 구성된 집합을 만든다. Find-Set(x) - 원소 x가 포함된 집합의 Representative(대표원소)를 리턴한다. Union(x, y) - 원소 x를 가진 집합과 원소 y를 가..
Grid File 그리드 파일 - Key의 내용으로 Record가 저장된 곳을 "단번에" 알아낼 수 있도록 한 Multi-Dimensional Store/Search 자료구조이다. - Key가 곧, Record의 저장 위치값이기 때문에, Grid File구조에서는 범위 검색이 가능하다. - 대표적인 자료구조 중 하나인 Hash Table (URL)은 저장 위치를 Hashing하여 Key로 산출해내는 구조이다. (즉, 그리드 파일과 달리, 해시 테이블에서는 저장 위치를 "변형"하여 Key로 만든다.) Mechanism (원리) - 메모리 공간을 배타적인 Grid(격자) 영역으로 나눈 다음, 해당 영역에 속하는 Record를 한 Page에 모아서 저장한다. - 즉, 임의의 레코드들에 특정 좌표값(=Key)이..
R-Tree (Rectangle-Tree) R-트리 (Rectangle-트리) * 검색 트리의 종류 (URL) - KDB-Tree와 같이, R-Tree도 B-Tree에서 다차원 검색이 가능하게끔 확장시켜 놓은 형태의 자료구조이다. Mechanism (원리) - 공간을 MBR(Minumum Bounding Rectangle; 최소 경계 사각형)로 분할하여 저장한다. - MBR끼리는 겹칠 수 있고, 상위 레벨의 MBR은 하위 레벨의 MBR을 포함하는 Hierarchical Tree Structure이다. Properties of B-Tree (B-Tree의 성질) 1. B-Tree에서 Root를 제외한, 모든 노드는 \(\lfloor {k \over 2} \rfloor\)개에서 \(k\)개 사이의 Key들을..
KDB-Tree (\(k\)-Dimensional B-Tree) KDB-트리 (\(k\)-차원 B-Tree) * 검색 트리의 종류 (URL) Mechanism (원리) - KDB-Tree에서는 B-Tree와 같이, 한 노드의 크기가 디스크의 한 Page를 담을 수 있을 만큼으로 구성된다. - 기본적으로, KDB-Tree 또한 B-Tree이기 때문에, 모든 Leaf Node들의 Level은 같다. Node Structure (노드 구조) 1) 영역 노드 (Region Page) - 복수 개의 (영역, 페이지 번호) Pair로 구성된다. (영역 값은 서로 겹치치 않는다.) - 영역 노드에서의 페이지 번호란, 자식 노드가 위치한 페이지 번호를 의미한다. - KDB-Tree의 모든 Internal Node는 영..
KD-Tree (\(k\)-Dimensional Tree) KD-트리 (\(k\)-차원 트리) * 검색 트리의 종류 (URL) - KD-Tree는 Binary Search Tree를 확장한 개념으로, \(k\)개(\(k \geq 2\))의 Field로 이루어진 Key를 연산에 사용한다. Mechanism (원리) Branch on KD-Tree - KD-Tree에서 분기는 Level=0인 Node(=Root Node)는 첫 번째 Field를 이용해 분기하고, Level=1인 Node는 두 번째 Field를, Level=2인 Node는 세 번째 Field를 이용해 분기하는 방식으로 이루어진다. (즉, 동일한 Level에 있는 Node들은 같은 순서에 있는 Field를 이용해 분기한다.) ※ KD-Tree에..
B-Tree B-트리 * 검색 트리의 종류 (URL) - Balanced-Tree의 약자로, 디스크 환경에서 사용하기 적합한 Balnced-외부 다진 검색 트리이다. - Child의 수를 늘리고, Balance를 유지하여 Tree의 Depth를 줄여 검색시간을 줄이는 것을 목표로 한 구조이다. - 일반적으로, B-Tree의 Node 하나의 크기를 Disk Block 크기와 일치시켜서 CPU가 Disk에 접근하는 I/O Access 횟수를 최소화한다. (컴퓨터는 Disk의 특정 데이터에 접근할 때, Disk내에서 특정 데이터가 위치한 Disk Block 전체를 Loading한다.) (I/O Access는 CPU의 입장에서 매우 큰 시간이 소요되는 Task이다.) * Memory Management (URL..
Boyer-Moore Algorithm 보이어-무어 알고리즘 * String Matching Algorithms (문자열 매칭 알고리즘) (URL) - 전체 문자열 \(\texttt{string[1...m]}\)에서 부분 문자열 \(\texttt{pattern[1...m]}\)을 찾아내는데, 최악의 경우에는, \(\Theta(n*m)\) 시간 동안 수행되지만, 평균적으로 \(\Theta(n)\)과 \(\Theta({n \over m})\) 사이의 시간 동안 수행되어 실무에서 KMP Algorithm보다 더 자주 쓰이는 알고리즘이다. (대체로, \(\Theta({n \over m})\)에 더 가까운 성능을 보인다고 한다.) Mechanism (원리) - Mismatching이 발생했을 때, Bad-Char..
