알고리즘...81

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();
			}
			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->GetSmallestKey() };
		key->SwapValue(leafKey);
		node = leafNode;
	}

	return leafNode;
}

 

BTreeNode::Delete

bool BTreeNode::Delete(int data)
{
	BTreeNodeKey* key{ keyRoot };

	while (key != nullptr)
	{
		if (key->value == data)
		{
			return Delete(key);
		}
		key = key->next;
	}

	return false;
}

 

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();

	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, 7]
[1][4][20, 25]
--------------------

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

 

이제 언더플로우에 대한 처리를 진행하면 될 것 같다.