c++ binary Search Tree

스마트 포인터를 이용한 Binary Search Tree 구현

#pragma once

#include <memory>

namespace assignment4
{
	template<typename T>
	class TreeNode final
	{
	public:
		TreeNode(std::unique_ptr<T> data);
		TreeNode(std::shared_ptr<TreeNode<T>> parent, std::unique_ptr<T> data);

		std::unique_ptr<T> Data;
		std::shared_ptr<TreeNode<T>> Left;
		std::shared_ptr<TreeNode<T>> Right;
		std::weak_ptr<TreeNode<T>> Parent;
	private :
	};

	template<typename T>TreeNode<T>::TreeNode(std::unique_ptr<T> data)
		: Data(std::move(data))
	{
	}

	template<typename T>TreeNode<T>::TreeNode(std::shared_ptr<TreeNode<T>> parent, std::unique_ptr<T> data)
		: Parent(parent)
		, Data(std::move(data))
	{
	}
}

#pragma once

#include <memory>
#include <vector>

namespace assignment4
{
	template<typename T>
	class TreeNode;

	template<typename T>
	class BinarySearchTree final
	{
	public:
		void Insert(std::unique_ptr<T> data);
		bool Search(const T& data);
		bool Delete(const T& data);
		const std::weak_ptr<TreeNode<T>> GetRootNode() const;

		static std::vector<T> TraverseInOrder(const std::shared_ptr<TreeNode<T>> startNode);
	private:
		void insert(std::shared_ptr<TreeNode<T>> node, std::unique_ptr<T> data);
		std::shared_ptr<TreeNode<T>> search(std::shared_ptr<TreeNode<T>> node, const T& data) const;
		void changeParent(std::shared_ptr<TreeNode<T>> deleteNode, std::shared_ptr<TreeNode<T>> changeNode);
		std::shared_ptr<TreeNode<T>> mRoot;

	};

	template<typename T>
	void BinarySearchTree<T>::Insert(std::unique_ptr<T> data)
	{
		if (mRoot == nullptr)
		{
			std::shared_ptr<TreeNode<T>> node = std::make_shared<TreeNode<T>>(std::move(data));
			mRoot = node;
			return;
		}

		insert(mRoot, std::move(data));
	}
	template<typename T>
	void BinarySearchTree<T>::insert(std::shared_ptr<TreeNode<T>> parentNode, std::unique_ptr<T> data)
	{
		if (*data <= *parentNode->Data)
		{
			// left
			if (parentNode->Left == nullptr)
			{
				parentNode->Left = std::make_shared<TreeNode<T>>(parentNode, std::move(data));
			}
			else
			{
				insert(parentNode->Left, std::move(data));
			}
		}
		else
		{
			// right
			if (parentNode->Right == nullptr)
			{
				parentNode->Right = std::make_shared<TreeNode<T>>(parentNode, std::move(data));
			}
			else
			{
				insert(parentNode->Right, std::move(data));
			}
		}
	}

	template<typename T>
	const std::weak_ptr<TreeNode<T>> BinarySearchTree<T>::GetRootNode() const
	{
		return mRoot;
	}

	template<typename T>
	bool BinarySearchTree<T>::Search(const T& data)
	{
		std::shared_ptr<TreeNode<T>> node = search(mRoot, data);
		return node != nullptr;
	}

	template<typename T>
	std::shared_ptr<TreeNode<T>> BinarySearchTree<T>::search(std::shared_ptr<TreeNode<T>> node, const T& data) const
	{
		if (node == nullptr)
			return nullptr;

		if (*node->Data == data)
		{
			return node;
		}
		else if (data < *node->Data)
		{
			return search(node->Left, data);
		}
		else if (data > * node->Data)
		{
			return search(node->Right, data);
		}
	}

	template<typename T>
	bool BinarySearchTree<T>::Delete(const T& data)
	{
		std::shared_ptr<TreeNode<T>> node = search(mRoot, data);
		if (node == nullptr)
			return false;

		if (node->Left != nullptr && node->Right != nullptr)
		{
			std::shared_ptr<TreeNode<T>> sucecessorNode = node->Right;

			while (true)
			{
				if (sucecessorNode->Left == nullptr)
					break;

				sucecessorNode = sucecessorNode->Left;
			}

			changeParent(sucecessorNode, sucecessorNode->Right);
			changeParent(node, sucecessorNode);
			sucecessorNode->Left = node->Left;
			sucecessorNode->Right = node->Right;

			if (sucecessorNode->Left != nullptr)
			{
				sucecessorNode->Left->Parent = sucecessorNode;
			}
			if (sucecessorNode->Right != nullptr)
			{
				sucecessorNode->Right->Parent = sucecessorNode;
			}
		}
		else if (node->Left != nullptr)
		{
			changeParent(node, node->Left);
		}
		else if (node->Right != nullptr)
		{
			changeParent(node, node->Right);
		}
		else
		{
			changeParent(node, nullptr);
		}

		return true;
	}

	template<typename T>
	void BinarySearchTree<T>::changeParent(std::shared_ptr<TreeNode<T>> deleteNode, std::shared_ptr<TreeNode<T>> changeNode)
	{
		std::shared_ptr<TreeNode<T>> parent = deleteNode->Parent.lock();
		if (parent == nullptr)
		{
			mRoot = changeNode;
			return;
		}

		if (changeNode == nullptr)
		{
			if (parent->Left == deleteNode)
			{
				parent->Left = nullptr;
			}
			else if (parent->Right == deleteNode)
			{
				parent->Right = nullptr;
			}
		}
		else
		{
			if (parent->Left == deleteNode)
			{
				parent->Left = changeNode;
			}
			else if (parent->Right == deleteNode)
			{
				parent->Right = changeNode;
			}
			changeNode->Parent = deleteNode->Parent;
		}
	}

	template<typename T>
	std::vector<T> BinarySearchTree<T>::TraverseInOrder(const std::shared_ptr<TreeNode<T>> startNode)
	{
		std::vector<T> v;

		if (startNode == nullptr)
			return v;

		if (startNode->Left != nullptr)
		{
			v = TraverseInOrder(startNode->Left);
		}

		v.push_back(*startNode->Data);

		if (startNode->Right != nullptr)
		{
			std::vector<T> vR = TraverseInOrder(startNode->Right);
			v.insert(v.end(), vR.begin(), vR.end());
		}

		return v;
	}
}