Binary tree with C++11 smart pointers
Unless I missed something, it appears that bool rbtree&lt;K, D&gt;::insert(K&amp; key, D&amp; data) always returns true. It is quite misleading. If there is no way for this function to ever return anything but true, you could as well get rid of the bool return type.

Also, I propose a different approach than Loki's one for the default constructors of rbnode: you can use in-class members initializers for the default values:

struct rbnode
{
    node_ptr left { nullptr };
    node_ptr right { nullptr };
    rbnode *parent { nullptr };
    enum { Red, Black } color = Red;
    D data;
    K key;

    // Etc...
};


This way, your default constructor can be reduced to its simplest form:

rbnode() = default;


And the "default" values from the in-class member initializers will also be used to automatically initialize non-initialized members in the other constructors:

rbnode(K k, D d):
    data{d},
    key{k}
{}

rbnode(K k, D d, rbnode* p):
    parent{p},
    data{d},
    key{k}
{}


Note that I also used list initialization for some of the in-class members initializers and for the constructor initialization list. List initialization can help to avoid some problems related to implicit narrowing conversions of values.