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