분류 전체보기

R-Tree - B-트리의 다차원 확장 - 균형잡힌 검색트리 - 모든 레코드는 리프 노드에서만 가리킴 - 다차원 도형의 저장 가능 - 기본적으로, KDB-Tree와 노드 구조를 같이 한다. 삽입 연산 1. 노드가 삽입될 위치를 찾은 후, 값을 해당 노드에 삽입한다. 2-1 삽입 이후에 OverFlow가 발생하지 않았으면 삽입에 성공 2-2 삽입 이후에 overflow가 발생한 노드가 있다면 재분배 시도 2-3 삽입 이후에 overflow가 발생한 노드가 있는데 재분배가 안되는 경우 노드를 분할한다.

KDB-Tree KD-Tree와 B-Tree의 특성 결합 KD-Tree의 특성 다차원 key B-Tree의 특성 디스크의 한 페이지가 한 노드와 일치 Balanced tree : 모든 리프노드들의 레벨이 같다. 각 레코드는 k차원 공간에서 하나의 점에 해당한다. Internal node하나는 k차원 공간에서 한 영역을 담당한다. 루트노드는 k차원 공간 전체를 커버하고 이하의 노드들은 k차원 공간의 부분영역을 담당한다. 같은 level에 있는 모든 노드들은 서로 겹치는 영역이 없다 같은 level에 있는 모든 노드들의 담당 영역을 합하면 k차원 공간 전체가 된다. 리프노드는 데이터 페이지 정보를 저장한다. 영역노드 - 복수개의 (영역, 페이지 번호) pair로 구성된다. - 영역노드에서의 페이지 번호란, ..

KD-트리 - 각 레벨에서 필드를 번갈아 가며 검색에 사용한다. - 한 레벨에서는 하나의 필드만 사용한다. - 총 k개의 필드를 사요하는 검색이라면, k개의 레벨을 내려가면 검색에 사용하는 필드가 일치한다. - h-1번째에서 마지막 필드로 분기했다면 h에서는 다시 첫번째 필드로 사용 - 2차원 KD-Tree 1레벨 : x축 비교 -> 2레벨 : y축 비교 -> 3레벨 : x축 비교 -> 4레벨 : y축 비교 ... - 만약 [10|60] 노드를 검색 하고자 한다면 다음과 같은 순서가 된다. (1) 1레벨 x축(50)보다 작으므로(10) A의 왼쪽 자식으로 내려간다. (2) 2레벨 y축(70)보다 작으므로(60) B의 왼쪽 자식으로 내려간다. (3) 3레벨 x축(25)보다 작으므로(10) D의 왼쪽 자식으..

B-트리 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. ✅사용 디스크의 접근 단위는 블록(페이지) (블럭단위로 파일을 입출력한다.) 디스크에 한 번 접근하는 시간은 수십만 명령어의 처리시간과 맞먹는다. B-Tree도 자식 노드를 접근할 때는 참조 포인터로 접근을 하지만, 하나의 노드가 가지는 데이터 개수가 많아질수록 포인터 개수는 확연히 줄어 들고, 트리 내에서 다루는 데이터가 많아질수록 이러한 차이는 커진다. 검색트리가 디스크에 저장되어 있다면 트리의 높이를 최소화하는 것이 유리하다. B-트리는 다진검색트리가 균형을 유지하도록 하여 최악의 경우 디스크 접근 횟수를 줄인 것이다. ✅구조 k차 트리일 때,루트를 제외한 모든 노드는 [k/2] ~ k개의 키..

레드 블랙 트리(Red Black Tree) 자가균형이진탐색트리(AVL 트리)로서, 대표적으로는 연관 배열 등을 구현하는데 쓰이는 자료구조이다. (AVL트리는 레드-블랙 트리보다 더 엄격하게 균형이 잡혀있기 때문에, 삽입과 삭제를 할 때 최악의 경우에는 더 많은 회전이 필요하다.) - 최악의 경우에도 O(log n)의 시간 복잡도로 삽입/삭제/검색 가능 - 루트노드보다 가장 먼 리프노드까지의 거리가 가장 가까운 노드 경로까지의 거리의 두배보다 항상 작다는 특성 때문에 성립한다. 0. 삽입되는 노드의 색깔은 무조건 레드이다 1.루트는 블랙이다 2. 모든 리프노드(단말)은 블랙이다 (여기서 리프노드는 일반적인 의미의 리프노드와 다르다. 모든 NIL포인터가 NIL이라는 리프노드를 가리킨다고 가정한다.) 3. ..

자가균형이진탐색트리(AVL트리) 각 노드에서 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1이하인 이진 탐색 트리를 말한다. 이진 탐색 트리의 한 종류로서 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조이다. 높이 차이가 1보다 커지면 회전을 통해 균형을 맞춰 높이 차이를 줄인다. - 정렬된 데이터를 트리로 만든 경우, 탐색에 필요한 시간은 O(n), 최악의 경우에도 O(log n)에 탐색할 수 있도록 만든 트리이다. - 삽입/검색/삭제의 시간 복잡도는 O(log n) Balance Factor (BF, 균형 인수) : AVL 트리가 균형이 무너졌는지를 판단할 때 사용 BF(k) = k의 왼쪽 서브트리의 높이 - k의 오른쪽 서브트리의 높이 AVL트리는 모든 노드의 BF가 -1,0,1 ..

이진 검색 트리 이진 탐색 : 배열 기반의 탐색을 위한 자료구조 이진 탐색 트리 : 이진 트리 기반의 탐색을 위한 자료 구조 ✔️정의 모든 원소의 키는 유일한 키를 가진다. 왼쪽 서브 트리 키들은 루트키보다 작고, 오른쪽 서브 트리 키들은 루트키보다 크다. 각 노드는 최대 두개의 자식 노드를 가진다. ✔️탐색 연산 순환적인 방식(재귀적인 관점) 비교한 결과가 같으면 탐색이 성공적으로 끝난다. 비교한 결과가 주어진 키 값이 루트 노드의 키값보다 작으면 탐색은 이 루트 노드의 왼쪽 자식을 기준으로 다시 시작한다. 비교한 결과가, 주어진 키 값이 루트 노드의 키값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작한다. treeSearch(t,x) //t:트리 노드 //x:검색하고자 하는 키 {..

검색트리(Search Tree) 검색(search)는 컴퓨터가 가장 많이 하는 작업 중의 하나이다. 검색은 기본적으로 여러 개의 자료 중에서 원하는 자료를 찾는 작업이다. 검색을 위하여 사용되는 자료 구조는 배열, 연결리스트, 트리, 그래프 등 매우 다양할 수 있다. 레코드(record) 개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위 EX) 사람의 레코드 : 주민번호, 이름, 집주조, 집 전화번호, 휴대폰 번호, 최종 학력, 연소득 등의 정보 필드(field) 레코드에서 각각의 정보를 나타내는 부분 EX) 위 사람의 레코드에서 각각의 정보를 나타내는 부분 검색키(search key 또는 key) 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드 키는 하나의 필드로 이루어질 수도 ..