Here is an implementation of a red black tree that I made. I am pretty sure it's working fine though I may have overlook something. How can I improve it in any way possible?Interface:#include <functional>#include <utility>#include <iostream>#include <stack>template <typename K , typename D, typename Func = std::less<K>>class RBTree {public:    RBTree();    RBTree(Func);    ~RBTree();    bool add(const K&, const D&);    bool add(K&&, const D&);    bool add(const K&, D&&);    bool add(K&&, D&&);    bool remove(const K& key, D&);        std::pair<K,D> get_min() const;    std::pair<K,D> get_max() const;    bool get(const K&, D&) const;    template<typename Accion>    void in_order_walk(Accion) const;    unsigned cardinality() const;    bool empty() const;    //Test    bool isRedBlackTree() const    {         bool isRedBlack=true;         blackH(root, isRedBlack);        return assertPropery3(root) && isRedBlack && !root->isRed;    } private:    Func cmp;    unsigned size;    struct Node    {        D data;        K key;        bool isRed;        Node  *left;        Node  *rigth;        Node  *p;    };    Node *root;    Node *nil;    Node* find_node(const K&) const;    bool is_left_child(Node* x) const{ return  x == x->p->left;}    bool is_rigth_child(Node* x)const { return x == x->p->rigth;}    void insert_move_up(Node *&x, Node* uncle);    template <typename KK, typename DD>    Node* BST_add(KK&& key, DD&& data);    template <typename KK, typename DD>    Node* BST_add_recursive(KK&& key, DD&& data, Node* p , Node*& node);    void fixed_add(Node* x);    void fixed_remove(Node* x);    template <typename KK, typename DD>    Node* create_node(KK&& key, DD&& data);    void delete_node(Node*);    void delete_node_v2(Node*);    Node* minimun(Node* x) const;    Node* maximun(Node* x) const;    void transplant(Node * x, Node * y);    template <typename ChildA, typename ChildB >    void generic_fixed_delete(Node*& , ChildA, ChildB);    template <typename ChildA, typename ChildB>    void generic_fixed_add(Node*& ,ChildA, ChildB);    template <typename ChildA, typename ChildB >    Node* generic_rotate(Node*,ChildA, ChildB);    template<typename Accion>    void recur_in_order_walk(Node*, Accion) const;            template<typename Accion>    void iter_in_order_walk(Node*, Accion) const;     template<typename Accion>    void stack_in_order_walk(Node*, Accion) const;     template <typename KK, typename DD>    bool generic_add(KK&&, DD&&) ;    void destroy_tree(Node*);    static Node*& left(Node* x){ return x->left;};    static Node*& rigth(Node* x){ return x->rigth; };    //Test        int blackH(Node*, bool& isRedBlack) const;    bool assertPropery3(Node*) const;};Implementation:template<typename K, typename D, typename Func>bool RBTree<K,D,Func>::empty() const{    return root == nil;}template<typename K, typename D, typename Func>RBTree<K,D,Func>::~RBTree(){    destroy_tree(root);    delete nil;}template<typename K, typename D, typename Func>void RBTree<K,D,Func>::destroy_tree(Node* node){    if(node == nil) return;    destroy_tree(node->left);    destroy_tree(node->rigth);    delete node;}template<typename K, typename D, typename Func>RBTree<K,D,Func>::RBTree(Func pcmp): cmp(pcmp), nil(new Node{D(),K(), false , nullptr , nullptr, nullptr }){    root = nil;}template<typename K, typename D, typename Func>RBTree<K,D,Func>::RBTree(): RBTree(Func()){}template<typename K, typename D, typename Func>unsigned RBTree<K,D,Func>::cardinality() const{    return size;}template<typename K, typename D, typename Func>template <typename ChildA, typename ChildB >typename RBTree<K,D,Func>::Node* RBTree<K,D,Func>::generic_rotate(Node* x,ChildA childA, ChildB childB){    Node *y=  childB(x);    childB(x) = childA(y);    if(childA(y)!=nil)         childA(y)->p= x;    if(x->p== nil)        root = y;    else if(x == childA(x->p))    childA(x->p) = y;    else    childB(x->p) = y;    y->p =x->p;    childA(y) = x;    x->p= y;    return y;}template <typename K, typename D, typename Func>template<typename KK, typename DD>bool RBTree<K,D, Func>::generic_add(KK&& key, DD&& data){    Node *newN=  BST_add_recursive    (        std::forward<KK>(key),          std::forward<DD>(data),         nil, root    );    bool isAdded = newN!=nullptr;    if(isAdded) fixed_add(newN);    return isAdded;}template <typename K, typename D, typename Func>bool RBTree<K,D, Func>::add(const K& key, const D& data){    return generic_add(const_cast<K&>(key), const_cast<K&>(data));}template <typename K, typename D, typename Func>bool RBTree<K,D, Func>::add(K&& key, const D& data){    return generic_add(std::move(key), const_cast<K&>(data));}template <typename K, typename D, typename Func>bool RBTree<K,D, Func>::add(const K& key, D&& data){    return generic_add(const_cast<K&>(key), std::move(data));}template <typename K, typename D, typename Func>bool RBTree<K,D, Func>::add(K&& key, D&& data){    return generic_add(std::move(key), std::move(data));}template <typename K, typename D, typename Func>std::pair<K,D> RBTree<K,D, Func>::get_min() const{    if(empty()) throw std::underflow_error(underflow);    auto min = minimun(root);    return std::pair<K,D>( min->key, min->data);}template <typename K, typename D, typename Func>std::pair<K,D> RBTree<K,D, Func>::get_max() const{    if(empty()) throw std::underflow_error(underflow);    auto min = maximun(root);    return std::pair<K,D>( min->key, min->data);}template <typename K, typename D, typename Func>bool RBTree<K,D, Func>::get(const K& key, D& result) const{    Node* resultN = find_node(key);    bool found = resultN!=nullptr;      if(found) result = resultN->data;    return found;}template <typename K, typename D, typename Func>template <typename KK, typename DD>typename RBTree<K,D, Func>::Node* RBTree<K,D, Func>::BST_add_recursive(KK&& key, DD&& data, Node* p , Node*& node){    if(node == nil)     {        node= create_node(std::forward<KK>(key) , std::forward<DD>(data));        node->p = p;        ++size;        return node;    }    if(cmp(key, node->key))         return BST_add_recursive(key, data, node , node->left);    else if(cmp(node->key , key))        return BST_add_recursive(key, data, node , node->rigth);    return nullptr;}template <typename K, typename D, typename Func>template <typename KK, typename DD>typename RBTree<K,D, Func>::Node* RBTree<K,D, Func>::BST_add(KK&& key, DD&& data){       Node *node= root, *p= nil;    while(node !=nil)    {        p= node;        if(cmp(node->key, key))            node= node->rigth;        else if(cmp(key,node->key))            node = node->left;        else return nullptr;    }    auto newN = create_node(std::forward<KK>(key) , std::forward<DD>(data));       if(root == nil)         root = newN;    else if(cmp(p->key, key))         p->rigth= newN;    else p->left= newN;    newN->p = p;    ++size;    return newN;}template <typename K, typename D, typename Func>void RBTree<K,D, Func>::fixed_add(Node* x) {       while(x->p->isRed)    {                if(is_left_child(x->p))            generic_fixed_add(x, left,rigth);         else            generic_fixed_add(x, rigth, left);    }    root->isRed= false;}template <typename K, typename D, typename Func>template <typename KK, typename DD>typename RBTree<K,D, Func>::Node* RBTree<K,D, Func>::create_node(KK&& key, DD&& data){    return new Node{ std::forward<KK>(data), std::forward<DD>(key), true, nil, nil, nil};}template <typename K, typename D, typename Func>void RBTree<K,D, Func>::insert_move_up(Node *&x, Node* uncle){    x->p->p->isRed= true;    uncle->isRed = false;    x->p->isRed = false;    x = x->p->p;}template <typename K, typename D, typename Func>typename RBTree<K,D, Func>::Node* RBTree<K,D, Func>::minimun(Node* x) const{    while(x->left!=nil)        x = x->left;    return x;}template <typename K, typename D, typename Func>typename RBTree<K,D, Func>::Node* RBTree<K,D, Func>::maximun(Node* x) const{    while(x->rigth!=nil)        x = x->rigth;    return x;}template <typename K, typename D, typename Func>template<typename Accion>void RBTree<K,D, Func>::in_order_walk(Accion accion) const{    iter_in_order_walk(root,accion);}template <typename K, typename D, typename Func>template<typename Accion>void RBTree<K,D, Func>::recur_in_order_walk(Node* node, Accion accion) const{    if(node == nil) return;    recur_in_order_walk(node->left, accion);    accion(node->key , node->data);    recur_in_order_walk(node->rigth, accion);}template <typename K, typename D, typename Func>template<typename Accion>void RBTree<K,D, Func>::iter_in_order_walk(Node* node, Accion accion) const{    Node* min = minimun(node);    while(min != node->p)    {        accion(min->key, min->data);        if(min->rigth!= nil)            min = minimun(min->rigth);        else        {            while(min->p && is_rigth_child(min))                min = min->p;            min= min->p;        }    }} template <typename K, typename D, typename Func>template<typename Accion>void RBTree<K,D, Func>::stack_in_order_walk(Node* n, Accion accion) const{    std::stack<Node*> s;     s.push(nullptr);    s.push(nullptr);    while(!s.empty())    {        while(n!=nil)        {            s.push(n->rigth);            s.push(n);            n = n->left;        }        if((s.top()!=nullptr))            accion(s.top()->key, s.top()->data);        s.pop();        n = s.top();        s.pop();    }} template <typename K, typename D, typename Func>void RBTree<K,D, Func>::delete_node_v2(Node* z){    auto x = z->rigth, y=z;    if(z->left == nil)        transplant(z, x);    else if(z->rigth == nil)        transplant(z, x = z->left);    else    {        y= minimun(z->rigth);        x= y->rigth;        z->data = std::move(y->data);        z->key = std::move(y->key);        transplant(y, x);    }    if(!y->isRed) fixed_remove(x);    --size;    delete y;}template <typename K, typename D, typename Func>void RBTree<K,D, Func>::delete_node(Node* z) {    auto x = z->rigth, y=z;    bool originalColor = z->isRed;    if(z->left == nil)        transplant(z, x);    else if(z->rigth == nil)        transplant(z, x = z->left);    else    {        y= minimun(z->rigth);        originalColor = y->isRed;        x= y->rigth;        if(y->p == z)            x->p = y;        else        {            transplant(y,y->rigth);            y->rigth = z->rigth;            y->rigth->p = y;        }        transplant(z,y);        y->left= z->left;        y->left->p= y;        y->isRed= z->isRed;    }    if(!originalColor) fixed_remove(x);    --size;    delete z;}template <typename K, typename D, typename Func>void RBTree<K,D, Func>::transplant(Node * x, Node * y){    if(x->p == nil) root= y;    else if(is_left_child(x))        x->p->left= y;    else x->p->rigth= y;    y->p= x->p;}template <typename K, typename D, typename Func>void RBTree<K,D, Func>::fixed_remove(Node* x){    while(x!= root && !x->isRed)    {                if(is_left_child(x))            generic_fixed_delete(x, left, rigth);        else            generic_fixed_delete(x, rigth, left);    }    x->isRed = false;}template <typename K, typename D, typename Func>template <typename ChildA, typename ChildB >void RBTree<K,D, Func>::generic_fixed_delete(Node*& x, ChildA childA, ChildB childB){    Node *w= childB(x->p);    if(w->isRed)    {        std::swap( w->isRed, x->p->isRed);        generic_rotate(x->p, childA, childB);        w = childB(x->p);    }    if(!w->left->isRed && !w->rigth->isRed)    {        w->isRed = true;        x = x->p;    }    else    {           if (!childB(w)->isRed)        {            std::swap(w->isRed, childA(w)->isRed);            w = generic_rotate(w, childB, childA);           }        w->isRed= x->p->isRed;        x->p->isRed = false;        childB(w)->isRed = false;        generic_rotate(x->p, childA, childB);        x =root;    }}template <typename K, typename D, typename Func>typename RBTree<K,D, Func>::Node* RBTree<K,D, Func>::find_node(const K& key) const{    Node *node = root;    while(node!= nil)    {        if(cmp(key, node->key))            node= node->left;        else if (cmp(node->key, key))            node = node->rigth;        else return node;    }    return node;}template <typename K, typename D, typename Func>bool RBTree<K,D, Func>::remove(const K& key, D& data){    auto node= find_node(key);    bool exist = node !=nil;    if(exist)    {        data = node->data;        delete_node_v2(node);    }    return exist;}template <typename K, typename D, typename Func>template <typename ChildA, typename ChildB >void RBTree<K,D, Func>::generic_fixed_add(Node*& x ,ChildA childA ,ChildB childB){    Node* uncle = childB(x->p->p);    if(uncle->isRed)        insert_move_up(x, uncle);    else    {        if(x == childB(x->p))             generic_rotate(x = x->p, childA, childB);        x->p->p->isRed = true;           generic_rotate(x->p->p, childB, childA)->isRed =false;    }}//testtemplate <typename K, typename D, typename Func>bool RBTree<K,D, Func>::assertPropery3(Node *node) const{    if(node == nil) return true;    return !node->isRed || (node->left->isRed && node->rigth->isRed)            && assertPropery3(node->left) && assertPropery3(node->rigth);}//testtemplate<typename K, typename D, typename Func>int RBTree<K,D, Func>::blackH(Node* node, bool &isRedBlack) const{    if(node == nil) return 1;    auto left = blackH(node->left, isRedBlack);    auto rigth = blackH(node->rigth, isRedBlack);    isRedBlack= isRedBlack && left == rigth;     return  (node->isRed? 0 : 1)            + std::max(left, rigth);}
Red-Black Tree (2-3-4 node tree) map implementation
c++;performance;c++11;tree