알고리즘
-
알고리즘...63일지 2021. 10. 6. 10:17
B 트리 검색 구현 다진 검색 트리인 B 트리의 검색을 구현한다. BTree::Exists /// /// B 트리를 확인하여 주어진 값이 트리에 존재하는지 여부를 반환한다. /// /// 확인할 값 /// 존재 여부 bool BTree::Exists(int data) { BTreeNode* node{ _root }; while (node != nullptr) { for (int i = 0; i keys[i].value == data) { return true; } if (data keys[i].value) { node = node->keys[i].left; break; } if (node->keys[i].val..
-
알고리즘...62일지 2021. 10. 5. 16:54
B 트리의 노드 관리를 위한 매니저 클래스 이전 트리의 구현과 마찬가지로 노드 관리를 위한 매니저 클래스를 구현한다. BTreeNode struct BTreeNode; /// /// B 트리의 노드에서 사용할 키 /// struct BTreeNodeKey { BTreeNodeKey() : left(nullptr), value(0), right(nullptr) {} void Clear() { left = nullptr; value = 0; right = nullptr; } BTreeNode* left; int value; BTreeNode* right; }; /// /// B 트리에 사용할 노드 /// struct BTreeNode { static const size_t TotalKeyCount{ 4 };..
-
알고리즘...61일지 2021. 10. 3. 14:49
B 트리 구현을 위한 노드 구조 확인 일단 하드웨어에 맞추지 않고 적당한 크기로 만들어 구조와 동작을 확인하고자 한다. 키를 4개를 가지고 자식 링크를 5개, 부모 링크를 1개 가지는 노드를 구성하자. BTreeNode struct BTreeNode { BTreeNode* parent; BTreeNode* child0; int key1; BTreeNode* child1; int key2; BTreeNode* child2; int key3; BTreeNode* child3; int key4; BTreeNode* child4; }; 단순한 나열로는 사용에 굉장한 불편이 따르게 될 것 같다. 해소를 위해 키와 자식을 가리키는 키 구조체를 만들어야 할 것 같다. BTreeNodeKey와 BTreeNode ///..
-
알고리즘...60일지 2021. 9. 30. 18:57
B 트리 작업 성능 분석 이진 검색 트리는 균형이 잘 맞을 경우 높이가 log_2-n 에 근접할 수 있다. 마찬가지로 d진 검색 트리가 균형이 잘 맞으면 높이가 log_d-n에 근접할 수 있다. 또한 B 트리는 루트를 제외한 노드는 최소 └d/2┘개의 자식을 가져야 하므로 B 트리의 깊이는 최악의 경우에도 대략 log_d/2-n 보다 깊을 수 없다. B 트리의 깊이는 다음의 범위에서 결정된다. [log_d-n, log_d/2-n] B 트리의 작업 수행시간은 디스크 접근 횟수를 기준으로 하며 B 트리의 모든 작업의 시간 복잡도는 점근적으로 Ο(logn)이 된다. ※ 노드를 메모리에 올린 이후 작업 시간이 디스크 접근 시간에 비하면 무시할 수 있을 정도로 작기 때문에 디스크 접근 횟수를 기준으로 한다. 더보..
-
알고리즘...59일지 2021. 9. 29. 11:17
B 트리에서의 삭제 입력된 값을 x라 할 때, x를 삽입하는 방법은 다음과 같다. x를 갖고 있는 노드를 찾는다. 이 노드가 리프 노다가 아니면 x의 직후 원소 y를 가진 리프 노드 r을 찾아 x와 y를 맞바꾼다. 리프 노드에서 x를 제거한다. x 제거 후 노드에 언더플로우가 발생하면 키를 가져올 수 있는 형제 노드가 있으면 해당 키를 가져온다. 키를 가져올 수 있는 형제 노드가 없으면 형제 노드와 병합한다. 부모 노드에 언더플로우 발생 시 부모 노드를 문제 노드로 하여 이상을 반복한다. - B 트리 삭제 알고리즘 주어진 키를 삭제한 뒤 언더플로우에 대한 처리를 진행한다. B 트리 삭제 알고리즘 BTreeDelete(t, x, v) { if (v가 리프 노드가 아님) then { x의 직후 원소 y를 가..
-
알고리즘...58일지 2021. 9. 28. 13:01
B 트리에서의 삽입 입력된 값을 x라 할 때, x를 삽입하는 방법은 다음과 같다. x를 삽입할 리프 노드를 찾는다. 리프 노드에 여유가 있으면 키를 삽입하고 종료한다. 리프 노드에 여유가 없으면 형제 노드에 여유가 있으면 형제 노드에 키를 하나 넘기고 종료한다. 형제 노드에 여유가 없으면 노드를 두 개로 분리한다. 부모 노드에 오버플로우 발생 시 부모 노드를 문제 노드로 하여 이상을 반복한다. - B 트리 삽입 알고리즘 새로운 키를 삽입한 뒤 오버플로우에 대한 처리를 진행한다. B 트리 삽입 알고리즘 BTreeInsert(t, x) { x를 삽입할 리프 노드 r을 찾는다; x를 r에 삽입한다; if (r에 오버플로우 발생) then { clearOverflow(r); } } clearOverflow(r)..
-
알고리즘...56일지 2021. 9. 24. 17:20
B 트리 개요 검색 트리가 방대하면 검색 트리를 메모리에 모두 올려두고 사용할 수 없게 되어 검색 트리가 디스크에 있는 상태에서 작업을 해야 한다. 이런 경우에 CPU 작업 효율성보다 디스크 접근 횟수가 효율을 좌우하게 된다. B 트리는 디스크 환경에서 사용하기 적합한 외부 다진 검색 트리로 B 트리의 한 노드에는 최대 k개까지의 키가 크기 순으로 저장되어 있다. ※ 검색 트리가 디스크에 있는 상태로 사용되면 이를 외부 검색 트리라고 한다. B 트리에 k개의 키가 존재하는 경우 k + 1 개의 자식을 가지게 된다. 이때, 주어진 키를 key 0 ~ key k - 1로 나타내고 자식 서브 트리를 각각 T 0 ~ T k 로 나타내면 다음의 관계가 성립한다. T 0 의 모든 노드의 값 < key 0 < T 1..