Skip to main content
2 of 4
added 125 characters in body
lightning_missile
  • 2.7k
  • 2
  • 23
  • 40

Recursive binary search tree without iterators

Please review my BST.

//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 improve this code?

lightning_missile
  • 2.7k
  • 2
  • 23
  • 40