最近看到講解紅黑樹時, 感覺其中代碼寫得很不錯. 自己受益匪淺, 首先STL關(guān)聯(lián)容器中map和set是由紅黑樹實現(xiàn)的.而符合STL的標(biāo)準(zhǔn), 則必須提供begin() 和 end() 2個迭代器, 那么在STL的紅黑樹中是怎么表示這兩個迭代器的呢?
紅黑樹的結(jié)點結(jié)構(gòu):
template<typename T>
struct RBTreeNode{
T data;
bool ColorType;
RBTreeNode *parent;
RBTreeNode *leftChild;
RBTreeNode *rightChild;
};
STL用的方法是用一個虛擬的_header結(jié)點, 其leftChild指向整棵樹中最小的結(jié)點(最左結(jié)點), 其中rightChild指向整棵樹中最大的結(jié)點(最右結(jié)點). 其parent指向根節(jié)點root, 而begin() 所指向的是_header結(jié)點的左leftChild結(jié)點, 而end()所指向的是虛擬結(jié)點_header本身.
初始化如下圖所示:
初始化.jpg
插入一個結(jié)點:
插入一個結(jié)點.jpg
插入n個結(jié)點:
插入n個結(jié)點.jpg
好, 現(xiàn)在把基礎(chǔ)結(jié)構(gòu)描述清楚后, 據(jù)可以寫具體迭代器++ 和迭代器--的操作了.
本來想寫個玩具STL匕坯， 更一系列的文章哨坪，但學(xué)校破事太多润歉，看來只有暑假在做這個事了，平時就寫些零散的權(quán)當(dāng)復(fù)習(xí)準(zhǔn)備秋招了。
