Red-Black Tree Implementation

Question

This is my implementation of a red-black tree that I'm planning to use in a little personal project. It works fine, however I'm not sure that the code is very good as I'm only a beginner, and insertions are 4x slower than in a broken implementation I found here (it stops working after a few insertions).

I was wondering if I did something unnecessary that slows down the algorithm or is it just because my nodes also have keys instead of just data. I'd greatly appreciate any suggestions and corrections.

enum Color { Red = 0, Black };

template <typename TKey, typename TData>
class RBTree
{
public:
    RBTree();
    ~RBTree();
    void Insert(TKey Key, TData Data);
    void Delete(TKey Key);
    TData * Find(TKey Key);
private:
    struct Node
    {
        Node(const TKey & Key, const TData & Data, Node * Parent);
        ~Node();
        Color _Color;
        Node * _Link[2];
        Node * _Parent;
        TKey _Key;
        TData _Data;
    };
    Node * _Root;
};


template<typename TKey, typename TData>
inline RBTree<TKey, TData>::RBTree() :
    _Root(nullptr)
{

}

template<typename TKey, typename TData>
inline RBTree<TKey, TData>::~RBTree()
{
    delete _Root;
}

template<typename TKey, typename TData>
inline void RBTree<TKey, TData>::Insert(TKey Key, TData Data)
{
    Node * pNode = nullptr;
    Node * pParent = nullptr;
    Node * pUncle = nullptr;
    Node * pGrandparent = nullptr;
    Node * T = nullptr;
    int Dir;
    int PDir;
    if (!_Root)
    {
        _Root = new Node(Key, Data, nullptr);
        _Root->_Color = Black;
    }
    else
    {
        pNode = _Root;
        while (pNode)
        {
            pParent = pNode;
            Dir = Key > pNode->_Key;
            pNode = pNode->_Link[Dir];
        }
        pParent->_Link[Dir] = new Node(Key, Data, pParent);
        pNode = pParent->_Link[Dir];

        TKey k;
        TData d;
        Node * n;
        while (pNode->_Parent && pNode->_Parent != _Root && pParent->_Color == Red)
        {
            pGrandparent = pParent->_Parent;
            PDir = pParent->_Data > pGrandparent->_Data;
            pUncle = pGrandparent->_Link[!PDir];

            if ((pUncle != nullptr) && (pUncle->_Color == Red))
            {
                pGrandparent = pParent->_Parent;
                PDir = pParent->_Data > pGrandparent->_Data;
                pUncle = pGrandparent->_Link[!PDir];

                pParent->_Color = Black;
                pUncle->_Color = Black;
                pGrandparent->_Color = Red;

                pNode = pGrandparent;
            }
            else if ((pGrandparent->_Link[!PDir] == nullptr) || (pGrandparent->_Link[!PDir]->_Color == Black))
            {
                if (Dir != PDir)
                {
                    k = pGrandparent->_Key;
                    d = pGrandparent->_Data;
                    pGrandparent->_Key = pNode->_Key;
                    pGrandparent->_Data = pNode->_Data;
                    pNode->_Key = k;
                    pNode->_Data = d;
                    n = pGrandparent->_Link[!PDir];
                    pGrandparent->_Link[!PDir] = pNode;
                    pNode->_Parent = pGrandparent;
                    pNode->_Link[Dir] = n;
                    if (n)
                    {
                        n->_Parent = pNode;
                    }
                    pParent->_Link[Dir] = nullptr;
                }
                else
                {
                    k = pGrandparent->_Key;
                    d = pGrandparent->_Data;
                    pGrandparent->_Key = pParent->_Key;
                    pGrandparent->_Data = pParent->_Data;
                    pParent->_Key = k;
                    pParent->_Data = d;
                    n = pGrandparent->_Link[!PDir];
                    pGrandparent->_Link[!PDir] = pParent;
                    pGrandparent->_Link[PDir] = pNode;
                    pNode->_Parent = pGrandparent;
                    pParent->_Link[Dir] = pParent->_Link[!Dir];
                    pParent->_Link[!Dir] = n;
                    if (n)
                    {
                        n->_Parent = pParent;
                    }
                }
            }
            pNode = pGrandparent;
            pParent = pNode->_Parent;
        }
        _Root->_Color = Black;
    }
}

template<typename TKey, typename TData>
inline void RBTree<TKey, TData>::Delete(TKey Key)
{

}

template<typename TKey, typename TData>
inline TData *  RBTree<TKey, TData>::Find(TKey Key)
{
    Node * pNode = _Root;
    int Dir;
    if (!_Root)
    {
        return nullptr;
    }
    while (pNode)
    {
        if (Key == pNode->_Key)
        {
            return &pNode->_Data;
        }
        else
        {
            Dir = Key > pNode->_Key;
            pNode = pNode->_Link[Dir];
        }
    }
    return nullptr;
}

template<typename TKey, typename TData>
inline RBTree<TKey, TData>::Node::Node(const TKey & Key, const TData & Data, Node * Parent) :
    _Color(Red), _Parent(Parent), _Link(), _Key(Key), _Data(Data)
{

}


template<typename TKey, typename TData>
inline RBTree<TKey, TData>::Node::~Node()
{
    delete _Link[0];
    delete _Link[1];
}

Answer 1

Issues

Rule of Three/Five

You don't obey the rule of Three (or Five). Thus your code can easily break. Did you know that the compiler generates the copy constructor and assignment operator for you? The compiler-generated version does not work well with owned RAW pointers (yours are owned because you define the destructor).

You can use the rule of Zero to help you out (by using smart pointers). But personally, I think you should implement the rule of three as you are building a container.

Moving objects

