2
\$\begingroup\$

The BST below slightly different from the ones I commonly see on here in that it uses std::unique_ptr to manage the memory. Thoughts?

#include <algorithm>
#include <cassert>
#include <memory>


template <typename KeyType, typename ValueType>
struct BSTNode
{
    BSTNode(KeyType const &key, ValueType const &value) : key(key), value(value) { }


    static BSTNode *find_min(BSTNode *root)
    {
        while (root->left_child != nullptr) {
            root = root->left_child.get();
        }
        return root;
    }


    static BSTNode *find_max(BSTNode *root)
    {
        while (root->right_child != nullptr) {
            root = root->right_child.get();
        }
        return root;
    }


    static bool is_left_child(BSTNode *node)
    {
        return (node->parent != nullptr) && (node->parent->left_child.get() == node);
    }


    static bool is_right_child(BSTNode *node)
    {
        return (node->parent != nullptr) && (node->parent->right_child.get() == node);
    }


    static BSTNode *next_larger(BSTNode *node)
    {
        if (node->right_child != nullptr) {
            return find_min(node->right_child.get());
        }        

        if (is_left_child(node)) {
            return node->parent;
        }

        while (is_right_child(node)) {
            node = node->parent;
        }

        return node->parent;
    }


    static BSTNode *next_smaller(BSTNode *node)
    {
        if (node->left_child != nullptr) {
            return find_max(node->left_child.get());
        }        

        if (is_right_child(node)) {
            return node->parent;
        }

        while (is_left_child(node)) {
            node = node->parent;
        }

        return node->parent;
    }


    KeyType key;
    ValueType value;

    BSTNode *parent;
    std::unique_ptr<BSTNode> left_child;
    std::unique_ptr<BSTNode> right_child;
};


template <
    typename KeyType, 
    typename ValueType, 
    typename Compare = std::less<KeyType>>
class BinarySearchTree
{
public:
    using Node = BSTNode<KeyType, ValueType>;


    BinarySearchTree() = default;


    ValueType &operator[](KeyType const &key) 
    {
        if (root_ == nullptr) {
            root_ = std::make_unique<Node>(key, ValueType());
            root_->parent = nullptr;
            return root_->value;
        }

        Node *parent, *node;
        std::tie(parent, node) = find(key, root_.get());

        if (node != nullptr) {
            return node->value;
        }

        std::unique_ptr<Node> &node_ptr = compare_(parent->key, key) ? 
            parent->right_child : 
            parent->left_child;

        node_ptr = std::make_unique<Node>(key, ValueType());
        node_ptr->parent = parent;
        return node_ptr->value;
    }


    std::unique_ptr<Node> remove(KeyType const &key) 
    {
        Node *parent, *node;
        std::tie(parent, node) = find(key, root_.get());

        if (node == nullptr) {
            return nullptr;
        }

        if (node == root_.get()) {
            assert(parent == nullptr);
            return remove_from_unique_ptr(root_, nullptr);
        }

        return remove_has_parent(node, parent);
    }

private:

    // Return pair of <parent, node>
    std::pair<Node*, Node*> find(KeyType const &key, Node *node) 
    {
        Node *parent = node->parent;

        while (node != nullptr) {
            if (node->key == key) {
                break;
            } 

            parent = node;

            if (compare_(parent->key, key)) {
                node = parent->right_child.get();
            } else {
                node = parent->left_child.get();
            }
        }

        return { parent, node };
    }


    std::unique_ptr<Node> remove_has_parent(Node *next, Node *parent)
    {
        std::unique_ptr<Node> &next_ptr = Node::is_right_child(next) ? 
            parent->right_child : 
            parent->left_child;

        return remove_from_unique_ptr(next_ptr, parent);       
    }


    std::unique_ptr<Node> remove_from_unique_ptr(std::unique_ptr<Node> &node_ptr, Node *parent)
    {
        std::unique_ptr<Node> result = std::move(node_ptr);
        result->parent = nullptr;

        if (result->left_child == nullptr) {
            if (result->right_child == nullptr) {
                return std::move(result);
            } else { 
                node_ptr = std::move(result->right_child);
            }
        } else {
            if (result->right_child == nullptr) {
                node_ptr = std::move(result->left_child);
            } else {
                Node *replacement = Node::next_larger(result.get());
                node_ptr = remove_has_parent(replacement, replacement->parent);
                node_ptr->right_child = std::move(result->right_child);
                node_ptr->left_child = std::move(result->left_child);
                node_ptr->right_child->parent = node_ptr.get();
                node_ptr->left_child->parent = node_ptr.get();
            }
        }

        node_ptr->parent = parent;
        return result;
    }

    std::unique_ptr<Node> root_;
    Compare compare_;
};

#endif 
\$\endgroup\$
3
\$\begingroup\$

Overall that seems needlessly complex.

Design

You return a value object even if you don't find the key in the tree. That seems funny. Especially since you must construct the value using the default constructor and thus your value type must be default constructible.

Most containers when you search them return an iterator. If the object is not in the container then it will return an iterator that equals end() so that you can check to see if the value was found.

Code Design

There is no need to expose BSTNode. This is an implementation detail that you leaking to the user. You should hide this and make it a private member of the class.

When adding to the tree you only use copy semantics (on the value). You should look at using move semantics (on the value) to make the code more efficient.

As a side note: because you use unique_ptr your tree itself is not copyable but is movable. Is this a desired trait? Must containers are both copyable and movable.

Side Note

Note all the methods in BSTNode are used.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.