1
\$\begingroup\$

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;

    }
}

//test
template <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);
}
//test
template<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);
}
\$\endgroup\$
  • 2
    \$\begingroup\$ You could put it in a namespace. \$\endgroup\$ – Martin York Sep 18 '15 at 9:18
  • 1
    \$\begingroup\$ Only not in the standard namespace ;) \$\endgroup\$ – glampert Sep 18 '15 at 15:11
  • 1
    \$\begingroup\$ Would it make sense to make bool is_left_child(Node* x) static, or a member-function of the Node? Same for other functions that doesn't need a this pointer to the container for themselves or anything they call. Passing this pointers around will optimize away when functions are inlined, but it would better document which functions can touch the container, and which only look at Nodes. \$\endgroup\$ – Peter Cordes Sep 18 '15 at 22:01
  • \$\begingroup\$ minimun is a typo \$\endgroup\$ – Peter Cordes Sep 18 '15 at 22:12

Your Answer

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

Browse other questions tagged or ask your own question.