I have just implemented a simple model of binary search tree. It can store template values with unique keys. All implementation is encapsulated so there's no access to nodes.
#define RZD_BEGIN namespace rzd {
#define RZD_END }
#define ANYWAY
#define THEN
#include <list>
#include <memory>
#include <optional>
RZD_BEGIN
using std::list;
using std::optional;
// binary search tree
template <typename T>
class Tree
{
// prototype
struct Node;
// aliases
using pointer = std::shared_ptr<Node>;
using pair = std::pair<int, T>;
// unit of tree
struct Node {
pair data;
pointer left;
pointer right;
Node(pair data) : data{ data }, left{ nullptr }, right{ nullptr } {}
};
// start point
pointer root;
// IF CONDITION ACTION
void _insert(pointer& leaf, const pair data)
{
if (!leaf) leaf = pointer{ new Node{ data } };
else if (data.first < leaf->data.first) _insert(leaf->left, data);
else if (data.first > leaf->data.first) _insert(leaf->right, data);
else leaf->data.first = data.first;
}
pointer _find(const pointer& leaf, const int key) const
{
if (!leaf || leaf->data.first == key) return leaf;
else if (key < leaf->data.first) return _find(leaf->left, key);
else return _find(leaf->right, key);
}
pointer _minimum(const pointer& leaf) const
{
if (leaf->left) return _minimum(leaf->left);
else return leaf;
}
void _remove(pointer& leaf, const int key)
{
if (!leaf) return;
else if (key < leaf->data.first) _remove(leaf->left, key);
else if (key > leaf->data.first) _remove(leaf->right, key);
else if (leaf->left && leaf->right) {
THEN leaf->data.first = _minimum(leaf->right)->data.first;
THEN _remove(leaf->right, leaf->data.first);
}
else if (leaf->left) leaf = leaf->left;
else if (leaf->right) leaf = leaf->right;
else leaf = nullptr;
}
void _clear(pointer& leaf)
{
if (leaf) {
THEN _clear(leaf->left);
THEN _clear(leaf->right);
THEN leaf = nullptr;
}
}
int _size(const pointer& leaf) const
{
if (leaf) return _size(leaf->left) + 1 + _size(leaf->right);
else return 0;
}
list<pair>& _get_list(const pointer& leaf, list<pair>& list) const
{
if (leaf) {
THEN _get_list(leaf->left, list);
THEN list.push_back(leaf->data);
THEN _get_list(leaf->right, list);
}
ANYWAY return list;
}
public:
// inserts new node with key and value
inline void insert(const int key, const T& value)
{
ANYWAY _insert(root, pair{ key, value });
}
// returns optional value by key
inline optional<T> find(const int key) const
{
if (pointer leaf = _find(root, key)) return { leaf->data.second };
else return {};
}
// removes node by key
inline void remove(const int key)
{
ANYWAY _remove(root, key);
}
inline void clear()
{
ANYWAY _clear(root);
}
// returns number of nodes
inline int size() const
{
ANYWAY return _size(root);
}
// returns sorted list
inline list<pair> get_list() const
{
ANYWAY return _get_list(root, list<pair>());
}
// returns optional value by key
inline optional<T> operator[](const int key)
{
ANYWAY return find(key);
}
// constructors
Tree() : root{ nullptr } {}
Tree(const int key, const T& value) : root{ new Node{ pair{ key, value } } } {}
};
RZD_END
I use optional
class from C++17 for find
method. It supported by gcc 7.1 and latest vs compiler. Usage:
rzd::Tree<std::string> tree;
tree.insert(42, "root");
tree.insert(41, "foo");
tree.insert(43, "bar");
std::cout << tree[42].value() << "\n";
std::cout << tree.find(41).value() << "\n";
std::cout << tree[43].value() << "\n";
std::cout << tree << "\n";
tree.remove(42);
std::cout << tree[42].value_or("not found") << "\n";
I'm interested in bug fixes, optimisations, std
library usages and maybe better solutions for storing data.