最近看到讲解红黑树时, 感觉其中代码写得很不错. 自己受益匪浅, 首先STL关联容器中map和set是由红黑树实现的.而符合STL的标准, 则必须提供begin() 和 end() 2个迭代器, 那么在STL的红黑树中是怎么表示这两个迭代器的呢?
红黑树的结点结构:
template<typename T>
struct RBTreeNode{
T data;
bool ColorType;
RBTreeNode *parent;
RBTreeNode *leftChild;
RBTreeNode *rightChild;
};
STL用的方法是用一个虚拟的_header结点, 其leftChild指向整棵树中最小的结点(最左结点), 其中rightChild指向整棵树中最大的结点(最右结点). 其parent指向根节点root, 而begin() 所指向的是_header结点的左leftChild结点, 而end()所指向的是虚拟结点_header本身.
初始化如下图所示:
初始化.jpg
插入一个结点:
插入一个结点.jpg
插入n个结点:
插入n个结点.jpg
好, 现在把基础结构描述清楚后, 据可以写具体迭代器++ 和迭代器--的操作了.
本来想写个玩具STL， 更一系列的文章，但学校破事太多，看来只有暑假在做这个事了，平时就写些零散的权当复习准备秋招了。
