算法实战：亲自写红黑树之三 算法详解
此文承接：算法实战：亲自写红黑树之一-CSDN博客
算法实战：亲自写红黑树之二 完整代码-CSDN博客
目录
一、底层抽象
二、基本定义
三、TREE_NODE树节点结构
四、CRBTree容器结构
五、结构检查函数
六、插入的平衡算法
七、删除的平衡算法
一、底层抽象
之前已经反复说过，我搞的东西都是在共享内存上运行的，不能使用指针，也就是相当于是在固定大小的数组上操作，实际实现考虑的东西还更多一些，所以对底层做了抽象。
底层数据节点有一个索引位置，就是数组元素索引，有符号整数，定义为T_SHM_SIZE，-1代表无效。
从索引到实际位置通过接口转换，具体实现为TREE_NODE的静态成员at(n)，这是个关键点。测试代码使用的是静态数组，相关代码如下：
====================红黑树头文件：
typedef long long T_SHM_SIZE;
//静态数组大小
#define ARRAY_CAPACITY 10000
====================测试代码文件：
//静态数组
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;
}
二、基本定义
本代码原来是模板代码，适用于各种不同的数据结构，所以沿用了几个类型定义：
T_DATA 用户数据类型
T_COMP 用户数据类型的比较方式，默认是less
在这个测试代码里面将两个定义实现为：
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;
由于相关代码实现的原因，用户数据类型必须按照CDemoData的样式写（也就是模板代码用到了这些功能），不支持简单类型。其实也不是没法支持简单类型，只不过因为实践中不可能在共享内存放简单类型，所以一开始没考虑，后来再修改需要改的地方就多了。
三、TREE_NODE树节点结构
终于到了跟树有关的部分，树节点的结构和一般的树结点的结构相比多了删除标志deleted，因为数据是放在数组里面的，删除了位置还在，虽然说删除的节点位于删除链表，无法从树结构访问到，理论上并不需要额外的删除标志，但是为了检查数据结构有这个标志会好很多（由于共享内存的共享性，数据结构被破坏是比较频繁的）。另外由于对齐原因，多一个这个并不会增加树节点大小。
树节点结构如下：
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;
树节点有一些内置方法，很容易理解。
四、CRBTree容器结构
由于对底层做了抽象，容器内部包含一个数组对象T_SETARRAY，由这个对象提供底层数据，实际用到的就是添加（删除的属于树的删除链表，并不会归还给数组）。
容器的另外一个数据成员就是TREE_HEAD指针，为什么是指针呢？因为共享内存是独立存在的，大部分操作是连接到已经存在的数据上去，所以是指针，包含的数组对象内部实际也同样是指针。
在这个测试代码中直接内置了一个TREE_HEAD结构，以便与模板代码保持一致：
private:
TREE_HEAD _tree_head;为了与共享内存操作一致，这个变量不可直接使用，只能使用tree_head
......
public:
T_SETARRAY m_array;//内置数组对象，存储实际数据
TREE_HEAD* tree_head = &_tree_head;//指向树的头
TREE_HEAD结构：
struct TREE_HEAD
{
T_SHM_SIZE hHead;
T_SHM_SIZE size;
T_SHM_SIZE free_head;//空闲地址头指针
};
底层数组T_SETARRAY结构：
struct T_SETARRAY
{
//新版数组头
struct array_head
{
T_SHM_SIZE capacity;
T_SHM_SIZE size;
};
array_head _array_head;这个本来也是在共享内存的，所以不可直接使用，只能使用GetHead()
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;
}
}
};
由于本代码底层用了静态数组，所以这个结构修改了内部实现，仅仅保持接口和原来相同。这个结构与算法基本没什么关系，不用太关注。
容器还定义了迭代器iterator，符合一般的规则，代码也很简单。
容器初始化很简单：
CRBTree() :m_OldValueSeted(false)
{
m_array._array_head.capacity = ARRAY_CAPACITY;
m_array._array_head.size = 0;
}
初始化了数组的容量和大小。如果是共享内存，这些数据就要从共享内存获得。当然，这跟算法没什么关系。
五、结构检查函数
有一组结构检查函数，用于检查数据是否正确。
- bool _check_handle(T_SHM_SIZE h)const 检查h是否合法，必须大于等于-1，注意，不是检查是否是数据节点
- bool _check_is_data_node(T_SHM_SIZE h)const 这才是检查是否是数据节点，不能是-1
- T_SHM_SIZE _check_get_count(T_SHM_SIZE h) 获取节点总数，包括自身
- void _check_show_tree(......) 显示树形结构
- void debug() 无参数，显示整个树形结构
- bool _check_rbtree() 检查红黑树特征，主要是调用下一个函数
- bool _check_rbtree_count(......) 递归检测红黑树特征
- bool _check()const 检查普通树特征，先调用这个检查树结构，再调用_check_rbtree检查红黑树特征
六、插入的平衡算法
算法实战：亲自写红黑树之四 插入insert的平衡-CSDN博客
七、删除的平衡算法
算法实战：亲自写红黑树之五 删除erase的平衡-CSDN博客
（这里是结束）