Recursive binary search tree - follow-up

Question

This is a follow-up to

changes:

Used raw pointers rather than std::unique_ptr
const correctness
Made variable names more beautiful
implemented at()

How can I improve this code?

template<typename K, typename V>
class binarySearchTree {

    struct Node {
        K key;
        V val;
        Node* left;
        Node* right;
        Node(const K& k, const V& v) : key(k), val(v), left(nullptr), right(nullptr) { }
    };

    void check(Node* node) {
        if (node == nullptr) {
            throw std::runtime_error("No node");
        }
    }

    V& at(Node* node, const K& key) {
        if (node == nullptr) {
            throw std::runtime_error("no node");
        }
        if (key < node->key) {
            return at(node->left,key);
        } else if (key > node->key) {
            return at(node->right,key);
        }
        return node->val;
    }

    V& get(Node*& node, const K& key) {
        if (node == nullptr) {
            node = new Node{key,{}};
            ++n;
            return node->val;
        }
        if (key < node->key) {
            return get(node->left,key);
        } else if (key > node->key) {
            return get(node->right,key);
        } else {
            return node->val;
        }
    }

    Node* min(Node* node) const {
        if (node->left == nullptr) {
            return node;
        }
        return min(node->left);
    }

    Node* max(Node* node) const {
        if (node->right == nullptr) {
            return node;
        }
        return max(node->right);
    }

    Node* remove_min(Node*& node) {
        if (node->left == nullptr) {
            Node* x = node->right;
            delete node;
            --n;
            return x;
        }
        node->left = remove_min(node->left);
        return node;
    }

    Node* remove_max(Node*& node) {
        if (node->right == nullptr) {
            Node* x = node->left;
            delete node;
            --n;
            return x;
        }
        node->right = remove_max(node->right);
        return node;
    }

    Node* remove(Node*& node, K key) {
        check(node);
        if      (key < node->key){
            node->left = remove(node->left,  key);
        } else if (key > node->key){
            node->right = remove(node->right, key);
        } else {
            if (node->right == nullptr) {
                Node* x =  node->left;
                delete node;
                --n;
                return x;
            }
            if (node->left == nullptr) {
                Node* x = node->right;
                delete node;
                --n;
                return x;
            }
            Node* old = node;
            node = min(old->right);
            node->right = remove_min(old->right);
            node->left = old->left;
            delete old;
            --n;
        }
        return node;
    }

    void traverse(Node* node) {
        if (node == nullptr) {
            return;
        }
        traverse(node->left);
        std::cout << node->key << " " << node->val << '\n';
        traverse(node->right);
    }

    void destruct(Node* node) {
        if (node == nullptr) {
            return;
        }
        destruct(node->left);
        destruct(node->right);
        delete node;
    }

    Node* root;
    std::size_t n;

public:

    binarySearchTree() :root{nullptr},n{0} { }
    //no compy/move

    std::size_t size() const {
        return n;
    }

    V& at(const K& key) {
        return at(root,key);
    }

    V& operator[](const K& key) {
        return get(root,key);
    }

    K& min() {
        check(root);
        return min(root)->key;;
    }

    K& max() {
        check(root);
        return max(root)->key;
    }

    void remove_min() {
        check(root);
        root = remove_min(root);
    }

    void remove_max() {
        check(root);
        root = remove_max(root);
    }

    void remove(K key) {
        root = remove(root, key);
    }

    void traverse() {
        traverse(root);
    }

    ~binarySearchTree() {
        destruct(root);
    }

};

If there is no copy/move. Then you should explicitly delete them otherwise the compiler will generate them for you. Currently you are failing the rule of 5. — Loki Astari, Jan 12 at 18:15

Emily L. · Accepted Answer · 2015-01-31 19:38:03Z

In addition to ratchet freak's answer. These private methods:

V& at(Node* node, const K& key)
V& get(Node*& node, const K& key)
Node* min(Node* node) const
Node* max(Node* node) const
Node* remove_min(Node*& node)
Node* remove_max(Node*& node)
Node* remove(Node*& node, K key)
void traverse(Node* node)

can and should easily be reworked into members of Node. Try it and see how much less typing of node-> it will result in.

This method:

void destruct(Node* node)

should really just be the destructor ~Node(), and in ~binarySearchTree() simply call delete root. Calling delete on a null pointer is perfectly fine so you don't even need to check for null here.

So you only really need this:

    ~Node() {
        delete left;
        delete right;
    }

    ~binarySearchTree(){
        delete root;
    }

to clean up after you. Please note that if you do this, you need to completely detach a node from the tree in your remove* methods before deleting it, otherwise the children will go too. But I find this to be better style anyway; detach, re-link tree, then delete.

