红黑树实现

Question

这是我计划在一个小的个人项目中使用的一棵红黑树的实现。它工作得很好，但是我不确定代码是否非常好，因为我只是个初学者，而且插入速度比我发现的这里 (在几次插入之后就停止工作)慢了4倍。

我想知道我是否做了一些不必要的事情来减缓算法的速度，还是因为我的节点也有键而不是数据。如有任何建议和更正，我将不胜感激。

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

发行

三/五

规则

你不遵守三(或五)的规则。因此，您的代码很容易中断。您知道编译器为您生成复制构造函数和赋值操作符吗？编译器生成的版本不能很好地处理拥有的原始指针(您的是自己的，因为您定义了析构函数)。

您可以使用Zero规则来帮助您(通过使用智能指针)。但就我个人而言，我认为在构建容器时，您应该执行三条规则。

运动对象

您的容器拥有数据(和键)的所有权。它通过复制传递的对象来做到这一点。通过正确地在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

通用评论

避免下划线

避免将下划线作为标识符中的第一个字符。规则是复杂的，甚至那些认为自己知道规则的人也会犯错。

你的确搞错了：

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

所有这些成员名称都保留给实现使用。见在C++标识符中使用下划线的规则是什么？。

如果您必须使用前缀来标识成员，那么m_似乎很受欢迎。就我个人而言，我认为使用前缀是不好的风格。如果您需要使用前缀，这意味着您使用的是需要限定的弱成员名。更好的解决方案是使用更有意义的名称。

当我们讨论命名约定时:类型是创建C++最重要的部分，所以请确保读取器很容易识别这些类型。因此，一个非常常见的约定是用一个初始大写字母命名用户定义的类型，用一个初始小写字母命名对象(变量/函数)。

当我们还在使用命名约定时：pParent！将类型信息放入名称中对于指针来说不是有用的p。Hungarian Notation被认为是糟糕的实践。它将您铐在特定类型上，从而使您的代码变得脆弱。此外，类型信息在声明时由对象的实际类型表示得非常清楚。

成员初始化的

顺序

对象的成员按照与声明相同的顺序初始化：

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

您在这里的订单与申报顺序不一样。在这种情况下，这不会导致问题，但这是一种混乱和糟糕的做法(编译器应该对此发出警告)。

始终将初始化程序列表按与声明相同的顺序放置。这样，当它确实重要的时候，你可以很容易地发现它。

也像普通变量声明，请初始化每一行一个变量。请记住，您正在编写这段代码，以便其他人(在6个月内可能就是您)能够阅读它。

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

在需要之前不要声明变量。

Node * pNode = _Root;
int Dir;

6行不需要pNode，13行不需要Dir。对于许多类型，这会产生不同的效果，因为构造函数是将要执行的代码。如果您不需要这些变量，则不声明它们是一般规则。而且，从使用的角度看，要使声明保持很长的距离，就很难验证变量的类型。

自文档化代码

我正在努力阅读和理解Insert()。但这并不容易。没有文档，代码也不是以自文档形式编写的。

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

这样读起来更符合逻辑，比如：

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

Answer 2

内存管理：

帮你自己一个忙，用聪明的指点。这样你就不会那么容易地泄露记忆了。此外，我强烈建议您将所有内存存储在树中，并且只存储节点中的链接。

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>>;
};

这可以确保，一旦树超出作用域，所有内存都会被正确地释放。通常在C++中，您应该尽可能避免使用new/delete。

更明确：

Dir = Key > pNode->_Key;

这里有一个布尔值，该布尔值被隐式转换为一个整数，该整数被隐式转换为枚举。直接添加枚举可以提高可读性：

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

使用标准功能：

你在这里做的是一个经典的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;

等于

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;

另一个分支也是如此：

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;

等于

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;

另外，这两个分支都是高度等价的，因此可能只需创建一个指向父/祖父母的临时指针，并简化代码。