//I don't know what to return when key is not found, so throw std::runtime_error()
//this code does not have handwritten copy/move/destruct because I think unique_ptr already handled the node pointers
template<typename T>
using Ptr = std::unique_ptr<T>;
template<typename K, typename V>
class Bst {
struct Node {
K key;
V val;
std::size_t n;
Ptr<Node> left;
Ptr<Node> right;
Node(const K& k, const V& v, const std::size_t& s) : key(k), val(v), n(s), left(nullptr), right(nullptr) { }
};
Ptr<Node> root;
public:
Bst() :root{nullptr} { }
std::size_t size() {
return size(root);
}
std::size_t size(Ptr<Node>& t) {
return (t == nullptr) ? 0 : t->n;
}
void insert(const K& k, const V& v) {
root = insert(root,k,v);
}
Ptr<Node> insert(Ptr<Node>& t, const K& k, const V& v) {
if (t == nullptr) {
Ptr<Node> node(new Node(k,v,1));
return node;
}
if (k < t->key) {
t->left = insert(t->left,k,v);
} else if (k > t->key) {
t->right = insert(t->right,k,v);
} else {
t->val = v;
}
t->n = size(t->left)+size(t->right)+1;
return std::move(t);
}
V& operator[](const K& k) {
return get(root,k);
}
V& get(Ptr<Node>& t, const K& k) {
if (t == nullptr) {
t = insert(t,k,{});
return t->val;
}
if (k < t->key) {
return get(t->left,k);
} else if (k > t->key) {
return get(t->right,k);
} else {
return t->val;
}
}
K min() {
check(root);
return min(root)->key;;
}
Ptr<Node>& min(Ptr<Node>& t) {
if (t->left == nullptr) {
return t;
}
return min(t->left);
}
K max() {
check(root);
return max(root)->key;
}
Ptr<Node>& max(Ptr<Node>& t) {
if (t->right == nullptr) {
return t;
}
return max(t->right);
}
void remove_min() {
check(root);
root = remove_min(root);
}
Ptr<Node> remove_min(Ptr<Node>& t) {
if (t->left == nullptr) {
return std::move(t->right);
}
t->left = remove_min(t->left);
t->n = size(t->left)+size(t->right)+1;
return std::move(t);
}
void remove_max() {
check(root);
root = remove_max(root);
}
Ptr<Node> remove_max(Ptr<Node>& t) {
if (t->right == nullptr) {
return std::move(t->left);
}
t->right = remove_max(t->right);
t->n = size(t->left)+size(t->right)+1;
return std::move(t);
}
void remove(K k) {
root = remove(root, k);
}
Ptr<Node> remove(Ptr<Node>& t, K k) {
check(t);
if (k < t->key){
t->left = remove(t->left, k);
} else if (k > t->key){
t->right = remove(t->right, k);
} else {
if (t->right == nullptr) {
return std::move(t->left);
}
if (t->left == nullptr) {
return std::move(t->right);
}
Ptr<Node> d = std::move(t);
t = std::move(min(d->right));
t->right = remove_min(t);
t->left = std::move(d->left);
}
t->n = size(t->left)+size(t->right)+1;
return std::move(t);
}
void traverse() {
traverse(root);
}
void traverse(Ptr<Node>& t) {
if (t == nullptr) {
return;
}
traverse(t->left);
std::cout << t->key << " " << t->val << '\n';
traverse(t->right);
}
private:
void check(Ptr<Node>& t) {
if (t == nullptr) {
throw std::runtime_error("No node");
}
}
};
How is my usage of std::unique_ptr() and std::move()? How can I improvleimprove this code?
