C++红黑树的实现

最近在阅读SGI STL源代码，其中红黑树的实现比较有技术含量，但标准库里面是捆绑了其中的allocator, iterator(Rb_tree专用的)，使用很多模板变量，实现对多种数据类型的处理。这些情况对于有较扎实C++基础的人来说不成问题，但对于一般 初学算法，而又没有太好的C++基础的人来说有点困难。并且SGI STL中的实现代码写得很精巧，节省代码，也高效运行，但会使得功能不够深厚的人读起来还是比较费劲。
这里使用简单的int类型节点，实现红黑树的创建、插入及相关内部操作的功能。目前代码中删除节点及其内部操作功能没有实现。
关于红黑树的五个条件（有的书上说四个，内容是等价的）以及插入节点后的调整，可以参考侯捷先生的《STL源码剖析》，里面有详细的原理介绍。也可以参考 《算法导论》。下面代码可以直接使用运行，经测试正确，代码不追求在物理运行上的效率，尽量把算法步骤表现在代码里，不作过多合并优化，并且已经加上不少 注释，方便阅读。
My_Rb_Tree.h

#pragma once
 
#define node_black true
#define node_red false
 
typedef bool node_color;
typedef int value_type;
 
struct node
{
    node_color color;
    node * left;
    node * right;
    node * parent;
    value_type val;
};
 
class My_Rb_Tree
{
public:
    My_Rb_Tree(void);
    ~My_Rb_Tree(void);
 
    node * InsertUnique(value_type in_val);
    void Erase(node * in_cur);
    node * Find(value_type _val);
 
private:
    node * Root();
    void Init();
    node * CreateNode(value_type _val);
 
    void DestoryNode(node * &_n);
 
    void RotateLeft(node * _cur);
    void RotateRight(node * _cur);
 
    void Rebalance(node * _cur);
    void RebalanceForErase(node * _cur);
 
    node * Insert(node * in_parent, node * in_cur, value_type in_value);
 
private:
    int node_count;
    node * head;
 
};
 

My_Rb_Tree.cpp

/************************************************************************/
/*  @brief Red-Black tree implement.
/*  @author sail2010@163.com
/*  @date 2012.10.12
/*  @time 16:56:37                                       
/************************************************************************/
#include "StdAfx.h"
#include "My_Rb_Tree.h"
#include "assert.h"
 
My_Rb_Tree::My_Rb_Tree(void)
:node_count(0),
head(0)
{
    Init();
}
 
My_Rb_Tree::~My_Rb_Tree(void)
{
}
 
node * My_Rb_Tree::Root()
{
    assert(head);
    if (!head)
    {
        return 0;
    }
    return head->parent;
}
 
void My_Rb_Tree::Init()
{  
    head = CreateNode(0);
    if (!head)
    {
        return;
    }
    head->color = node_red;
    head->left = head;
    head->right = head;
    head->parent = 0;
}
 
node * My_Rb_Tree::CreateNode(value_type _val)
{
    node * n = new node;
    n->parent = 0;
    n->left = 0;
    n->right = 0;
    n->color = node_red;
    n->val = _val;
    return n;
}
 
void My_Rb_Tree::DestoryNode(node * &_n)
{
    delete _n;
    _n = 0;
}
 
void My_Rb_Tree::RotateLeft(node * _cur)
{
    node * _root = Root();
    node * r = _cur->right;
    if (!r)
    {
        return;
    }
 
    if ( _cur ==_root )
    {
        _root = r;
        r->parent = _cur->parent;
        _cur->parent->parent = r;
    }
    else
    {
 
    }
    r->parent = _cur->parent;
    if (_cur->parent->left == _cur)
    {
        r->parent->left = r;
    }
    else
    {
        r->parent->right = r;
    }
 
    _cur->right = r->left;
    if (r->left)
    {  
        _cur->right->parent = _cur;
    }
 
    r->left = _cur;
    _cur->parent = r;
}
void My_Rb_Tree::RotateRight(node * _cur)
{
    node * _root = Root();
    node * l = _cur->left;
    if (!l)
    {
        return;
    }
    if ( _cur == _root )
    {
        _root = l;
        l->parent = _cur->parent;//head
        l->parent->parent = l;// head->parent
    }
    else
    {
 
        l->parent = _cur->parent;
        if (l->parent->left == _cur)
        {
            l->parent->left = l;
        }
        else
        {
            l->parent->right = l;
        }
    }
 
    _cur->left = l->right;
    if (l->right)
    {
        _cur->left->parent = _cur;
    }
 
    l->right = _cur;
    _cur->parent = l;
 
}
 
