알고리즘...82

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* rsKey{ parent->keyRoot };
		while (rsKey != nullptr)
		{
			if (rsKey->left == node)
			{
				break;
			}
			lsKey = rsKey;
			rsKey = rsKey->next;
		}

		// 왼쪽 형제가 존재하고 키 인출 가능한 경우
		if (lsKey != nullptr && lsKey->left != nullptr
			&& lsKey->left->IsAbleToWithdraw())
		{
			BTreeNodeKey* key{ lsKey->left->GetBiggestKey() };
			lsKey->SwapValue(key);
			node->Insert(key);
			isDone = true;
		}
		// 오른쪽 형제가 존재하고 키 인출 가능한 경우
		else if (rsKey != nullptr && rsKey->right != nullptr
			&& rsKey->right->IsAbleToWithdraw())
		{
			BTreeNodeKey* key{ rsKey->right->GetSmallestKey() };
			rsKey->SwapValue(key);
			node->Insert(key);
			isDone = true;
		}

		// 인출 가능한 형제가 없는 경우
		if (!isDone)
		{
			BTreeNodeKey* key{ rsKey != nullptr ? rsKey : lsKey };
			BTreeNode* mergeNode{ MergeNodeWithKey(node, lsKey, rsKey) };

			if (key != nullptr)
			{
				if (key->prev != nullptr)
				{
					key->prev->right = mergeNode;
				}
				if (key->next != nullptr)
				{
					key->next->left = mergeNode;
				}

				if (parent == _root && _root->size == 1)
				{
					parent->Delete(key);
					_nodeManager.Push(parent);
					_root = mergeNode;
				}
				else if (!parent->Delete(key))
				{
					ClearUnderflow(parent);
				}
			}
		}
	}
}

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->keyRoot;
			}
			break;
		}

		BTreeNodeKey* key{ node->keyRoot };
		while (key != nullptr)
		{
			if (data < key->value)
			{
				node = key->left;
				break;
			}
			else if (key->value < data)
			{
				if (key->next == nullptr || data < key->next->value)
				{
					node = key->right;
					break;
				}
			}

			key = key->next;
		}
	}

	if (leafNode != nullptr && leafNode != node)
	{
		BTreeNodeKey* key{ node->GetKey(data) };
		BTreeNodeKey* leafKey{ leafNode->keyRoot };
		key->SwapValue(leafKey);
		node = leafNode;
	}

	return leafNode;
}

 

main.cpp

#include "Common.h"
#include "검색트리/BTree.h"

int main()
{
	int n = 9;
	int* arr;

	// 동작 테스트를 위한 값
	arr = new int[n]{ 10, 5, 20, 3, 7, 15, 25, 1, 4 };

	BTree tree;
	for (int i = 0; i < n; i++)
	{
		tree.Insert(arr[i]);
		tree.PrintTree();
	}

	tree.Delete(5);
	tree.PrintTree();

	tree.Delete(10);
	tree.PrintTree();

	tree.Delete(15);
	tree.PrintTree();

	tree.Delete(1);
	tree.PrintTree();

	tree.Delete(3);
	tree.PrintTree();

	tree.Delete(20);
	tree.PrintTree();

	tree.Delete(7);
	tree.PrintTree();

	tree.Delete(4);
	tree.PrintTree();

	tree.Delete(25);
	tree.PrintTree();

	delete[] arr;
}

 

실행결과

--------------------
[10]
--------------------

--------------------
[5, 10]
--------------------

--------------------
[5, 10, 20]
--------------------

--------------------
[5]
[3][10, 20]
--------------------

--------------------
[5]
[3][7, 10, 20]
--------------------

--------------------
[7]
[3, 5][10, 15, 20]
--------------------

--------------------
[10]
[3, 5, 7][15, 20, 25]
--------------------

--------------------
[3, 10]
[1][5, 7][15, 20, 25]
--------------------

--------------------
[3, 10]
[1][4, 5, 7][15, 20, 25]
--------------------

--------------------
[3, 10]
[1][4, 7][15, 20, 25]
--------------------

--------------------
[3, 15]
[1][4, 7][20, 25]
--------------------

--------------------
[3, 20]
[1][4, 7][25]
--------------------

--------------------
[4, 20]
[3][7][25]
--------------------

--------------------
[20]
[4, 7][25]
--------------------

--------------------
[7]
[4][25]
--------------------

--------------------
[4, 25]
--------------------

--------------------
[25]
--------------------

--------------------
EMPTY TREE
--------------------