알고리즘
-
알고리즘...71일지 2021. 10. 18. 16:53
B 트리 삽입 오버플로우 처리 오버 플로우 처리 중 삽입 가능한 형제가 존재한 경우에 대한 처리를 구현한다. 오버 플로우가 발생한 노드의 형제 노드의 위치가 왼쪽인 경우 가장 작은 키를 부모에 넣고 부모의 형제 노드를 가리키는 키와 값을 바꾼 뒤 해당 키를 형제 노드에 삽입하면 된다. 이를 위해 Node의 Insert 함수를 수정하여 Key가 직접 입력된 경우를 적절하게 처리해 주는 함수를 추가한다. BTreeNodeKey /// /// 새 키를 기존 키의 오른쪽에 삽입한다. /// /// 삽입할 키 void BTreeNodeKey::AddKeyToNext(BTreeNodeKey* newKey) { BTreeNodeKey* nextKey{ next }; if (nextKey != nullptr) { ne..
-
알고리즘...70일지 2021. 10. 15. 00:55
B 트리 삽입 메서드 구현 진행 적절한 노드를 검색 함수를 수정하여 다음과 같이 구현했다. BTree::GetProperNodeToInsert(int data) /// /// 주어진 data를 삽입할 수 있는 적절한 노드를 찾아 반환한다. /// /// 삽입할 값 /// 데이터를 삽입할 수 있는 노드 BTreeNode* BTree::GetProperNodeToInsert(int data) { if (_root == nullptr) { _root = _nodeManager.Pop(); return _root; } BTreeNode* node{ _root }; BTreeNode* prevNode{ nullptr }; while (node != nullptr) { if (node->IsAbleToInsert(..
-
알고리즘...69일지 2021. 10. 14. 14:22
B 트리 삽입 함수 구현 진행 노드에 키를 삽입하기 위해 여러 확인이 필요한데 우선 단순히 키를 삽입하는 함수를 구현했다. BTree::Insert /// /// 새 키를 기존 키의 왼쪽에 삽입한다. /// /// 삽입할 키 void BTreeNodeKey::AddKeyToPrev(BTreeNodeKey* newKey) { BTreeNodeKey* prevKey{ prev }; if (prevKey != nullptr) { prevKey->next = newKey; newKey->prev = prevKey; } newKey->next = this; prev = newKey; } /// /// 새 키를 기존 키의 오른쪽에 삽입한다. /// /// 삽입할 키 void BTreeNodeKey::AddKeyTo..
-
알고리즘...68일지 2021. 10. 13. 13:14
B 트리 검색 함수 구현 기존 배열에서 포인터 방식으로 구현 변경. 기존 방식보다 가독성 측면에서 더 나은 것 같다. BTree::Exists /// /// B 트리를 확인하여 주어진 값이 트리에 존재하는지 여부를 반환한다. /// /// 확인할 값 /// 존재 여부 bool BTree::Exists(int data) { BTreeNode* node{ _root }; while (node != nullptr) { BTreeNodeKey* key{ node->keyRoot }; while (key != nullptr) { if (key->value == data) { return true; } if (data value) { node = key->left; break; } else if (ke..
-
알고리즘...67일지 2021. 10. 12. 16:30
B 트리 삽입 알고리즘 문제 파악 삽입이 진행될 때 노드에 공간이 있는 경우 오름차순으로 정렬하여 삽입이 진행되어야 한다. 또, 삽입 후 오버플로우에 대한 처리를 위해 키를 배열로 묶는 게 아닌 포인터로 연결할 필요가 있어 보인다. #pragma region 노드 /// /// 노드의 키를 초기화한다. /// void BTreeNodeKey::Clear() { prev = nullptr; left = nullptr; value = 0; right = nullptr; next = nullptr; } /// /// 주어진 값을 키에 저장한다. /// /// 저장할 값 void BTreeNodeKey::Set(int data) { value = data; } /// /// B 트리 소멸자, 생성했던 키를 제거..
-
알고리즘...66일지 2021. 10. 10. 00:22
B 트리 삽입 함수 구현 진행 삽입 알고리즘 처리 중 재귀적으로 처리해야 하는 부분을 적용했다. BTree::Insert /// /// 주어진 값을 B 트리에 삽입한다. /// /// 삽입할 값 void BTree::Insert(int data) { if (Exists(data)) { return; } Insert(_root, data); } /// /// 주어진 값을 B 트리에 삽입한다. /// /// 삽입할 노드 /// 삽입할 값 void BTree::Insert(BTreeNode* parent, int data) { // 루트가 빈 값이었던 경우 if (parent == nullptr) { BTreeNode* node{ _nodeManager.Pop() }; node->Insert(data); _r..
-
알고리즘...65일지 2021. 10. 8. 12:52
B 트리 삽입 처리 진행 삽입 처리 중 노드가 가득 찬 경우 새로운 노드를 만드는 코드 추가 BTreeNode /// /// 삽입 처리를 위한 적절한 노드를 반환한다. /// /// 추가할 값 /// 적절한 노드 BTreeNode* BTreeNode::GetProperNodeToInsert(int data) { for (int i = 0; i < size; i++) { if (data < keys[i].value) { return keys[i].left; } if (keys[i].value < data) { if (i == size) { return keys[i].right; } else if (data < keys[i + 1].value) { return keys[i].right; } } } retur..
-
알고리즘...64일지 2021. 10. 7. 14:51
B 트리 삽입 함수 구현 시작 먼저 삽입 처리를 수월하게 하기 위해 노드에 삽입 함수를 구현하고 삽입된 키의 개수를 수월하게 관리하기 위해 노드에 현재 키의 개수를 도입한다. BTree.h /// /// B 트리의 노드에서 사용할 키 /// struct BTreeNodeKey { BTreeNodeKey() : left(nullptr), value(0), right(nullptr) {} void Clear(); void Set(int data); BTreeNode* left; int value; BTreeNode* right; }; /// /// B 트리에 사용할 노드 /// struct BTreeNode { static const size_t TotalKeyCount{ 4 }; BTreeNode(); ~..