알고리즘
-
KD 트리 알고리즘프로그래밍 기초/알고리즘 2021. 11. 18. 18:51
KD 트리 이진 검색 트리를 다차원 검색 트리로 확장한 트리 자료구조이다. KD 트리는 같은 레벨의 노드는 동등한 위치의 필드를 사용하여 분기를 진행하며 k 개의 필드를 가지는 KD 트리에서 레벨 k에 도달한 경우 다시 0 번째 필드를 사용하여 분기를 진행한다. ※ 다차원 검색 트리는 노드의 키가 하나의 필드가 아닌 여러 개의 필드로 이루어진 검색 트리를 말한다. KD 트리에서의 검색 기본적으로 이진 검색 트리와 동일한 방식으로 탐색을 진행하나 KD 트리는 각 레벨 별로 다른 필드를 사용하여 검색을 진행하는 점이 다르다. 레벨 0 에서는 첫 번째 필드를 사용하여 분기하고 레벨 1에서는 두 번째 필드를 사용하여 분기를 진행한다. 이렇게 진행하다 레벨 k 에서는 다시 첫 번째 필드를 사용하는 방식으로 검색을..
-
알고리즘...85일지 2021. 11. 17. 20:31
KD 트리의 삽입과 삭제 KD 트리는 검색 과정을 통해 리프 노드에 도달한 경우 왼쪽 혹은 오른쪽 자식으로 새로운 노드를 삽입하면 된다. 삭제의 경우 이진 검색 트리와 달리 자식이 하나인 경우에도 자식이 두 개인 경우와 마찬가지로 처리해 줘야 한다. 이는 단순히 상위 레벨로 노드를 올리게 된다면 사용하는 필드가 달라져 속성이 깨지기 때문이다. 삭제 시 노드가 두 개인 경우, 오른쪽 서브 트리에서 삭제할 노드에 사용된 필드의 값이 가장 작은 노드를 찾아 삭제할 노드와 교환하고 찾은 노드를 삭제한 뒤, 말단 노드가 아닌 경우 삭제 과정을 반복하면 된다. 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘
-
알고리즘...84일지 2021. 11. 16. 20:40
KD 트리 개요 KD 트리는 이진 검색 트리를 확장한 것으로 k 개의 필드로 이루어진 키를 사용하며, 이진 검색 트리와 비슷하게 동작 하나 레벨 별로 분기 시 하나의 필드만을 사용한다는 점이 다르다. 위 그림에서 보는 것처럼 KD 트리는 같은 레벨의 노드는 동등한 위치의 필드를 사용하여 분기를 진행하며 k 개의 필드를 가지는 KD 트리에서 레벨 k에 도달한 경우 다시 0 번째 필드를 사용하여 분기를 진행한다. 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘
-
알고리즘...83일지 2021. 11. 15. 14:00
다차원 검색 트리 데이터를 검색하기 위한 키가 여러 개로 이루어진 검색 트리를 말하며 다음과 같은 종류가 존재한다. KD 트리 이진 검색 트리를 확장한 것으로 검색에 두 키 중 하나의 키만 사용한다. KDB 트리 B 트리를 확장한 것으로 루트 노드에서 부터 전체 공간을 쪼개가면서 검색을 진행한다. R 트리 B 트리를 확장한 것으로 KDB 트리와 달리 키를 포함하는 최소 영역에만 노드가 존재한다. 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘
-
B 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 11. 11. 19:58
B 트리 이진 검색 트리를 기반으로 노드에 Balance Factor(이후 BF)를 추가하여 BF의 상태에 따라 트리의 균형을 유지한다. B 트리 개요 검색 트리가 방대하면 검색 트리를 메모리에 모두 올려두고 사용할 수 없게 되어 검색 트리가 디스크에 있는 상태에서 작업을 해야 한다. 이런 경우에 CPU 작업 효율성보다 디스크 접근 횟수가 효율을 좌우하게 된다. B 트리는 디스크 환경에서 사용하기 적합한 외부 다진 검색 트리로 B 트리의 한 노드에는 최대 k개까지의 키가 크기 순으로 저장되어 있다. ※ 검색 트리가 디스크에 있는 상태로 사용되면 이를 외부 검색 트리라고 한다. B 트리에 k개의 키가 존재하는 경우 k + 1 개의 자식을 가지게 된다. 이때, 주어진 키를 key 0 ~ key k - 1로 ..
-
알고리즘...82일지 2021. 11. 10. 09:16
B 트리 삭제 메서드, 병합 처리 병합 처리를 구현한 부분 중 leaf 노드와 키를 처리하는 부분에서 키를 노드에서 빼는 과정으로 인해 버그가 발생하여 해당 값을 빼는 게 아니니 최소 값인 keyRoot를 이용하는 것으로 수정했다. BTree void BTree::ClearUnderflow(BTreeNode* node) { // 노드가 루트인 경우 if (node == _root) { if (node->size == 0) { _nodeManager.Push(node); _root = nullptr; } } else { bool isDone{ false }; BTreeNode* parent{ node->parent }; BTreeNodeKey* lsKey{ nullptr }; BTreeNodeKey* rs..
-
알고리즘...81일지 2021. 11. 9. 20:16
B 트리 삭제 메서드 구현 시작 기존 삭제 메서드에서 문제가 있었던 부분을 수정했다. BTree::GetProperNodeToDelete BTreeNode* BTree::GetProperNodeToDelete(int data) { BTreeNode* node{ _root }; BTreeNode* leafNode{ nullptr }; while (node != nullptr) { if (node->IsContainsData(data)) { BTreeNodeKey* key{ node->GetKey(data) }; leafNode = node; while (key->right != nullptr) { leafNode = key->right; key = leafNode->GetSmallestKey(); } br..
-
알고리즘...80일지 2021. 11. 3. 01:49
형제 노드로 넘기는 처리 기존 코드에서 왼쪽 형제로 키를 넘길 때 기존 노드에서 가장 작은 값을 가져오는데 이때 next를 nullptr로 처리해주지 않아 적절하게 완료되지 않았었다. 노드를 인출할 때 완전히 연결을 끊어줬다. BTreeNode /// /// 가장 작은 키를 노드에서 떼어내 반환한다. /// /// 가장 작은 키 BTreeNodeKey* BTreeNode::GetSmallestKey() { BTreeNodeKey* key{ nullptr }; if (keyRoot != nullptr) { key = keyRoot; keyRoot = keyRoot->next; keyRoot->prev = nullptr; key->next = nullptr; } size--; return key; } 이제 ..