红黑树的实现(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++ ,