最近看到講解紅黑樹時, 感覺其中代碼寫得很不錯. 自己受益匪淺, 首先STL關(guān)聯(lián)容器中map和set是由紅黑樹實(shí)現(xiàn)的.而符合STL的標(biāo)準(zhǔn), 則必須提供begin() 和 end() 2個迭代器, 那么在STL的紅黑樹中是怎么表示這兩個迭代器的呢?
紅黑樹的結(jié)點(diǎn)結(jié)構(gòu):

template<typename T>
struct RBTreeNode{
    T data;
    bool ColorType;
    RBTreeNode *parent;
    RBTreeNode *leftChild;
    RBTreeNode *rightChild;
};

STL用的方法是用一個虛擬的_header結(jié)點(diǎn), 其leftChild指向整棵樹中最小的結(jié)點(diǎn)(最左結(jié)點(diǎn)), 其中rightChild指向整棵樹中最大的結(jié)點(diǎn)(最右結(jié)點(diǎn)). 其parent指向根節(jié)點(diǎn)root, 而begin() 所指向的是_header結(jié)點(diǎn)的左leftChild結(jié)點(diǎn), 而end()所指向的是虛擬結(jié)點(diǎn)_header本身.
初始化如下圖所示:

初始化.jpg

插入一個結(jié)點(diǎn):

插入一個結(jié)點(diǎn).jpg

插入n個結(jié)點(diǎn):

插入n個結(jié)點(diǎn).jpg

好, 現(xiàn)在把基礎(chǔ)結(jié)構(gòu)描述清楚后, 據(jù)可以寫具體迭代器++ 和迭代器--的操作了.
本來想寫個玩具STL， 更一系列的文章，但學(xué)校破事太多，看來只有暑假在做這個事了，平時就寫些零散的權(quán)當(dāng)復(fù)習(xí)準(zhǔn)備秋招了。