Binary Search Tree Implementation C++17

Question

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.

Answer 1

Let me explain the layout problem in much more detail. It will need some of your cooperation.

Some assumptions:

People generally use a wide screen, with 16:9 aspect ratio. Some people use more than one, or some use ultra wide. As a result, to read full horizontal line one will need head movement.

Assuming that average programmers uses chair with some back support, the head is fixed in one position. Navigating through the code vertically requires only mouse scrolling, whereas horizontal navigation requires head movement. Moving head is arguably much harder than slightly moving a finger. Also, muscles of a finger are much more suited to extensive movement, unlike neck.

Code Review:

• Weird usage of BEGIN and END

XXX_BEGIN (pun not intended) is usually used in some standard library implementation. Though the way they use it is very different. The macro is usually a product of some concatenation of current version, current ABI (not API!) version and what not. namespace xxx reads much better and less diverts with the surrounding.

• No possible way to safely iterate a tree

Usually people would want to just iterate the tree. Currently there is no straightforward way to do it (well, one can keep increasing key while optional doesn't contain value), but if someone removes a node, it won't be possible to iterate it in a safe manner at all. I recommend providing an in-order traversal iterator. Thus, traversing it becomes much like traversing a set, because in-order traversal means that elements will come out ordered.

• Lost and forgotten constructor

  Tree(const int key, const T& value) : root{ new Node{ pair{ key, value } } } {}
  

The constructor looks really weird. I'd expect at least std::initializer_list based one and one with ranges denoted by iterators. Not to be offensive, but the constructor made my day.

Better approach:

I think that using int as a key is not a good idea. It would be better to just use the T objects for ordering and layout. Usually access in C++ is done by iterators, for which most of the data structures are optimized for in standard library implementations. If being and end are provided, one can just use std::advance<>() or std::next<>() to make pseudo index based access.

Also the recursion could be transformed into a loop, but that might be slightly more costly in engineering costs.

Answer 2

That code makes my eyes bleed.

1. What is the purpose of the macros. They are completely useless and even worse obfuscating the real code. Anyone reading the code will wonder what ANYWAY and THEN are. Just burn them with fire.

2. Do not put if else and friends on the same line as the body. This is a terrible practice that renders code flow completely unreadable. Is this a strange condition, a long statement. Are there multiple statements. It is just a mess. One statement one line.

3. As far as i know leading underscores are illegal, so maybe just depend on your namespace

Answer 3

Point of fact, underscores are not illegal for identifiers, and macros are fine if they make sense. It's unclear what the macro's are attempting to accomplish, so a comment paragraph on the top about the macros would help.

http://en.cppreference.com/w/cpp/language/identifiers

I think it's readable.