此文承接：算法实战：亲自写红黑树之一-CSDN博客
目录
一、项目结构
二、辅助代码a.h
三、红黑树代码rbtree.h
四、测试代码main.cpp
五、运行效果
六、代码详解
一、项目结构
这里给出的代码是实际可以运行的代码。
运行环境：VS2022，控制台项目，64位。注意，VS的数据类型和UNix/Linux是不一样的，64位下long仍然是32位的，long long才是64位。
包含三个文件，一个辅助文件，主要是树形显示的代码，一个头文件，是红黑树代码，一个主文件，是测试代码，包含main函数。
二、辅助代码a.h
树形显示的代码，没有这个很难调试。
#include <string>
#include <vector>
using namespace std;
struct _cell
{
string value;
};
struct _record
{
vector<_cell > cells;
};
class Table
{
private:
vector<_record > m_bodys;
size_t _GetColCount(vector<_record > const& trs)
{
vector<_record >::const_iterator it;
size_t maxcount = 0;
for (it = trs.begin(); it != trs.end(); ++it)
{
if (it->cells.size() > maxcount)maxcount = it->cells.size();
}
return maxcount;
}
size_t GetActualColCount()
{
//这个值是定义的列的数目和每个行的列数目之最大者
size_t maxcount = 0;
if (_GetColCount(m_bodys) > maxcount)maxcount = _GetColCount(m_bodys);
return maxcount;
}
public:
//设置数据，行必须有效，但可随意跳过一些列
void SetData(size_t lineindex, size_t colindex, string const& data)
{
if (lineindex >= m_bodys.size())m_bodys.resize(lineindex + 1);
if (colindex >= m_bodys[lineindex].cells.size())m_bodys[lineindex].cells.resize(colindex + 1);
m_bodys[lineindex].cells[colindex].value = data;
}
//计算输出长度
size_t outputlen(string const& s)
{
return utf8outputlen(s.c_str());
}
//utf-8中文通常为3个字节，输出仍为两个字符宽度
size_t utf8outputlen(char const* s)
{
char const* p = s;
long count_ansi = 0;
long count_other = 0;
while (*p)
{
if (*p < 0)++count_other;
else ++count_ansi;
++p;
}
return count_ansi + count_other * 2 / 3;
}
//head_tail_n==0显示全部，否则只显示前后head_tail_n
string MakeTextTable(size_t head_tail_n = 0)
{
string ret;
size_t i, j;
size_t actualcount = this->GetActualColCount();
vector<size_t > v_colmaxlen;//列的最大宽度
v_colmaxlen.reserve(actualcount);
for (i = 0; i < actualcount; ++i)
{
v_colmaxlen.push_back(0);
for (j = 0; j < m_bodys.size(); ++j)
{
if (i < m_bodys[j].cells.size())
{
string data = m_bodys[j].cells[i].value;
if (outputlen(data) > v_colmaxlen[i])v_colmaxlen[i] = outputlen(data);
}
}
}
ret = "";
string str;
ret += "\n";
for (i = 0; i < actualcount; ++i)
{
str.assign(v_colmaxlen[i], '-');
ret += str;
ret += " ";
}
ret += "\n";
bool first_skip = true;
for (j = 0; j < m_bodys.size(); ++j)
{
if (head_tail_n > 0 && j >= head_tail_n && j < m_bodys.size() - head_tail_n)
{
if (first_skip)
{
first_skip = false;
ret += "......\n";
}
else continue;
}
else
{
for (i = 0; i < m_bodys[j].cells.size(); ++i)
{
string data = m_bodys[j].cells[i].value;
str.assign(v_colmaxlen[i] - outputlen(data), ' ');
ret += data;
ret += str;
ret += " ";
}
ret += "\n";
}
}
for (i = 0; i < actualcount; ++i)
{
str.assign(v_colmaxlen[i], '-');
ret += str;
ret += " ";
}
ret += "\n";
return ret;
}
};
这个类本来很大的，我删掉了所有不相关代码，只保留了显示树形结构的代码。这个代码在此文有介绍：程序设计：控制台输出二叉树 二叉树的形象显示-CSDN博客
这个代码不算复杂，其中计算输出长的outputlen是有问题的，没有真正按照字符数计算，一般我们只用asccii字符，不用中文，一般不会有问题（除非混有\t\r\n之类的格式字符）。
三、红黑树代码rbtree.h
这个代码是比较长的，后面会拆解分析主要代码。
#pragma once
#include "a.h"
#include <iomanip>
extern bool G_IS_DEBUG;
#define thelog cout<<setw(5)<<__LINE__<<" : "
#define debug_log if(G_IS_DEBUG)thelog
#define endi endl
#define ende " [ERROR]"<<endl
typedef long long T_SHM_SIZE;
#define ARRAY_CAPACITY 10000
struct CDemoData
{
long long n = 0;
//用于需要排序的场合
bool operator < (CDemoData const& tmp)const { return n < tmp.n; }
//某些场合也需要等于
bool operator == (CDemoData const& tmp)const { return n == tmp.n; }
friend ostream& operator << (ostream& o, CDemoData const& d)
{
return o << d.n;
}
//用于输出数据的场合
string& toString(string& str)const
{
char buf[2048];
sprintf_s(buf, 2048, "%lld", n);
return str = buf;
}
};
typedef CDemoData T_DATA;
typedef less<T_DATA> T_COMP;
struct TREE_NODE
{
T_SHM_SIZE hParent;//-1:无，根节点；0-N,子节点，或指向下个空闲地址
T_SHM_SIZE hLeft;//-1表示无子节点
T_SHM_SIZE hRight;//-1表示无子节点
//颜色
bool bColorRed;//是否为红色
//删除标志
signed char deleted;//0：有效，1：删除
T_DATA data;
TREE_NODE() :hParent(-1), hLeft(-1), hRight(-1), bColorRed(true), deleted(0) {}
TREE_NODE(T_SHM_SIZE parent, T_DATA const& tmp) :hParent(parent), hLeft(-1), hRight(-1), bColorRed(true), deleted(0), data(tmp) {}
string& toString(string& str, void* = NULL)const
{
char buf[2048];
string tmp;
if (-1 == _me())strcpy(buf, "空节点");
else sprintf_s(buf, 2048, "%8lld : %8lld %8lld %8lld %s %1d : %10s", _me(), hParent, hLeft, hRight, (bColorRed ? "R" : "B"), deleted, data.toString(tmp).c_str());
return str = buf;
}
string toString2(bool left,bool bStruct)const
{
if (-1 == _me())return "空节点";
char buf[2048];
string ret;
if (!bStruct)
{
sprintf_s(buf, 2048, "%lld%s%lld", _me(), (bColorRed ? "+" : "-"), data.n);
if (left)
{
ret = "[";
ret += buf;
}
else
{
ret = buf;
ret += "]";
}
}
else
{
sprintf_s(buf, 2048, "p%lld L%lld R%lld", hParent, hLeft, hRight);
ret = buf;
}
return ret;
}
bool operator < (TREE_NODE const& tmp)const
{
T_COMP comp;
return comp(data, tmp.data);
}
static TREE_NODE& at(T_SHM_SIZE n);
T_SHM_SIZE _me()const;
T_SHM_SIZE _begin()const
{
if (-1 == hLeft)return _me();
return at(hLeft)._begin();
}
T_SHM_SIZE _end()const
{
if (-1 == hRight)return _me();
return at(hRight)._end();
}
bool isRight()const
{
return -1 != hParent && _me() == at(hParent).hRight;
}
bool isLeft()const
{
return !isRight();
}
void _CopyWithoutData(TREE_NODE const& tmp)
{
hParent = tmp.hParent;
hLeft = tmp.hLeft;
hRight = tmp.hRight;
bColorRed = tmp.bColorRed;
deleted = tmp.deleted;
}
};
class CRBTree
{
public:
struct iterator
{
T_SHM_SIZE handle;
iterator() :handle(-1) {}
bool operator == (iterator const& tmp)const { return handle == tmp.handle; }
bool operator != (iterator const& tmp)const { return !(*this == tmp); }
T_DATA& operator * ()const
{
return TREE_NODE::at(handle).data;
}
T_DATA* operator -> ()const
{
return &(operator *());
}
iterator& operator ++ ()
{
if (-1 != TREE_NODE::at(handle).hRight)
{//存在右子树，取右子树的begin
handle = TREE_NODE::at(handle).hRight;
handle = TREE_NODE::at(handle)._begin();
}
else if (-1 != TREE_NODE::at(handle).hParent)
{//存在父节点
if (TREE_NODE::at(handle).isRight())
{//是父节点的右子树，向上找到是左子树的节点，取这个节点的父节点
while ((handle = TREE_NODE::at(handle).hParent) != -1 && TREE_NODE::at(handle).isRight()) {}
if (-1 != handle && !TREE_NODE::at(handle).isRight())handle = TREE_NODE::at(handle).hParent;
}
else
{//是父节点的左子树，取父节点
handle = TREE_NODE::at(handle).hParent;
}
}
else
{//根节点且没有右子树，结束
handle = -1;
}
return *this;
}
iterator& operator -- ()
{
if (-1 != TREE_NODE::at(handle).hLeft)
{//存在左子树，取左子树的end
handle = TREE_NODE::at(handle).hLeft;
handle = TREE_NODE::at(handle)._end();
}
else if (-1 != TREE_NODE::at(handle).hParent)
{//存在父节点
if (TREE_NODE::at(handle).isLeft())
{//是父节点的左子树，向上找到是右子树的节点，取这个节点的父节点
while ((handle = TREE_NODE::at(handle).hParent) != -1 && TREE_NODE::at(handle).isLeft()) {}
if (-1 != handle && !TREE_NODE::at(handle).isLeft())handle = TREE_NODE::at(handle).hParent;
}
else
{//是父节点的右子树，取父节点
handle = TREE_NODE::at(handle).hParent;
}
}
else
{//根节点且没有右子树，结束
handle = -1;
}
return *this;
}
};
typedef iterator const_iterator;
struct TREE_HEAD
{
T_SHM_SIZE hHead;
T_SHM_SIZE size;
T_SHM_SIZE free_head;//空闲地址头指针
TREE_HEAD() :hHead(-1), size(0), free_head(-1) {}
//用于输出数据的场合
string& toString(string& str)const
{
char buf[2048];
sprintf_s(buf, 2048, "head %lld size %lld", hHead, size);
return str;
}
};
struct T_SETARRAY
{
//新版数组头
struct array_head
{
T_SHM_SIZE capacity;
T_SHM_SIZE size;
};
array_head _array_head;
array_head const* GetHead()const { return &_array_head; }
T_SHM_SIZE capacity()const { return _array_head.capacity; }
T_SHM_SIZE size()const { return _array_head.size; }
T_SHM_SIZE Capacity()const { return _array_head.capacity; }
T_SHM_SIZE Size()const { return _array_head.size; }
struct HANDLE
{
T_SHM_SIZE handle;
};
bool Add(TREE_NODE const& data, HANDLE& h)
{
if (_array_head.size == _array_head.capacity)return false;
else
{
h.handle = _array_head.size;
TREE_NODE::at(h.handle) = data;
++_array_head.size;
return true;
}
}
};
private:
TREE_HEAD _tree_head;
private:
//insert时如果已经存在保存被覆盖的数据
bool m_OldValueSeted;
T_DATA m_OldValue;
public:
T_SETARRAY m_array;//内置数组对象，存储实际数据
TREE_HEAD* tree_head = &_tree_head;//指向树的头
CRBTree() :m_OldValueSeted(false)
{
m_array._array_head.capacity = ARRAY_CAPACITY;
m_array._array_head.size = 0;
}
T_SHM_SIZE size()const { return tree_head->size; }
T_SHM_SIZE capacity()const { return m_array.GetHead()->capacity; }
const_iterator begin()const
{
const_iterator it;
if (-1 == tree_head->hHead)it.handle = -1;
else it.handle = TREE_NODE::at(tree_head->hHead)._begin();
return it;
}
const_iterator end()const
{
const_iterator it;
it.handle = -1;
return it;
}
bool _check_handle(T_SHM_SIZE h)const
{
return h >= -1 && h < m_array.GetHead()->size;
}
bool _check_is_data_node(T_SHM_SIZE h)const
{
return h >= 0 && h < m_array.GetHead()->size;
}
//获取节点总数，包括自身
T_SHM_SIZE _check_get_count(T_SHM_SIZE h)
{
//thelog << h << endi;
T_SHM_SIZE n = 0;
if (_check_is_data_node(h))
{
++n;
//thelog << h << " " << TREE_NODE::at(h).hLeft<<" "<< TREE_NODE::at(h).hRight << endi;
n += _check_get_count(TREE_NODE::at(h).hLeft);
n += _check_get_count(TREE_NODE::at(h).hRight);
}
else
{
//thelog << "NULL" << endi;
}
return n;
}
//树形显示，px为偏移量，左边元素数
void _check_show_tree(Table& table, T_SHM_SIZE h, bool left = true, T_SHM_SIZE line = 0, T_SHM_SIZE px = 0)
{
//thelog << h << " " << line << " " << px << endi;
if (!_check_is_data_node(h))
{
//thelog << "空" << endi;
return;
}
T_SHM_SIZE leftCount = _check_get_count(TREE_NODE::at(h).hLeft);
//thelog << "leftCount " << leftCount << endi;
T_SHM_SIZE pos = px + leftCount;
table.SetData(line * 2, pos, TREE_NODE::at(h).toString2(left, false));//设置自身数据
table.SetData(line * 2 + 1, pos, TREE_NODE::at(h).toString2(left, true));//设置自身数据
//thelog << "TREE_NODE::at(h).hLeft " << TREE_NODE::at(h).hLeft << endi;
_check_show_tree(table, TREE_NODE::at(h).hLeft, true, line + 1, px);//处理左子项
//thelog << "TREE_NODE::at(h).hRight " << TREE_NODE::at(h).hRight << endi;
_check_show_tree(table, TREE_NODE::at(h).hRight, false, line + 1, pos + 1);//处理右子项
}
void debug()
{
if (G_IS_DEBUG)
{
Table table;
_check_show_tree(table, tree_head->hHead);
thelog << endl << table.MakeTextTable() << endi;
}
}
//检查红黑树特征
bool _check_rbtree()
{
if (-1 == tree_head->hHead)return true;
if (TREE_NODE::at(tree_head->hHead).bColorRed)
{
thelog << "根节点不是黑色" << ende;
return false;
}
T_SHM_SIZE count_black = -1;
if (_check_rbtree_count(tree_head->hHead, count_black, 0, 0, false))
{
debug_log << "深度 " << count_black << endi;
return true;
}
else
{
return false;
}
}
bool _check_rbtree_count(T_SHM_SIZE h, T_SHM_SIZE& count_black, T_SHM_SIZE black, T_SHM_SIZE red, bool PisRed)
{
if (-1 == h)
{
if (-1 == count_black)
{
count_black = black;
return true;
}
else
{
if (black != count_black || red > black)
{
thelog << "深度不正确 " << count_black << " " << black << " " << red << ende;
return false;
}
return true;
}
}
else
{
if (TREE_NODE::at(h).bColorRed)
{
if (PisRed)
{
thelog << "连续红节点 " << h << ende;
return false;
}
return _check_rbtree_count(TREE_NODE::at(h).hLeft, count_black, black, red + 1,true)
&& _check_rbtree_count(TREE_NODE::at(h).hRight, count_black, black, red + 1,true);
}
else
return _check_rbtree_count(TREE_NODE::at(h).hLeft, count_black, black + 1, red,false)
&& _check_rbtree_count(TREE_NODE::at(h).hRight, count_black, black + 1, red,false);
}
}
//检查数据结构是否正确
bool _check()const
{
debug_log << "检查树结构，如果检查过程中发生数据修改则检查可能会出错" << endi;
{
size_t count_data_array = 0;//数组中的有效数据个数
T_SHM_SIZE h;
for (h = 0; h < static_cast<T_SHM_SIZE>(m_array.size()); ++h)
{
if (!TREE_NODE::at(h).deleted)++count_data_array;
}
debug_log << "数组容量 " << m_array.capacity() << " 个数 " << m_array.size() << " 有效数据 " << count_data_array << endi;
debug_log << "树结构容量 " << capacity() << " 个数 " << size() << endi;
if (count_data_array != size())
{
thelog << "树结构大小与数组统计不符 " << size() << " " << count_data_array << ende;
return false;
}
}
T_SHM_SIZE max_handle = m_array.GetHead()->size - 1;//整个已分配空间的最大句柄
size_t count_free = 0;//未用节点数（删除的）
//获取自由节点数
{
if (!_check_handle(tree_head->free_head))
{
thelog << "free_head error " << tree_head->free_head << ende;
return false;
}
T_SHM_SIZE h = tree_head->free_head;
while (h >= 0)
{
if (!TREE_NODE::at(h).deleted)
{
thelog << "此节点未被标记为删除 " << h << ende;
return false;
}
++count_free;
if (TREE_NODE::at(h).hParent<-1 || TREE_NODE::at(h).hParent>max_handle)
{
thelog << "TREE_NODE::at(h).hParent error " << TREE_NODE::at(h).hParent << ende;
return false;
}
h = TREE_NODE::at(h).hParent;
}
}
if (count_free != m_array.size() - size())
{
thelog << "删除链表总数不正确 " << count_free << " " << m_array.size() - size() << ende;
return false;
}
debug_log << "删除链表节点总数 " << count_free << endi;
size_t count_used = 0;//已用节点数
//获取已用节点数
{
T_COMP comp;
iterator it = begin();
iterator it_old = end();
while (it != end())
{
if (!_check_handle(it.handle))
{
thelog << "无效的节点 " << it.handle << ende;
return false;
}
if (TREE_NODE::at(it.handle).deleted)
{
thelog << "此节点被标记为删除 " << it.handle << ende;
return false;
}
if (it_old == it)
{
thelog << "指针循环 [" << it_old.handle << "][" << it.handle << "]" << ende;
return false;
}
if (it_old != end() && !comp(*it_old, *it))
{
string str1, str2;
thelog << "节点数据比较错误 [" << it_old->toString(str1) << "][" << it->toString(str2) << "]" << ende;
return false;
}
++count_used;
it_old = it;
++it;
}
}
if (count_used != static_cast<size_t>(tree_head->size))
{
thelog << "begin->end ！= size " << count_used << " " << tree_head->size << ende;
return false;
}
if (count_used != size())
{
thelog << "遍历获得节点数不正确 " << count_used << " " << size() << ende;
return false;
}
debug_log << "检查完成，没有错误" << endi;
return true;
}
private:
//替换数据（只在插入时使用）
void _update(T_SHM_SIZE position, T_DATA const& tmp)
{
TREE_NODE::at(position).data = tmp;
}
//修改头指针指向 src 的改为指向des（除了旋转只在删除里用到）
void _changeRoot(T_SHM_SIZE src, T_SHM_SIZE des)
{
TREE_NODE::at(des).hParent = TREE_NODE::at(src).hParent;
if (TREE_NODE::at(des).hParent != -1)
{
//旋转后是左节点
if (TREE_NODE::at(TREE_NODE::at(des).hParent).hLeft == src)
TREE_NODE::at(TREE_NODE::at(des).hParent).hLeft = des;
//旋转后是右节点
else
TREE_NODE::at(TREE_NODE::at(des).hParent).hRight = des;
}
else
{
tree_head->hHead = des;
}
}
//右旋转
void _RRotate(T_SHM_SIZE p)
{
debug_log << "右旋" << p << endi;
//assert(p>=0&&p<tree_head->size);
//DEBUG_LOG<<"当前位置"<<p <<"大小"<< tree_head->size <<endi;
T_SHM_SIZE t_lchild = TREE_NODE::at(p).hLeft;
TREE_NODE::at(p).hLeft = TREE_NODE::at(t_lchild).hRight;
//右节点非空
if (TREE_NODE::at(t_lchild).hRight != -1)
TREE_NODE::at(TREE_NODE::at(t_lchild).hRight).hParent = p;
//修改根节点父指针
_changeRoot(p, t_lchild);
TREE_NODE::at(p).hParent = t_lchild;
TREE_NODE::at(t_lchild).hRight = p;
}
//左旋转
void _LRotate(T_SHM_SIZE p)
{
debug_log << "左旋 " << p << endi;
string tmp;
debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
T_SHM_SIZE t_rchild = TREE_NODE::at(p).hRight;
debug_log << "t_rchild " << TREE_NODE::at(t_rchild).toString(tmp) << endi;
TREE_NODE::at(p).hRight = TREE_NODE::at(t_rchild).hLeft;
debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
//右节点非空
if (TREE_NODE::at(t_rchild).hLeft != -1)
{
TREE_NODE::at(TREE_NODE::at(t_rchild).hLeft).hParent = p;
debug_log << "TREE_NODE::at(t_rchild).hLeft " << TREE_NODE::at(TREE_NODE::at(t_rchild).hLeft).toString(tmp) << endi;
}
//非根节点
//DEBUG_LOG << "_LRotate t_rchild's parent" <<TREE_NODE::at(t_rchild).hParent <<endi;
//修改根节点父指针
_changeRoot(p, t_rchild);
debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
debug_log << "t_rchild " << TREE_NODE::at(t_rchild).toString(tmp) << endi;
TREE_NODE::at(p).hParent = t_rchild;
TREE_NODE::at(t_rchild).hLeft = p;
debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
debug_log << "t_rchild " << TREE_NODE::at(t_rchild).toString(tmp) << endi;
}
//交换颜色
void _exchage_color(T_SHM_SIZE a, T_SHM_SIZE b)
{
bool tmp = TREE_NODE::at(a).bColorRed;
TREE_NODE::at(a).bColorRed = TREE_NODE::at(b).bColorRed;
TREE_NODE::at(b).bColorRed = tmp;
}
//是否是红色，-1当作黑色
bool _isRed(T_SHM_SIZE h)
{
return h != -1 && TREE_NODE::at(h).bColorRed;
}
//插入的入口
pair<iterator, bool> _insert(T_DATA const& tmp, T_COMP& comp)
{
pair<iterator, bool> tmppair;
T_SHM_SIZE insert_position = -1;
bool isLeft = true;//插入节点方向 默认左插入
bool isInsert = false;
if ((insert_position = __insert(tmp, tree_head->hHead, -1, isLeft, isInsert, comp)) >= 0)
{
tmppair.first.handle = insert_position;
tmppair.second = isInsert;
//DEBUG_LOG<<"插入节点"<<insert_position<<"数据 "<<show(insert_position) <<endi;
}
else
{
//插入失败或者空间已满
thelog << "插入节点失败" << ende;
tmppair.first.handle = -1;
tmppair.second = false;
}
TREE_NODE::at(tree_head->hHead).bColorRed = false;//根节点始终是黑色，因为转置的时候不能改颜色，所以只能在最后改
return tmppair;
}
//插入节点返回-1不成功，vp父节点的子节点（即试图在此处插入），_parent父节点，taller 判断插入数据后节点深度是否增加
T_SHM_SIZE __insert(T_DATA const& tmp, T_SHM_SIZE vp, T_SHM_SIZE _parent, bool isLeft, bool& isInsert, T_COMP& comp)
{
T_SHM_SIZE insert_position = -1;
if (vp == -1)
{
//此位置为空，在此处插入
insert_position = tree_head->free_head;
___insert_new(tmp, insert_position, _parent, isLeft, isInsert);
//DEBUG_LOG<<"insert_position="<<insert_position<<endi;
}
else
{
//此位置有数据，根据比较结果处理
if (comp(TREE_NODE::at(vp).data, tmp))
{
//大，走右边
if ((insert_position = __insert(tmp, TREE_NODE::at(vp).hRight, vp, false, isInsert, comp)) == -1)
{
return -1;
}
}
else if (comp(tmp, TREE_NODE::at(vp).data))
{
//小，走左边
if ((insert_position = __insert(tmp, TREE_NODE::at(vp).hLeft, vp, true, isInsert, comp)) == -1)
{
return -1;
}
}
else
{
//相等，更新数据
//thelog<<"插入数据已经存在"<<endw;
m_OldValue = TREE_NODE::at(vp).data;//保存被覆盖的值
m_OldValueSeted = true;//设置被覆盖的对象有效
_update(vp, tmp);
return vp;
}
}
return insert_position;
}
//插入新节点，position为新节点的位置，来自空闲列表，parent为父节点的位置
void ___insert_new(T_DATA const& data, T_SHM_SIZE& position, T_SHM_SIZE parent, bool isLeft, bool& isInsert)
{
if (position < 0)
{
//没有空闲位置，需要动态扩展长度
if (m_array.Capacity() > m_array.Size())
{
TREE_NODE tmp;
typename T_SETARRAY::HANDLE h;
if (!m_array.Add(tmp, h))
{
thelog << "扩展数组出错" << ende;
isInsert = false;
return;
}
else
{
//tree_head = m_array.GetUserHead();算法测试不用
position = h.handle;
}
}
else
{
thelog << "空间已满，请申请更大空间!!!!!!!!!!!!!!!!!!" << ende;
isInsert = false;
return;
}
}
else
{
//thelog<<"exist position="<<position<<endi;
}
tree_head->free_head = TREE_NODE::at(position).hParent;//空闲队列用hParent指向下一个
//char buf[256];
//sprintf(buf,"%ld %p",position,&TREE_NODE::at(position));
//thelog<<buf<<endi;
new(&TREE_NODE::at(position)) TREE_NODE(parent, data);
//DEBUG_LOG<<show(position)<<endi;
TREE_NODE::at(position).deleted = 0;
if (parent == -1)
{
//没有父节点，空树
tree_head->hHead = position;
TREE_NODE::at(position).bColorRed = false;//根节点为黑色
}
else
{
//修改父节点
//DEBUG_LOG<<show(parent)<<endi;
if (isLeft)
{
TREE_NODE::at(parent).hLeft = position;
//DEBUG_LOG<<show(parent)<<endi;
}
else
{
TREE_NODE::at(parent).hRight = position;
//DEBUG_LOG<<show(parent)<<endi;
}
//平衡处理
_RB_insert_Balance(position);
}
isInsert = true;
//DEBUG_LOG<<"新增节点"<<position<<"["<<show(position)<<"]"<<endi;
++tree_head->size;
if (tree_head->size % 200000 == 0)
{
thelog << "树结构新增数据" << tree_head->size << endi;
}
}
void _RB_insert_Balance(T_SHM_SIZE x)
{
T_SHM_SIZE p = TREE_NODE::at(x).hParent;
if (!_isRed(p))return;
//连续红，需要调整
bool isLeft = (x == TREE_NODE::at(p).hLeft);
T_SHM_SIZE g = TREE_NODE::at(p).hParent;
bool isL = (p == TREE_NODE::at(g).hLeft);
T_SHM_SIZE u = (isL ? TREE_NODE::at(g).hRight : TREE_NODE::at(g).hLeft);
if (_isRed(u))
{
//u为红只需要染色，然后递归
TREE_NODE::at(p).bColorRed = false;
TREE_NODE::at(u).bColorRed = false;
TREE_NODE::at(g).bColorRed = true;
_RB_insert_Balance(g);
}
else
{
if (isL)
{
if (isLeft)
{//LL
_RRotate(g);
_exchage_color(p, g);
}
else
{//LR
_LRotate(p);
_RRotate(g);
_exchage_color(x, g);
}
}
else
{
if (isLeft)
{//RL
_RRotate(p);
_LRotate(g);
_exchage_color(x, g);
}
else
{//RR
_LRotate(g);
_exchage_color(p, g);
}
}
}
}
//删除指定节点，将节点接入到空闲链表
void __erase_node(T_SHM_SIZE position)
{
debug_log << "删除节点 " << position << endi;
TREE_NODE::at(position).hParent = tree_head->free_head;
tree_head->free_head = position;
TREE_NODE::at(position).hLeft = -1;
TREE_NODE::at(position).hRight = -1;
TREE_NODE::at(position).deleted = 1;
--tree_head->size;
}
//删除中间节点，将中间节点替换为左子树最大值（数据不动，改变树结构）
bool __erase_change_middle(T_SHM_SIZE const position, bool& vLeft, bool& vRed, T_SHM_SIZE& u, bool& uRed, T_SHM_SIZE& p)
{
string tmp;
T_SHM_SIZE new_position = TREE_NODE::at(position).hLeft;
if (-1 != new_position)
{
while (-1 != TREE_NODE::at(new_position).hRight)
{
new_position = TREE_NODE::at(new_position).hRight;
}
}
debug_log << "position " << position << " new_position " << new_position << endi;
debug_log << "position " << position << TREE_NODE::at(position).toString(tmp) << endi;
debug_log << "new_position " << new_position << TREE_NODE::at(new_position).toString(tmp) << endi;
vLeft = false;
vRed = TREE_NODE::at(new_position).bColorRed;
p = TREE_NODE::at(new_position).hParent;
debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
if (p != position)
{
debug_log << "非直接对调 p " << TREE_NODE::at(p).toString(tmp) << ende;
TREE_NODE t;
t._CopyWithoutData(TREE_NODE::at(new_position));
TREE_NODE::at(new_position)._CopyWithoutData(TREE_NODE::at(position));
TREE_NODE::at(position)._CopyWithoutData(t);
debug_log << "position " << TREE_NODE::at(position).toString(tmp) << endi;
debug_log << "new_position " << TREE_NODE::at(new_position).toString(tmp) << endi;
//注意，这里无法用isLeft来判断，因为父节点的hLeft和hRight是旧数据
if (TREE_NODE::at(new_position).hParent != -1)
{
if (TREE_NODE::at(TREE_NODE::at(new_position).hParent).hLeft == position)TREE_NODE::at(TREE_NODE::at(new_position).hParent).hLeft = new_position;
else TREE_NODE::at(TREE_NODE::at(new_position).hParent).hRight = new_position;
}
if (TREE_NODE::at(position).hParent != -1)
{
if (TREE_NODE::at(TREE_NODE::at(position).hParent).hLeft==new_position)TREE_NODE::at(TREE_NODE::at(position).hParent).hLeft = position;
else TREE_NODE::at(TREE_NODE::at(position).hParent).hRight = position;
}
if (TREE_NODE::at(new_position).hLeft != -1)TREE_NODE::at(TREE_NODE::at(new_position).hLeft).hParent = new_position;
if (TREE_NODE::at(position).hLeft != -1)TREE_NODE::at(TREE_NODE::at(position).hLeft).hParent = position;
if (TREE_NODE::at(new_position).hRight != -1)TREE_NODE::at(TREE_NODE::at(new_position).hRight).hParent = new_position;
if (TREE_NODE::at(position).hRight != -1)TREE_NODE::at(TREE_NODE::at(position).hRight).hParent = position;
}
else
{
debug_log << "直接对调 p " << TREE_NODE::at(p).toString(tmp) << endi;
TREE_NODE t;
t._CopyWithoutData(TREE_NODE::at(new_position));
TREE_NODE::at(new_position)._CopyWithoutData(TREE_NODE::at(position));
TREE_NODE::at(position)._CopyWithoutData(t);
debug_log << "position " << TREE_NODE::at(position).toString(tmp) << endi;
debug_log << "new_position " << TREE_NODE::at(new_position).toString(tmp) << endi;
//注意，这里无法用isLeft来判断，因为父节点的hLeft和hRight是旧数据
if (TREE_NODE::at(new_position).hParent != -1)
{
if (TREE_NODE::at(TREE_NODE::at(new_position).hParent).hLeft == position)TREE_NODE::at(TREE_NODE::at(new_position).hParent).hLeft = new_position;
else TREE_NODE::at(TREE_NODE::at(new_position).hParent).hRight = new_position;
}
TREE_NODE::at(position).hParent = new_position;
TREE_NODE::at(new_position).hLeft=position;
if (TREE_NODE::at(position).hLeft != -1)TREE_NODE::at(TREE_NODE::at(position).hLeft).hParent = position;
if (TREE_NODE::at(new_position).hRight != -1)TREE_NODE::at(TREE_NODE::at(new_position).hRight).hParent = new_position;
if (TREE_NODE::at(position).hRight != -1)TREE_NODE::at(TREE_NODE::at(position).hRight).hParent = position;
}
//如果是根节点
if (-1 == TREE_NODE::at(new_position).hParent)
{
TREE_NODE::at(new_position).bColorRed = false;
tree_head->hHead = new_position;
}
debug_log << "position " << TREE_NODE::at(position).toString(tmp) << endi;
debug_log << "new_position " << TREE_NODE::at(new_position).toString(tmp) << endi;
debug();
return true;
}
//删除时做平衡，u可能是空节点
bool _RB_erase_Balance(T_SHM_SIZE p, T_SHM_SIZE u)
{
if (-1 == p)
{
debug_log << "已经到顶，结束" << endi;
return true;
}
string tmp;
debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
if (u != -1)debug_log << "u " << TREE_NODE::at(u).toString(tmp) << endi;
else debug_log << "u -1" << endi;
bool isL = (u == TREE_NODE::at(p).hRight);//兄弟节点是否是左节点
T_SHM_SIZE s = (isL ? TREE_NODE::at(p).hLeft : TREE_NODE::at(p).hRight);
T_SHM_SIZE r = -1;//s的红色子节点
bool is_rL;//s的红色子节点是否是左节点
debug_log << "平衡：p " << p << " u " << u << " s " << s << " TREE_NODE::at(s).hRight " << TREE_NODE::at(s).hRight << endi;
if (TREE_NODE::at(s).hRight != -1 && TREE_NODE::at(TREE_NODE::at(s).hRight).bColorRed)
{
r = TREE_NODE::at(s).hRight;
is_rL = false;
}
else if (TREE_NODE::at(s).hLeft != -1 && TREE_NODE::at(TREE_NODE::at(s).hLeft).bColorRed)
{
r = TREE_NODE::at(s).hLeft;
is_rL = true;
}
else
{
r = -1;
is_rL = false;//无意义
}
debug_log << "p " << p << " u " << u << " s " << s << " r（-1表示双黑） " << r << endi;
debug();
if (-1 == r)
{
debug_log << "s子节点均为黑" << endi;
if (TREE_NODE::at(p).bColorRed)
{
debug_log << "p为红，s必为黑 s改为红p改为黑 结束" << endi;//s子节点均为黑，p改为黑，所以s改为红是安全的，不会造成双红
TREE_NODE::at(s).bColorRed = true;
TREE_NODE::at(p).bColorRed = false;
debug();
}
else
{
debug_log << "p为黑" << endi;
if (!TREE_NODE::at(s).bColorRed)
{
debug_log << "s为黑 s改为红平衡下层并向上递归" << endi;//p的左右分支均少1，所以p成为新的双黑节点
//置s为红，p为新的u，递归
TREE_NODE::at(s).bColorRed = true;
debug();
return _RB_erase_Balance(TREE_NODE::at(p).hParent, p);
}
else
{
debug_log << "s为红 " << TREE_NODE::at(s).toString(tmp) << endi;
debug_log << TREE_NODE::at(TREE_NODE::at(s).hParent).toString(tmp) << endi;
if (TREE_NODE::at(s).isLeft())
{
debug_log << "s为左 " << s << endi;
//右旋p
_RRotate(p);
}
else
{
debug_log << "s为右" << endi;
_LRotate(p);
}
//p和s变色
TREE_NODE::at(s).bColorRed = false;
TREE_NODE::at(p).bColorRed = true;
debug();
//此时深度情况不变，但p变成了红，重新对p和u做平衡处理
return _RB_erase_Balance(p, u);
}
}
}
else
{
if (isL && is_rL)
{
debug_log << "LL" << ende;
TREE_NODE::at(r).bColorRed = TREE_NODE::at(s).bColorRed;
TREE_NODE::at(s).bColorRed = TREE_NODE::at(p).bColorRed;
_RRotate(p);
TREE_NODE::at(p).bColorRed = false;
}
else if (isL && !is_rL)
{
debug_log << "LR" << endi;
debug();
TREE_NODE::at(r).bColorRed = TREE_NODE::at(p).bColorRed;
debug();
_LRotate(s);
debug();
_RRotate(p);
debug();
TREE_NODE::at(p).bColorRed = false;
debug();
}
else if (!isL && is_rL)
{
debug_log << "RL------------------------" << endi;
debug();
TREE_NODE::at(r).bColorRed = TREE_NODE::at(p).bColorRed;
debug();
_RRotate(s);
debug();
string tmp;
debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
debug_log << "s " << TREE_NODE::at(p).toString(tmp) << endi;
_LRotate(p);
debug();
TREE_NODE::at(p).bColorRed = false;
debug();
}
else if (!isL && !is_rL)
{
debug_log << "RR" << endi;
TREE_NODE::at(r).bColorRed = TREE_NODE::at(s).bColorRed;
TREE_NODE::at(s).bColorRed = TREE_NODE::at(p).bColorRed;
_LRotate(p);
TREE_NODE::at(p).bColorRed = false;
}
else
{
thelog << "非预期的状态" << ende;
return false;
}
}
return true;
}
//删除
bool _erase(T_SHM_SIZE position)
{
string report;
//DEBUG_LOG<<"开始删除...."<<Report(report) <<endi;
bool vLeft;//删除的节点是左子节点
bool vRed;//删除的节点是红色
T_SHM_SIZE p = TREE_NODE::at(position).hParent;//父节点
T_SHM_SIZE u;//替换节点
bool uRed;//替换节点是红色（-1为黑色）
if (TREE_NODE::at(position).hLeft != -1 && TREE_NODE::at(position).hRight != -1)
{
debug_log << "左右都存在，替换为左子树最大值" << endi;
if (!__erase_change_middle(position, vLeft, vRed, u, uRed, p))return false;
debug();
return _erase(position);
}
else if (-1 == TREE_NODE::at(position).hLeft && -1 == TREE_NODE::at(position).hRight)
{
vLeft = TREE_NODE::at(position).isLeft();
vRed = TREE_NODE::at(position).bColorRed;
u = -1;
uRed = false;
if (-1 == p)
{
debug_log << "最后一个节点" << endi;
tree_head->hHead = -1;
vRed = true;//阻止后面继续处理，删除红色无需额外处理
}
else
{
debug_log << "叶子节点" << endi;
if (TREE_NODE::at(position).isLeft())TREE_NODE::at(p).hLeft = -1;
else TREE_NODE::at(p).hRight = -1;
}
}
else
{
vLeft = TREE_NODE::at(position).isLeft();
vRed = TREE_NODE::at(position).bColorRed;
if (-1 != TREE_NODE::at(position).hLeft)
{
debug_log << "左子树存在" << endi;
u = TREE_NODE::at(position).hLeft;
}
else
{
debug_log << "右子树存在" << endi;
u = TREE_NODE::at(position).hRight;
}
if (-1 == p)
{
debug_log << "根节点" << endi;
tree_head->hHead = u;
}
else
{
if (vLeft)TREE_NODE::at(p).hLeft = u;
else TREE_NODE::at(p).hRight = u;
}
TREE_NODE::at(u).hParent = p;
uRed = TREE_NODE::at(u).bColorRed;
p = TREE_NODE::at(u).hParent;
}
bool ret = true;
if (vRed)
{
debug_log << "删除红色节点，不用调整" << endi;
//string tmp;
//debug_log << "position " << TREE_NODE::at(position).toString(tmp) << endi;
//debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
//debug_log << "u " << TREE_NODE::at(u).toString(tmp) << endi;
//TREE_NODE::at(u).hParent = p;
//if (vLeft)TREE_NODE::at(p).hLeft = u;
//else TREE_NODE::at(p).hRight = u;
//debug_log << "position " << TREE_NODE::at(position).toString(tmp) << endi;
//debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
//debug_log << "u " << TREE_NODE::at(u).toString(tmp) << endi;
}
else if (!vRed && uRed)
{
debug_log << "删除黑色节点，替换节点红色改为黑色" << endi;
TREE_NODE::at(u).bColorRed = false;
}
else
{
debug_log << "删除双黑节点================================================" << endi;
ret = _RB_erase_Balance(p, u);
}
debug();
if (ret)__erase_node(position);
if (-1 != tree_head->hHead)TREE_NODE::at(tree_head->hHead).bColorRed = false;
return ret;
}
string show(T_SHM_SIZE position)
{
char buf[2048];
string tmp;
TREE_NODE::at(position).toString(tmp);
sprintf_s(buf, 2048, "%lld : %s", position, tmp.c_str());
return buf;
}
public:
//如果second为false则已经存在，发生了覆盖，用GetOldValue获得被覆盖的值
pair<iterator, bool> insert(T_DATA const& data)
{
T_COMP comp;
return insert(data, comp);
}
pair<iterator, bool> insert(T_DATA const& data, T_COMP& comp)
{
m_OldValueSeted = false;//清除被覆盖对象的有效标志
pair<iterator, bool> ret;
ret.first = end();
ret.second = false;
if (tree_head->free_head < 0 && m_array.Capacity() <= m_array.Size())
{
thelog << "超出容量限制" << ende;
return ret;
}
try
{
ret = _insert(data, comp);
}
catch (exception& e)
{
thelog << e.what() << ende;
}
//thelog<<"insert ret "<<ret.first.handle<<" "<<ret.second<<endi;
return ret;
}
//返回被覆盖的值，如果最近的操作没有发生覆盖则false
bool GetOldValue(T_DATA& ret)const
{
if (m_OldValueSeted)
{
ret = m_OldValue;
return true;
}
else
{
return false;
}
}
template<typename T_FIND >
const_iterator find(T_FIND const& tmp)const
{
T_COMP comp;
const_iterator it = lower_bound<T_FIND >(tmp);
if (it != end())
{
if (comp(*it, tmp) || comp(tmp, *it))return end();
}
return it;
}
const_iterator find(T_DATA const& tmp, T_COMP& comp)const
{
const_iterator it = lower_bound(tmp, comp);
if (it != end())
{
if (comp(*it, tmp) || comp(tmp, *it))return end();
}
return it;
}
bool erase(const_iterator it)
{
T_COMP comp;
return erase(it, comp);
}
//删除并指向下一个
iterator& DeleteAndMoveNext(iterator& it)
{
if (end() == it)return it;
iterator& ret = it;
iterator tmp = ret;
++ret;
erase(tmp);
return ret;
}
bool erase(const_iterator it, T_COMP& comp)
{
if (it.handle < 0)return true;
//DEBUG_LOG<<"要删除节点"<<show(it.handle)<<endi;
bool ret = _erase(it.handle);
return ret;
}
bool erase(T_DATA const& data)
{
T_COMP comp;
return erase(data, comp);
}
bool erase(T_DATA const& data, T_COMP& comp)
{
const_iterator it = find(data, comp);
if (it.handle < 0)return true;
return erase(it, comp);
}
//用全比较函数，实际是find的功能
template<typename T_FIND >
const_iterator lower_bound(T_FIND const& tmp)const
{
T_COMP comp;
const_iterator it;
T_SHM_SIZE hNode = tree_head->hHead;
it.handle = -1;
while (-1 != hNode)
{
if (comp(tmp, TREE_NODE::at(hNode).data))
{
it.handle = hNode;
hNode = TREE_NODE::at(hNode).hLeft;
}
else if (comp(TREE_NODE::at(hNode).data, tmp))
{
hNode = TREE_NODE::at(hNode).hRight;
}
else
{
it.handle = hNode;
break;
}
}
return it;
}
//用部分比较函数（但必须是符合顺序的，否则结果不可预期）
template<typename T_FIND, typename T_LESS_BOUND >
const_iterator lower_bound(T_FIND const& tmp, T_LESS_BOUND comp)const
{
const_iterator it;
T_SHM_SIZE hNode = tree_head->hHead;
it.handle = -1;
while (-1 != hNode)
{
if (comp(tmp, TREE_NODE::at(hNode).data))
{
it.handle = hNode;
hNode = TREE_NODE::at(hNode).hLeft;
}
else if (comp(TREE_NODE::at(hNode).data, tmp))
{
hNode = TREE_NODE::at(hNode).hRight;
}
else
{
it.handle = hNode;
hNode = TREE_NODE::at(hNode).hLeft;
}
}
return it;
}
//用部分比较函数（但必须是符合顺序的，否则结果不可预期）
template<typename T_FIND, typename T_LESS_BOUND >
const_iterator upper_bound(T_FIND const& tmp, T_LESS_BOUND comp)const
{
const_iterator it;
T_SHM_SIZE hNode = tree_head->hHead;
it.handle = -1;
while (-1 != hNode)
{
if (comp(tmp, TREE_NODE::at(hNode).data))
{
it.handle = hNode;
hNode = TREE_NODE::at(hNode).hLeft;
}
else if (comp(TREE_NODE::at(hNode).data, tmp))
{
hNode = TREE_NODE::at(hNode).hRight;
}
else
{
hNode = TREE_NODE::at(hNode).hRight;
}
}
return it;
}
//检查一个节点是否已经删除，必须是有效参数
bool IsDeleted(T_SHM_SIZE handle)const
{
if (handle < 0 || handle >= m_array.capacity())return false;
return TREE_NODE::at(handle).deleted;
}
};四、测试代码main.cpp
#include <iostream>
#include <vector>
#include "rbtree.h"
bool G_IS_DEBUG;
TREE_NODE g_array[ARRAY_CAPACITY];
TREE_NODE& TREE_NODE::at(T_SHM_SIZE n)
{
return g_array[n];
}
T_SHM_SIZE TREE_NODE::_me()const
{
return this - g_array;
}
//日志用格式
string TimeToString_log(time_t const & t1)
{
if (0 == t1)return "";
tm const * t2;
char buf[256];
t2 = localtime(&t1);
sprintf(buf, "%02d-%02d %02d:%02d:%02d", t2->tm_mon + 1, t2->tm_mday, t2->tm_hour, t2->tm_min, t2->tm_sec);
return buf;
}
bool test(int _seed, int count)
{
CRBTree rbtree;
T_DATA a;
srand(_seed);
vector<T_SHM_SIZE > datas;
for (T_SHM_SIZE i = 0; i < count; ++i)
{
datas.push_back(rand());
}
debug_log << rbtree.size() << " " << rbtree.capacity() << endi;
for (T_SHM_SIZE v : datas)
{
a.n = v;
debug_log << a.n << endi;
rbtree.insert(a);
}
debug_log << rbtree.size() << " " << rbtree.capacity() << endi;
rbtree._check();
rbtree._check_rbtree();
// CRBTree::const_iterator it = rbtree.begin();
// for (; it != rbtree.end(); ++it)
// {
// string tmp1,tmp2;
//thelog <<"h "<< it.handle << " 值：" << it->toString(tmp1) << " TREE_NODE：" << TREE_NODE::at(it.handle).toString(tmp2) << endi;
// }
Table table;
rbtree._check_show_tree(table, rbtree.tree_head->hHead);
debug_log << endl << table.MakeTextTable() << endi;
bool ret = true;
for (T_SHM_SIZE v : datas)
{
a.n = v;
debug_log << a.n << endi;
ret = rbtree.erase(a) && rbtree._check() && rbtree._check_rbtree();
if (G_IS_DEBUG)
{
Table table;
rbtree._check_show_tree(table, rbtree.tree_head->hHead);
thelog << endl << table.MakeTextTable() << endi;
}
if (!ret)break;
}
//CRBTree::const_iterator it = rbtree.begin();
//for (; it != rbtree.end(); ++it)
//{
// string tmp1, tmp2;
// thelog << "h " << it.handle << " 值：" << it->toString(tmp1) << " TREE_NODE：" << TREE_NODE::at(it.handle).toString(tmp2) << endi;
//}
return ret;
}
int main()
{
G_IS_DEBUG = true;//大数据量测试时先设置为false，然后把后面循环的次数调大
int count = 10;//每次测试的数据量，上限为 ARRAY_CAPACITY;
for (int i = 0; i < 1; ++i)
{
if (!test(i, count))
{
G_IS_DEBUG = true;
thelog << "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@" << endi;
test(i, count);
thelog << "失败 i= " << i << endi;
return 1;
}
thelog << TimeToString_log(time(NULL)) << " " << i << endi;
//break;
}
return 0;
}
五、运行效果
以上三个代码就是全部代码，建立新工程，保存辅助代码和红黑树代码，用测试代码替换主代码，然后编译运行应该是没问题的。
运行效果：
由于是打开调试执行的，有很多输出，每一次改变树结构都有树形显示。
最后结果：
注意删除最后一个节点时调试输出为“删除红色节点，不用调整”，但是根节点其实是黑色的。这是因为代码里的临时变量把最后一个节点指示为红色，防止后面执行调整代码。这里算是个小缺陷吧（本该使用一个独立变量来指示的）。
六、代码详解
算法实战：亲自写红黑树之三 算法详解-CSDN博客
（这里是结束）
