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.

• Peilonrayz: Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers .
• lisovskey: @Peilonrayz Will you let me slightly update not mentioned parts of code?
• Peilonrayz: I'd recommend not doing that, but I can't stop you. If I were you, I'd write the code to the best of your abilities, give it a couple of days, go over it again fixing any problems. If you've not changed anything post it as a follow up question.
• lisovskey: @Peilonrayz Forgive me for the first time
• Peilonrayz: I don't know what you want me to forgive... But you're forgiven, :)

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.

• lisovskey: Can you explain why it is a redundant delegation? My private methods are recursive so how should I fix it? About layout: yes, everything is clearly understandable for me, this code is written this way experimentally, and to save some space I had to use XXX_BEGIN. Constructor: okay, it was not a good idea. Iterators and template key: this night I have added these features so my tree became like std::map. almost.
• Incomputable: yes, you're right about recursing functions, but you could still implement them as a loop (I'll remove wrong part in the morning). Ideally it should become like set (I meant that T itself should be a key), but if there is another template parameter for the key, then sure. Also you might want to have a look at red black trees.
• lisovskey: Maybe you'd wish to see the updated version? Waiting for pull request :)
• Incomputable: seems ok. I'll give it closer look tomorrow.

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

• lisovskey: I know all these code conventions, and don't lie to yourself, everything is clear if you just get used to this style and see to the top of the header to figure out what is ANYWAY. If not, so sorry, I've asked about logic but not about code conventions.
• miscco: The point about code style is that you should NOT have to get used to it. That is literally the only reason there are code styles.
• lisovskey: Okay I understand it. What can you propose instead leading underscores?
• Loki Astari: @lisovskey not a leading underscore. There is no need for it.
• Loki Astari: Get rid of all those macros at the top. It just makes the code unreadable.

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.