알고리즘...79

디버그를 위한 출력 함수 구현

삽입과 삭제에서 적절하게 처리가 되지 않아 디버깅을 하기 위해 출력 함수를 구현했다.

 

BTree

/// <summary>
/// 트리를 텍스트로 출력한다.
/// </summary>
void BTree::PrintTree()
{
	std::cout << "\n--------------------\n";

	if (_root == nullptr)
	{
		std::cout << "EMPTY TREE";
	}
	else
	{
		int nodeCount{ 1 };
		int counter{ 0 };

		_queue.push(_root);
		while (!_queue.empty())
		{
			BTreeNode* node{ _queue.front() };
			_queue.pop();

			if (counter == nodeCount)
			{
				counter = 0;
				nodeCount *= BTreeNode::TotalKeyCount;
				std::cout << '\n';
			}

			BTreeNodeKey* key{ node->keyRoot };
			if (key->left != nullptr)
			{
				_queue.push(key->left);
			}

			std::cout << '[';
			while (key != nullptr)
			{
				if (key->right != nullptr)
				{
					_queue.push(key->right);
				}
				std::cout << key->value << (key->next != nullptr ? ", " : "");
				key = key->next;
			}
			std::cout << ']';

			counter++;
		}
	}

	std::cout << "\n--------------------\n";
}

 

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.Delete(10);

	tree.Delete(15);

	delete[] arr;
}

 

실행결과

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

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

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

--------------------
[5]
[3, 3, 3, 3, 3, 3, 3, 3,

 

분할이 일어날 때 prev와 next 값이 초기화가 되지 않아서 발생한 것 같다.

 

확인해보니 GetBiggestKey 에서 반환 값이 keyRoot 일 때 처리를 하지 않아서 발생한 것이었고 수정한 이후에는 다른 버그가 발생했다.

 

실행결과2

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

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

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

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

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

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

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

 

15를 삽입하면서 값이 분할되고 부모 노드가 있으니 부모 노드에 삽입 처리가 되어야 하는데 뭔가 정상적으로 동작하지 않았다.