알고리즘...54

노드를 그려야 하는 크기를 정한 뒤 노드를 배치하는 방법

노드가 서로 동일한 간격으로 떨어져 있기만 하면 깔끔하게 정리가 가능할 것이라는 생각이 들었다.

아이디어는 다음과 같다. 다음과 같은 이진 검색 트리가 있다고 하자.

대략적인 이진 검색 트리

 

이에 대해 깊이 별 노드의 최대 개수는 다음과 같다.

---

깊이가 1인 경우 = 2^0 = 1 개

깊이가 2인 경우 = 2^1 = 2 개

깊이가 3인 경우 = 2^2 = 4개

 

일반화 하면 깊이가 n 일때 노드의 최대 개수는 2ⁿ - ¹ 개가 된다.

---

가장 하단의 노드 사이 간격을 노드의 크기와 동일하게 한다고 가정했을 때 필요한 공백의 개수는 노드의 개수 + 1이 되므로 필요한 넓이는 다음과 같다.

---

공백의 개수 + 노드의 개수 * 노드의 크기

---

이를 이용해 노드를 출력하는 코드를 작성한다.

 

BinarySearchTree.h

/// <summary>
/// 이진 검색 트리에 사용할 노드
/// </summary>
struct BinarySearchNode
{
	const static int Width = 5;

	BinarySearchNode() : isEmpty(false), data{ 0 }, parent{ nullptr },
		left{ nullptr }, right{ nullptr } {}
	BinarySearchNode(int data) : isEmpty(false), data{ data }, parent{ nullptr },
		left{ nullptr }, right{ nullptr } {}

	void Clear()
	{
		data = 0;
		parent = nullptr;
		left = nullptr;
		right = nullptr;
	}

	int GetMaxDepth()
	{
		int leftMaxDepth{ left != nullptr ? left->GetMaxDepth() : 0 };
		int rightMaxDpth{ right != nullptr ? right->GetMaxDepth() : 0 };
		return (leftMaxDepth > rightMaxDpth ? leftMaxDepth : rightMaxDpth) + 1;
	}

	int GetCurDepth()
	{
		return (parent != nullptr ? parent->GetCurDepth() : 0) + 1;
	}

	bool HasLeftChild()
	{
		return left != nullptr;
	}

	bool HasRightChild()
	{
		return right != nullptr;
	}

	string ToString()
	{
		if (isEmpty)
		{
			return string(Width, '_');
		}

		string dataStr = std::to_string(data);
		size_t spaceCnt = Width - dataStr.size();
		size_t leftSpaceCnt = spaceCnt / 2;
		size_t rightSpaceCnt = spaceCnt / 2 + spaceCnt % 2;

		return string(leftSpaceCnt, '_') + dataStr + string(rightSpaceCnt, '_');
	}

	bool isEmpty;

	int data;
	BinarySearchNode* parent;
	BinarySearchNode* left;
	BinarySearchNode* right;
};

/// <summary>
/// 이진 검색 트리에서 노드의 재활용을 위한 매니저
/// </summary>
class BinarySearchNodeManager
{
public:
	~BinarySearchNodeManager();

	void Push(BinarySearchNode* node);
	BinarySearchNode* Pop();
	BinarySearchNode* GetEmptyNode(BinarySearchNode* parent);

private:
	BinarySearchNode* nodes;
};

 

BinarySearchTree.cpp

/// <summary>
/// 주어진 노드를 부모로 하는 공백 노드를 반환한다.
/// </summary>
/// <param name="parent">부모 노드</param>
/// <returns>공백 노드</returns>
BinarySearchNode* BinarySearchNodeManager::GetEmptyNode(BinarySearchNode* parent)
{
	BinarySearchNode* emptyNode = Pop();
	emptyNode->parent = parent;
	emptyNode->isEmpty = true;

	return emptyNode;
}

/// <summary>
/// 이진 검색 트리를 출력한다.
/// </summary>
void BinarySearchTree::PrintBinarySearchTree()
{
	if (_root == nullptr)
	{
		std::cout << "EMPTY\n";
		return;
	}

	int maxDepth{ _root->GetMaxDepth() };
	int maxNodeCount{ static_cast<int>(std::pow(2, maxDepth - 1)) };
	int totalCount{ maxNodeCount * 2 + 1 };
	int lineWidth{ totalCount * BinarySearchNode::Width };

	for (int i = 1; i <= maxDepth; i++)
	{
		_numberMap[i] = "";
	}

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

		PrintBinarySearchTree(node, lineWidth);

		if (node->left != nullptr)
		{
			_queue.push(node->left);
		}
		else if (!node->isEmpty)
		{
			_queue.push(_nodeManager.GetEmptyNode(node));
		}
		if (node->right != nullptr)
		{
			_queue.push(node->right);
		}
		else if (!node->isEmpty)
		{
			_queue.push(_nodeManager.GetEmptyNode(node));
		}

		if (node->isEmpty)
		{
			_nodeManager.Push(node);
		}
	}

	for (int i = 1; i <= maxDepth; i++)
	{
		std::cout << _numberMap[i] << '\n';
	}
	std::cout << "\n\n";
}

/// <summary>
/// 이진 검색 트리를 출력한다.
/// </summary>
/// <param name="node">현재 출력할 노드</param>
void BinarySearchTree::PrintBinarySearchTree(BinarySearchNode* node, int lineWidth)
{
	int curDepth{ node->GetCurDepth() };
	int curNodeCount{ static_cast<int>(std::pow(2, curDepth - 1)) };
	int totalNodeSize{ curNodeCount * BinarySearchNode::Width };
	int blankCount{ curNodeCount + 1 };
	int totalBlankSize{ lineWidth - totalNodeSize };
	int blankSize{ totalBlankSize / blankCount };

	string& numberStr{ _numberMap[curDepth] };
	numberStr.append(string(blankSize, ' '));
	numberStr.append(node->ToString());
}

 

main.cpp

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

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

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

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

	tree.Delete(5);
	tree.Delete(10);
	tree.Delete(15);
	tree.PrintBinarySearchTree();

	delete[] arr;
}

 

실행결과

                                        _10__
                         __5__                         _20__
             __3__             __7__             _15__             _25__
     __1__     __4__     _____     _____     _____     _____     _____     _____


                                        __7__
                         __4__                         _20__
             __3__             _____             _____             _25__
     __1__     _____     _____     _____