알고리즘
-
알고리즘...79일지 2021. 11. 2. 02:43
디버그를 위한 출력 함수 구현 삽입과 삭제에서 적절하게 처리가 되지 않아 디버깅을 하기 위해 출력 함수를 구현했다. BTree /// /// 트리를 텍스트로 출력한다. /// void BTree::PrintTree() { std::cout left); } std::cout right != nullptr) { _queue.push(key->right); } std::cout value next != nullptr ? ", " : ""); key = key->next; } std::cout
-
알고리즘...78일지 2021. 11. 1. 21:29
B 트리 삭제 메서드 구현 언더 플로우 처리를 구현한다. 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* rsKey{ parent->keyRoot }; while (rsKey != nullpt..
-
알고리즘...77일지 2021. 10. 27. 12:29
삭제 메서드 구현, 부모 노드가 존재하는 경우 처리 노드가 루트인 경우와 노드의 형제에서 키를 인출해 가져올 수 있는 경우를 처리한다. 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* rsKe..
-
알고리즘...76일지 2021. 10. 26. 14:49
삭제 알고리즘 수정 기존 삭제 시 단순히 해당 값을 포함하는 노드를 반환했다면 이번에는 적절한 처리를 위해 해당 노드가 자식 노드가 있으면 오른쪽 서브 트리에서 가장 작은 값을 가진 키의 값과 교환하여 리프 노드에서 삭제가 일어나도록 수정했다. BTreeNodeKey /// /// 주어진 값을 가지는 키를 반환한다. /// /// 찾을 값 /// 값을 가지는 키 BTreeNodeKey* BTreeNode::GetKey(int data) { BTreeNodeKey* key{ keyRoot }; while (key != nullptr) { if (key->value == data) { break; } key = key->next; } return key; } BTree /// /// 주어진 값을 가지는 키를..
-
알고리즘...75일지 2021. 10. 22. 01:00
B 트리 제거 메소드 구현 진행 형제 노드에 여유 노드가 있는 경우를 처리한다. BTreeNode /// /// 이 노드에서 키를 인출해도 안정적인지 여부를 반환한다. /// /// 키를 인출해도 안정적인지 여부 bool BTreeNode::IsAbleToWithdraw() { return size > TotalKeyCount / 2; } 노드를 제거한 뒤 처리를 위해 함수를 구현하다가 노드를 삭제하는 건 리프 노드가 아닌 중간 노드에서도 발생할 수 있다는 것을 알게 됐다. 이 부분에서도 이진 검색 트리와 동일하게 해당 키에 자식 노드가 존재하는 경우 자식 노드에서 적절한 키를 가져와 값을 교환하고 리프 노드에서 삭제가 진행되도록 구현해야 할 필요가 있어 보인다. B 트리는 상위 노드가 되면 항상 두 개..
-
알고리즘...74일지 2021. 10. 21. 19:12
B 트리 삭제 처리 삽입 처리와 마찬가지로 일단 노드에서 키를 제거한 뒤 노드의 크기가 k / 2 보다 작아지면 언더플로우 처리를 진행한다. 먼저, 일반적인 삭제 연산을 구현한다. BTreeNode /// /// 주어진 데이터를 포함하는 키를 노드에서 제거한다. /// /// 제거할 값 /// 성공 여부 bool BTreeNode::Delete(int data) { BTreeNodeKey* key{ keyRoot }; while (key != nullptr) { if (key->value == data) { return Delete(key); } } return false; } /// /// 주어진 키를 노드에서 제거한다. /// /// 제거할 키 /// 성공 여부 bool BTreeNode::Delet..
-
알고리즘...73일지 2021. 10. 20. 14:47
B 트리 삽입 메서드 오버플로우 처리 오버 플로우 처리 시 필요한 노드를 분할하는 함수 추가했으며 기존 키 삽입 시 좌우 자식을 적절하게 넘겨주는 처리를 추가했다. BTreeNodeKey /// /// 새 키를 기존 키의 왼쪽에 삽입한다. /// /// 삽입할 키 void BTreeNodeKey::AddKeyToPrev(BTreeNodeKey* newKey) { BTreeNodeKey* prevKey{ prev }; if (prevKey != nullptr) { prevKey->next = newKey; newKey->prev = prevKey; prevKey->right = newKey->left; } newKey->next = this; prev = newKey; left = newKey->right..
-
알고리즘...72일지 2021. 10. 19. 15:04
B 트리 삽입 오버플로우 처리 진행 삽입 가능한 형제 노드가 없는 경우 기존 노드의 중간 값을 기준으로 두 개의 노드로 분리하고 중간 값을 부모로 삽입한 뒤 좌, 우 자식 노드로 기존 중간 값을 저장해 줘야 한다. 또, 삽입된 부모 노드에서 형제 키 값이 가리키는 노드를 적절하게 수정해 줘야 한다. 이후 부모 노드의 크기가 오버된 경우 오버플로우 처리를 부모 노드에 대해 반복한다. ※ 만약 처리한 노드가 루트 노드면 중간 키 값을 새로운 노드로 추가하고 새 노드를 루트로 변경한다. BTreeNode::GetMiddleKey /// /// 노드의 키 중 중간 값을 가진 키를 떼어내 반환한다. /// /// 중간 키 BTreeNodeKey* BTreeNode::GetMiddleKey() { size_t mi..