Also you're being inconsistent with your naming, you have Node and binarySearchTree. Either Node should be node (first letter of first word is lower case), or binarySearchTree should be BinarySearchTree (first letter of all words is upper case). Personally, I prefer the later.

PassingStranger · Answer 2 · 2015-01-13 14:57:31Z

up vote 2 down vote

There are a lot of inconsistency in your code and a few cases where you follow an if-block with something that probably should be in an else if- or else-block.

There are also functions that have return-values that really have nothing to do there.
I'll try to illustrate with the one function I found an actual error in.
The rewrite is as follows.

void remove(Node*& node, const K& key) {
    check(node);
    if (key < node->key) {
        remove(node->left, key);
    } else if (key > node->key) {
        remove(node->right, key);
    } else {
        Node* old = node;
        if (node->right == nullptr) {
            node = node->left;
        } else if (node->left == nullptr) {
            node = node->right;
        } else {
            node = min(old->right);
            // remove_min actually removes the node you just replaced above.
            node->right = // remove_min(old->right);
            node->left = old->left;
        }
        delete old;
        --n;
    }
}

As mentioned above, this function actually removes both the node you want to remove and the node you try to replace it with in the last case.

Fixing that error is something I leave as an exercise.

answered Jan 13 at 14:57

PassingStranger
211

"Fixing that error is something I leave as an exercise." - as you mentioned, I shouldn't use remove_min(old->right); because it will actually delete the node that I will use to replace the deleted node. I never noticed this because this code originally used unique_ptr. To fix, I changed node->right to point to the second smallest key in the right subtree of the deleted node, like this: node->right = old->right->right;. I think it's working correctly. What do you think? – morbidCode Jan 14 at 13:46

That would cut away everything above the node you are moving. The problem is that remove_min actually deletes the node you want to keep. You just want it removed from it's current location in the tree. – PassingStranger Jan 14 at 14:54

"That would cut away everything above the node you are moving." - I don't understand what you mean here. In my code in the comment above, I reset node to point to old->right to replace the deleted node. Then I reset node->right to point to the right subtree of node->right. Can you explain further? – morbidCode Jan 14 at 15:32

After replacing the old node with min(old->right), you still need all other nodes in old->right. All the nodes in old->right->left are missing if you do it that way. You have to actually graft min(old->right)->right all the way down where min(old->right) was. remove_min as a function would work perfectly except for the fact that it deletes the node it is just supposed to remove. – PassingStranger Jan 14 at 17:17

I created a new Node and stored the node returned by remove_min(old->right)'s data to it, like this: node = new Node{min(old->right)->key, min(old->right)->val};. So it doesn't matter when node->right = remove_min(old->right); deletes. What do you think? – morbidCode Jan 15 at 15:46

| show 1 more comment

Emily L. · Answer 3 · 2015-01-13 11:51:58Z

Why not make traverse() take a functor that accepts key/value so that you can do stuff on your traversal?

void traverse(std::function<void(K,V)>& f) {traverse(f, root);}
void traverse(std::function<void(K,V)>& f, Node* node) {
    if (node == nullptr) {
        return;
    }
    traverse(f, node->left);
    f(node->key, node->val);
    traverse(f, node->right);
}

Then printing is simply:

tree.traverse([](K const& k, V const& v){std::cout << k << " " << v << '\n';});

But it can also do other interesting things if need be.

ratchet freak · Answer 4 · 2015-01-12 16:50:45Z

You make a check(Node*) function and then you don't use it in the first method following it; probably an oversight.

You should make const versions of your operator[] and at besides the non-const versions (the idea is that all non-mutating operations should be doable with a const tree):

V& at(const K& key) {
    return at(root,key);
}

const V& at(const K& key) const {
    return at(root,key);//also make a const at
}

V& operator[](const K& key) {
    return get(root,key);
}

const V& operator[](const K& key) const {
    return get(root,key);//also make a const get
}

min and max should be const and return a const reference (allowing users to change the key like that would invalidate the structure of the tree).

const K& min() const {
    check(root);
    return min(root)->key;
}

const K& max() const {
    check(root);
    return max(root)->key;
}

asked	7 months ago
viewed	671 times
active	7 months ago

current community

your communities

more stack exchange communities

Recursive binary search tree - follow-up

4 Answers 4

Your Answer

Not the answer you're looking for? Browse other questions tagged c++ c++11 data-structures tree or ask your own question.

Visit Chat

Linked

Hot Network Questions

current community

your communities

more stack exchange communities

Recursive binary search tree - follow-up

4 Answers 4

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++ c++11 data-structures tree or ask your own question.

Visit Chat

Linked

Related

Hot Network Questions