btree.cpp

#include <memory>
#include <string>

using std::shared_ptr;
using std::string;

template <typename Value> class BSearchTree {
  struct Node {
    string element;
    Value value;
    std::shared_ptr<Node> left;
    std::shared_ptr<Node> right;
    Node(string elem, std::shared_ptr<Node> l, std::shared_ptr<Node> r)
        : element{std::move(elem)}, left{l}, right{r} {}
    Node(string&& elem, shared_ptr<Node> l, shared_ptr<Node> r)
        : element{std::move(elem)}, left{l}, right{r} {}
  };
  shared_ptr<Node> root;
  void set(const string& element, const Value& value,
              shared_ptr<Node>& tree) {
    if (tree == nullptr) {
      tree.reset(new Node{element, value, nullptr, nullptr});
    } else if (element < tree->element) {
      set(element, value, tree->left);
    } else if (tree->element < element) {
      set(element, value, tree->right);
    }
  }

  void set(string&& element, Value&& value, shared_ptr<Node>& tree) {
    if (tree == nullptr) {
      tree.reset(
          new Node{std::move(element), std::move(value), nullptr, nullptr});
    } else if (element < tree->element) {
      set(std::move(element), std::move(value), tree->left);
    } else if (tree->element < element) {
      set(std::move(element), std::move(value), tree->right);
    }
  }

  shared_ptr<Node> min(shared_ptr<Node> tree) const {
    if (tree == nullptr) {
      return nullptr;
    }
    if (tree->left == nullptr) {
      return tree;
    }
    return min(tree->left);
  }

  shared_ptr<Node> max(shared_ptr<Node> tree) const {
    if (tree != nullptr) {
      while (tree->right != nullptr) {
        tree = tree->right;
      }
    }
    return tree;
  }

  void remove(const string& element, shared_ptr<Node>& tree) {
    if (tree == nullptr) {
      return;
    }
    if (element < tree->element) {
      remove(element, tree->left);
    } else if (tree->element < element) {
      remove(element, tree->right);
    } else if (tree->left != nullptr && tree->right != nullptr) {
      tree->element = min(tree->right)->element;
      remove(tree->element, tree->right);
    } else {
      tree.reset((tree->left != nullptr) ? tree->left : tree->right);
    }
  }

  bool contains(const string& element, shared_ptr<Node> tree) const {
    if (element < tree->element) {
      return contains(element, tree->left);
    }

    if (tree->element < element) {
      return contains(element, tree->right);
    }

    return true;
  }

  Value get(const string& key, shared_ptr<Node> tree) const {
    if (key < tree->element) {
      return get(key, tree->left);
    }
    if (tree->element < key) {
      return get(key, tree->right);
    }
    return tree->value;
  }

 public:
  void remove(const string& element) { remove(element, this); }
  void set(const string& element, const Value& value) {
    set(element, value, this);
  }
  void set(const string&& element, const Value&& value) {
    set(element, value, this);
  }
  Value get(const string& key) { get(key, root); }
  bool contains(const string& element) const { contains(element, root); }
};