Your container takes ownership of the data (and key). It does so by making a copy of the object passed. You could potentially make your code much more efficient by correctly implementing move semantics on your insert:

Insert(K const& key, V const& value);      // The one you implement
Insert(K&& key, V&& value);                // Move the key and value.
template<Args...>
Insert(K const& key, Args... args);        // Build the value in place

General Comments

Avoid underscore

Avoid underscore as the first character in an identifier. The rules are complex and even those that think they know the rules get it wrong.

You do get it wrong:

    Color _Color;
    Node * _Link[2];
    Node * _Parent;
    TKey _Key;
    TData _Data;

All these members names are reserved for use by the implementation. See What are the rules about using an underscore in a C++ identifier?.

If you must use a prefix to identify members then m_ seems popular. Personally, I think using a prefix is bad style. If you need to use a prefix that means you are using weak member names that need to be qualified. A better solution is to use more meaningful names.

While we are on naming conventions: types are the most important part of creating C++, so make sure the types are easily identifiable by the reader. As such, a very common convention is to name user-defined types with an initial uppercase letter and objects (variables/functions) with an initial lowercase letter.

While we are still on naming conventions: pParent!. Putting type information into the name is not useful p for pointer. Hungarian Notation is considered bad practice. It handcuffs you to specific types and thus makes your code brittle. Also type information is expressed very clearly by the actual type of the object when declared.

Order Of Member Initialization

The members of an object are initialized in the same order as declaration:

inline RBTree<TKey, TData>::Node::Node(const TKey & Key, const TData & Data, Node * Parent) :
    _Color(Red), _Parent(Parent), _Link(), _Key(Key), _Data(Data)

Your order here is not the same as the order of declaration. This is not going to cause an issue in this situation but it is untidy and bad practice (any you should have been warned about this by the compiler).

Always put the initializer list in the same order as declaration. That way, when it does matter you can easily spot it.

Also like normal variable declaration, please initialize one variable per line. Remember you are writing this code so that other people (that could be you in 6 months) can read it.

inline RBTree<TKey, TData>::Node::Node(const TKey & Key, const TData & Data, Node * Parent)
    : _Color(Red)
    , _Link()
    , _Parent(Parent)
    , _Key(Key)
    , _Data(Data)
 {}

Don't declare variables until needed.

Node * pNode = _Root;
int Dir;

The pNode is not needed for 6 rows and Dir is not needed for 13 rows. For a lot of types this makes a difference as the constructor is code that will be executed. If you don't need those variables the don't declare them is the general rule. Also keeping the declarations a long way from the point of use makes it hard to verify the types of the variable.

Self-documenting code

I am trying to read and understand the Insert(). But it's not easy going. No documentation and the code is not written as self-documenting either.

    while (pNode->_Parent && pNode->_Parent != _Root && pParent->_Color == Red)

That would be much more logical to read as something like:

    while (grandParentNotBalanced(pNode, pParent)) // Or something.

Answer 2

Memory management:

Do yourself a favor and use smart pointers. That way you cannot leak memory so easily. Also I would strongly suggest that you store all the memory in the tree, and only the links in the nodes.

template <typename TKey, typename TData>
class RBTree
{
public:
    RBTree();
    ~RBTree();
    void Insert(TKey Key, TData Data);
    void Delete(TKey Key);
    TData * Find(TKey Key);
private:

    Node * _Root = nullptr;
    std::vector<std::unique_ptr<node>>;
};

This ensures, that once the tree goes out of scope, all memory is correctly deallocated. Generally in C++, you should avoid new/delete whenever possible.

Be more explicit:

Dir = Key > pNode->_Key;

Here you have a boolean that is implicitly converted to an integer that is implicitly converted to an enumeration. Adding the enumerations directly improves readability:

Dir = Key > pNode->_Key ? Black : Red;

Use standard functionality:

What you are doing here is a classic std:swap

k = pGrandparent->_Key;
d = pGrandparent->_Data;
n = pGrandparent->_Link[!PDir];
pGrandparent->_Key = pNode->_Key;
pGrandparent->_Data = pNode->_Data;
pGrandparent->_Link[!PDir] = pNode;
pNode->_Key = k;
pNode->_Data = d;
pNode->_Link[Dir] = n;
pNode->_Parent = pGrandparent;

Is equivalent to

std::swap(pGrandparent->_Key, pNode->_Key);
std::swap(pGrandparent->_Data, pNode->_Data);
pNode->_Link[Dir] = pGrandparent->_Link[!PDir];
pGrandparent->_Link[!PDir] = pNode;
pNode->_Parent = pGrandparent;

The same goes for the other branch:

k = pGrandparent->_Key;
d = pGrandparent->_Data;
pGrandparent->_Key = pParent->_Key;
pGrandparent->_Data = pParent->_Data;
pParent->_Key = k;
pParent->_Data = d;
n = pGrandparent->_Link[!PDir];
pGrandparent->_Link[!PDir] = pParent;
pGrandparent->_Link[PDir] = pNode;
pNode->_Parent = pGrandparent;
pParent->_Link[Dir] = pParent->_Link[!Dir];
pParent->_Link[!Dir] = n;

Is equivalent to

std::swap(pGrandparent->_Key, pParent->_Key);
std::swap(pGrandparent->_Data, pParent->_Data);
pParent->_Link[Dir] = pParent->_Link[!Dir];
pParent->_Link[!Dir] = pGrandparent->_Link[!PDir];
pGrandparent->_Link[!PDir] = pParent;
pGrandparent->_Link[PDir] = pNode;
pNode->_Parent = pGrandparent;

Also both branches are highly equivalent, so maybe just make a temporary pointer to either parent/grandparent and simplify the code