Thread: Binary Search Tree - Peer Review (Part 1)

So, I've made a minimalistic binary search tree data structure, not for practical reasons, but for experience and ... for a better grade, shall we say?
Anyway, this being a forum of experts and all, I wanted to hear your opinions on the code, if any. Criticism is sincerely welcome.

I know the interface isn't truly consistent, and that's bad, but eh... I figure it doesn't matter so much for a minimalistic implementation. This is just to get a working search tree.

The code is about 156 lines long, so sit down, grab some beer or coffee and have fun looking at it!

Code:

#ifndef BSEARCHTREE_20110923_2257
#define BSEARCHTREE_20110923_2257

#include <utility>
#include <memory>
#include <functional>
#include <stdexcept>
#include <cassert>

namespace NBSearchTree
{
	namespace Exceptions
	{
		class XKeyNotUnique: public std::runtime_error { public: XKeyNotUnique(): std::runtime_error("Key not unique") {} };
		class XKeyNotFound: public std::runtime_error { public: XKeyNotFound(): std::runtime_error("Key not found") {} };
	}

	template<typename Key_t, typename Value_t> class XTree;

	template<typename Key_t, typename Value_t>
	class XNode
	{
	public:
		friend XTree<Key_t, Value_t>;

		XNode(Key_t Key, Value_t & Value): m_Key(Key), m_Value(Value) {}
		void SetValue(const Value_t & Value) { m_Value = Value; }
		const Value_t & GetValue() const { return m_Value; }
		const Key_t & GetKey() const { return m_Key; }
		const std::shared_ptr<XNode> & GetLeft() const { return m_Left; }
		const std::shared_ptr<XNode> & GetRight() const { return m_Right; }

	protected:
		void SetKey(const Key_t & Key) { m_Key = Key; }
		std::shared_ptr<XNode> & GetModifiableLeft() { return m_Left; }
		std::shared_ptr<XNode> & GetModifiableRight() { return m_Right; }

		Key_t m_Key;
		Value_t m_Value;
		std::shared_ptr<XNode> m_Left, m_Right;
	};

	template<typename Key_t, typename Value_t>
	class XTree
	{
	public:
		typedef XNode<Key_t, Value_t> Node_t;
		typedef std::shared_ptr<Node_t> NodePtr_t;

		XTree(): m_TreeSize(0) {}

		void Insert(const Key_t & Key, Value_t Value)
		{
			if (!m_Root)
			{
				m_Root = std::make_shared<Node_t>(Key, Value);
				return;
			}
			Insert(m_Root, Key, Value);
		}

		NodePtr_t Find(const Key_t & Key) const { return Find(Key, m_Root).first; }

		bool Delete(const Key_t & Key)
		{
			try
			{
				NodePtr_t tmp;
				Delete( Key, Find(Key, m_Root, tmp) );
				return true;
			}
			catch (const Exceptions::XKeyNotFound&) { return false; }
		}

		NodePtr_t GetRoot() const { return m_Root; }

	protected:
		void Delete(const Key_t & Key, const std::pair<NodePtr_t, NodePtr_t> KeyPair)
		{
			auto pair = KeyPair;
			auto parent = pair.second;
			auto to_delete = pair.first;

			if (to_delete->m_Left && to_delete->m_Right)
			{
				auto successor = to_delete->m_Right;
				auto successor_parent = to_delete;

				while (successor->m_Left)
				{
					successor_parent = successor;
					successor = successor->m_Left;
				}

				auto successor_key = successor->GetKey();
				Delete(successor->m_Key, std::make_pair(successor, successor_parent));
				to_delete->SetKey(successor_key);
			}
			else
			{
				if (parent)
				{
					if ( Key < parent->GetKey() ) DeleteHelper(to_delete, parent->GetModifiableLeft());
					else if ( Key > parent->GetKey() ) DeleteHelper(to_delete, parent->GetModifiableRight());
				}
				else
				{
					// Special case: deleting root
					DeleteHelper(to_delete, m_Root);
				}
			}
		}

		void DeleteHelper(NodePtr_t & ToDelete, NodePtr_t & NodeToModify)
		{
			if (!ToDelete->m_Left && !ToDelete->m_Right)
				NodeToModify = nullptr;
			else if (ToDelete->m_Left && !ToDelete->m_Right)
				NodeToModify = ToDelete->m_Left;
			else if (!ToDelete->m_Left && ToDelete->m_Right)
				NodeToModify = ToDelete->m_Right;
		}

		// Returns true if item was inserted
		bool Insert(NodePtr_t & InsertAt, const Key_t & Key, Value_t & Value)
		{
			if ( Key == InsertAt->m_Key ) throw Exceptions::XKeyNotUnique();
			if ( InsertHelper(InsertAt->m_Left, Key, InsertAt->m_Key, Value, std::less<Key_t>()) ) return true;
			if ( InsertHelper(InsertAt->m_Right, Key, InsertAt->m_Key, Value, std::greater<Key_t>()) ) return true;
			return false;
		}

		// Returns true if item was inserted
		template<typename Comparison_t>
		bool InsertHelper(NodePtr_t & InsertAt, const Key_t & Key, const Value_t & NodeKey, Value_t & Value, Comparison_t Comparator)
		{
			if (Comparator(Key, NodeKey))
			{
				if (InsertAt)
					return Insert(InsertAt, Key, Value);
				InsertAt = std::make_shared<Node_t>(Key, Value);
				return true;
			}
			return false;
		}

		std::pair<NodePtr_t, NodePtr_t> Find(const Key_t & Key, NodePtr_t & NodeToSearch, NodePtr_t & PrevNode)
		{
			if (!NodeToSearch) throw Exceptions::XKeyNotFound();
			if (Key == NodeToSearch->m_Key)
				return std::make_pair(NodeToSearch, PrevNode);
			else if (Key < NodeToSearch->m_Key)
				return Find(Key, NodeToSearch->m_Left, NodeToSearch);
			else if (Key > NodeToSearch->m_Key)
				return Find(Key, NodeToSearch->m_Right, NodeToSearch);
			assert(false);
			throw std::runtime_error("Unknown internal error"); // Silence compiler warnings
		}

		NodePtr_t m_Root;
	};
}

#endif