当前位置:编程学习 > C/C++ >>

红黑树的实现(int精简版)

    最近在阅读SGI STL源代码,其中红黑树的实现比较有技术含量,但标准库里面是易做图了其中的allocator, iterator(Rb_tree专用的),使用很多模板变量,实现对多种数据类型的处理。这些情况对于有较扎实C++基础的人来说不成问题,但对于一般初学算法,而又没有太好的C++基础的人来说有点困难。并且SGI STL中的实现代码写得很精巧,节省代码,也高效运行,但会使得功能不够深厚的人读起来还是比较费劲。

      这里使用简单的int类型节点,实现红黑树的创建、插入及相关内部操作的功能。目前代码中删除节点及其内部操作功能没有实现。

      关于红黑树的五个条件(有的书上说四个,内容是等价的)以及插入节点后的调整,可以参考侯捷先生的《STL源码剖析》,里面有详细的原理介绍。也可以参考《算法导论》。下面代码可以直接使用运行,经测试正确,代码不追求在物理运行上的效率,尽量把算法步骤表现在代码里,不作过多合并优化,并且已经加上不少注释,方便阅读。

My_Rb_Tree.h

[cpp]
#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

[cpp] view plaincopy
/************************************************************************/ 
/*  @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; 
 &

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,