void My_Rb_Tree::Rebalance(node * _cur)
{
    node * _root = Root();
    _cur->color = node_red;
 
    if (_cur->parent == head) // _cur is root node
    {
        _cur->color = node_black;
        return;
    }
 
    if ( _cur->parent->color == node_black ) // now is balance state.
    {
        return ;
    }
 
    // 根据原来的树是符合红黑规则，祖父节点必定为黑色
    while( (_cur != Root()) && (_cur->parent->color == node_red)) // 当前节点的父节点为红色，违反规则
    {
        if (_cur->parent->parent->left == _cur->parent)  // 父节点为左子节点
        {
            if(_cur->parent->parent->right
                && _cur->parent->parent->right->color == node_red)  // 伯父节点为红
            {
                // 把父节点和伯父节点变成黑色，祖父节点变成红色
                _cur->parent->parent->right->color=node_black;
                _cur->parent->color = node_black;
                _cur->parent->parent->color = node_red;
 
                // 因为祖父节点为红色，需要继续向上测试是否满足规则
                _cur = _cur->parent->parent;
                continue;
            }
            else // 伯父节点为黑或不存在
            {
                if ( _cur == _cur->parent->right )
                {
                    // 以父节点为轴，左旋转后变成两个左外节点连续为红。
                    _cur = _cur->parent;
                    RotateLeft(_cur/*,_root*/);
                }
                // 改变颜色，以祖父节点为轴，右旋转。
                _cur->parent->parent->color = node_red;
                _cur->parent->color = node_black;
                RotateRight(_cur->parent->parent/*,_root*/);
                // 此时进入下一次while判断跳出循环
            }
        }
        else // 父节点为右子节点，依照左子节点的同样方法解决。
        {
            if(_cur->parent->parent->left
                && _cur->parent->parent->left->color == node_red)  // 伯父节点为红
            {
                // 把父节点和伯父节点变成黑色，祖父节点变成红色
                _cur->parent->parent->left->color=node_black;
                _cur->parent->color = node_black;
                _cur->parent->parent->color = node_red;
 
                // 因为祖父节点为红色，需要继续向上测试是否满足规则
                _cur = _cur->parent->parent;
                continue;
            }
            else // 伯父节点为黑或不存在
            {
                if ( _cur == _cur->parent->left )
                {
                    // 以父节点为轴，右旋转后变成两个右外节点连续为红。
                    _cur = _cur->parent;
                    RotateRight(_cur/*,_root*/);
                }
                // 改变颜色，以祖父节点为轴，左旋转。
                _cur->parent->parent->color = node_red;
                _cur->parent->color = node_black;
                RotateLeft(_cur->parent->parent/*,_root*/);
                // 此时进入下一次while判断跳出循环
            }
        }
    }//end while
    _root->color = node_black;
}
 
node * My_Rb_Tree::InsertUnique(value_type in_val)
{
    node * y = head;
    node * x = Root();
    bool comp = true;
    while( x )//一层一层深入找到合适的插入点
    {
        y = x;
        comp = ( in_val < x->val );
        if (in_val == x->val)
        {
            return 0;
        }
        x = comp ? x->left : x->right;
    }
    return Insert(y,x,in_val);
}
 
node * My_Rb_Tree::Insert(node * in_parent, node * in_cur, value_type in_value)
{
    node * new_node = CreateNode(in_value);
    if (in_parent == head) // 插入的是根节点
    {
        head->parent = new_node;
        head->left = new_node;
        head->right = new_node;
 
        new_node->parent = head;
        new_node->color = node_black;
    }
    else // 插入的是非根节点
    {
        if ( new_node->val < in_parent->val )
        {
            in_parent->left = new_node;
            if (in_parent == head->left) // 若插入点的父节点是最小节点，更新最小值节点指针
            {
                head->left = new_node;
            }
        }
        else
        {
            in_parent->right = new_node;
            if (in_parent == head->right)// 若插入点的父节点是最大节点，更新最大值节点指针
            {
                head->right = new_node;
            }
        }
        new_node->parent = in_parent;
 
        if (in_parent == head)
        {
            head->parent = new_node;
            in_parent->parent = Root();
        }
    }
 
    Rebalance(new_node/*,head->parent*/);
    node_count++;
    return new_node;
}
// 未实现，这个函数比较复杂
void My_Rb_Tree::RebalanceForErase(node * _cur)
{
    return;
}
// 依赖RebalanceForErase的实现
void My_Rb_Tree::Erase(node * in_cur)
{
    return;
}
 
node * My_Rb_Tree::Find(value_type _val)
{
    node * _t = Root();
    while(_t)
    {
        if (_t->val == _val)
        {
            return _t;
        }
        else if (_t->val > _val)
        {
            _t = _t->right;
        }
        else
        {
            _t = _t->left;
        }
    }
    return 0;
}

标签： 代码

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。