学步园

公司算法库中不希望包含STL,BOOST之类的库，很多基础算法都需要自己写。下边的代码是用红黑树实现的MAP模板类，测试无误，贴出来供参考。实现了插入·查找·删除等主要功能。因为没有加额外的容器，迭代器，所以速度比STL的快很多, 用20000000数据进行查找·删除·插入测试结果如下：

STL MAP:
Begin!

Insert Data ...
Insert End! time:47
Del Test ...
del End! time:28
Search Test ...
Search End! time:20
End!

MY MAP:
Begin!

Insert Data ...
Insert End! time:30
Del Test ...
del End! time:18
Search Test ...
Search End! time:11
End!

#ifndef _MAP_H_<br /> #define _MAP_H_</p> <p>#ifndef NULL<br /> #define NULL 0<br /> #endif</p> <p>template<class K, class V, class C></p> <p>class map<br /> {<br /> public:<br /> explicit map();</p> <p> ~map(){}</p> <p>public:<br /> enum { BLACK, RED, NIL };</p> <p> typedef struct<br /> {<br /> K k_value;<br /> V v_value;<br /> }Pair;</p> <p> struct RBTNode<br /> {<br /> Pair Obj;<br /> char Color;<br /> RBTNode* Parent;<br /> RBTNode* Lchild;<br /> RBTNode* Rchild;<br /> };</p> <p>public:<br /> void Insert(const Pair& pair);<br /> Pair* Find(const K& kvalue);</p> <p> Pair* operator [] (const K& kvalue);<br /> void Erase(const K& kvalue);<br /> void Clear();</p> <p>protected:<br /> void InsertFixup(RBTNode* newNode);<br /> void DeleteFixup(RBTNode* node);<br /> RBTNode* /<br /> UncleNode(RBTNode* node) { return node->Parent == node->Parent->Parent->Lchild/<br /> ? node->Parent->Parent->Rchild : node->Parent->Parent->Lchild; }</p> <p> RBTNode* /<br /> BrotherNode(RBTNode* node) { return node == node->Parent->Lchild ? node->Parent->Rchild/<br /> : node->Parent->Lchild; }</p> <p> void RotateRight(RBTNode* node)<br /> {<br /> RBTNode* lchild = node->Lchild;</p> <p> node->Lchild = lchild->Rchild;<br /> node->Lchild->Parent = node;</p> <p> lchild->Parent = node->Parent;<br /> if(NULL == node->Parent)<br /> _root = lchild;<br /> else if(node == node->Parent->Rchild)<br /> node->Parent->Rchild = lchild;<br /> else<br /> node->Parent->Lchild = lchild;</p> <p> node->Parent = lchild;<br /> lchild->Rchild = node;<br /> }</p> <p> void RotateLeft(RBTNode* node)<br /> {<br /> RBTNode* rchild = node->Rchild;</p> <p> node->Rchild = rchild->Lchild;<br /> node->Rchild->Parent = node;</p> <p> rchild->Parent = node->Parent;<br /> if(NULL == node->Parent)<br /> _root = rchild;<br /> else if(node == node->Parent->Rchild)<br /> node->Parent->Rchild = rchild;<br /> else<br /> node->Parent->Lchild = rchild;</p> <p> node->Parent = rchild;<br /> rchild->Lchild = node;<br /> }</p> <p>protected:<br /> RBTNode* _root;<br /> int _size;<br /> C _comp;<br /> };</p> <p>template<class K, class V, class C><br /> map<K,V,C>::map(void)<br /> {<br /> _root = new RBTNode;</p> <p> _root->Parent = NULL;<br /> _root->Color = NIL;</p> <p> _size = 0;<br /> }</p> <p>template<class K, class V, class C><br /> typename map<K,V,C>::Pair* map<K,V,C>::Find(const K& kvalue)<br /> {<br /> RBTNode* tmpNode = _root;<br /> while(tmpNode->Color != NIL)<br /> {<br /> if(!_comp(tmpNode->Obj.k_value, kvalue) && !_comp(kvalue, tmpNode->Obj.k_value))<br /> {<br /> return &tmpNode->Obj;<br /> }</p> <p> if(_comp(tmpNode->Obj.k_value, kvalue))<br /> {<br /> tmpNode = tmpNode->Rchild;<br /> }<br /> else<br /> {<br /> tmpNode = tmpNode->Lchild;<br /> }<br /> }<br /> return NULL;<br /> }</p> <p>template<class K, class V, class C><br /> typename map<K,V,C>::Pair* map<K,V,C>::operator [](const K& kvalue)<br /> {<br /> return Find(kvalue);<br /> }</p> <p>template<class K, class V, class C><br /> void map<K,V,C>::Clear()<br /> {<br /> RBTNode* node = _root, *tmp;</p> <p> while(NULL != node)<br /> {<br /> if(NIL == node->Color || NULL == node->Lchild && NULL == node->Rchild)<br /> {<br /> tmp = node;<br /> node = node->Parent;<br /> if(NULL != node)<br /> {<br /> if(tmp == node->Lchild)<br /> node->Lchild = NULL;<br /> else<br /> node->Rchild = NULL;<br /> }<br /> delete tmp;</p> <p> }</p> <p> if(NULL != node)<br /> {<br /> if(NULL != node->Lchild)<br /> node = node->Lchild;<br /> else if(NULL != node->Rchild)<br /> node = node->Rchild;<br /> }<br /> }<br /> }</p> <p>template<class K, class V, class C><br /> void map<K,V,C>::Insert(const Pair& pair)<br /> {<br /> RBTNode* tmpNode = _root;</p> <p> while(tmpNode->Color != NIL)<br /> {<br /> if(!_comp(tmpNode->Obj.k_value, pair.k_value) && !_comp(pair.k_value, tmpNode->Obj.k_value))<br /> {<br /> tmpNode->Obj = pair;<br /> return;<br /> }</p> <p> if(_comp(tmpNode->Obj.k_value, pair.k_value))<br /> tmpNode = tmpNode->Rchild;<br /> else<br /> tmpNode = tmpNode->Lchild;<br /> }</p> <p> tmpNode->Color = RED;<br /> tmpNode->Obj = pair;<br /> tmpNode->Lchild = new RBTNode;<br /> tmpNode->Rchild = new RBTNode;</p> <p> tmpNode->Lchild->Parent = tmpNode;<br /> tmpNode->Rchild->Parent = tmpNode;</p> <p> tmpNode->Lchild->Color = NIL;<br /> tmpNode->Rchild->Color = NIL;</p> <p> InsertFixup(tmpNode);<br /> }</p> <p>template<class K, class V, class C><br /> void map<K,V,C>::InsertFixup(RBTNode* newNode)<br /> {<br /> if(NULL == newNode->Parent)<br /> {<br /> newNode->Color = BLACK;<br /> return;<br /> }</p> <p> if(BLACK == newNode->Parent->Color)<br /> return;</p> <p> RBTNode* tmp = UncleNode(newNode);<br /> if(RED == tmp->Color)<br /> {<br /> tmp->Color = BLACK;<br /> newNode->Parent->Color = BLACK;<br /> newNode->Parent->Parent->Color = RED;</p> <p> InsertFixup(newNode->Parent->Parent);<br /> return;<br /> }</p> <p> if(newNode == newNode->Parent->Lchild && newNode->Parent/<br /> == newNode->Parent->Parent->Rchild)<br /> {<br /> RotateRight(newNode->Parent);<br /> newNode = newNode->Rchild;<br /> }</p> <p> else if(newNode == newNode->Parent->Rchild && newNode->Parent/<br /> == newNode->Parent->Parent->Lchild)<br /> {<br /> RotateLeft(newNode->Parent);<br /> newNode = newNode->Lchild;<br /> }</p> <p> newNode->Parent->Color = BLACK;<br /> newNode->Parent->Parent->Color = RED;</p> <p> if(newNode == newNode->Parent->Lchild)<br /> RotateRight(newNode->Parent->Parent);<br /> else<br /> RotateLeft(newNode->Parent->Parent);<br /> }</p> <p>template<class K, class V, class C><br /> void map<K,V,C>::Erase(const K& kvalue)<br /> {<br /> RBTNode* node = _root;</p> <p> while(NIL != node->Color)<br /> {<br /> if(!_comp(kvalue, node->Obj.k_value) && !_comp(node->Obj.k_value, kvalue))<br /> break;</p> <p> if(_comp(node->Obj.k_value, kvalue))<br /> node = node->Rchild;<br /> else<br /> node = node->Lchild;<br /> }</p> <p> if(NIL == node->Color)<br /> return;</p> <p> if(NIL == node->Rchild->Color && NIL == node->Lchild->Color)<br /> {<br /> delete node->Rchild;<br /> delete node->Lchild;</p> <p> if(RED == node->Color)<br /> node->Color = NIL;</p> <p> else<br /> {<br /> node->Color = NIL;<br /> DeleteFixup(node);<br /> }<br /> }<br /> else if(NIL != node->Lchild->Color)<br /> {<br /> RBTNode* tmpDel = node->Lchild, *replace;</p> <p> while(NIL != tmpDel->Rchild->Color)<br /> tmpDel = tmpDel->Rchild;<br /> node->Obj = tmpDel->Obj; </p> <p> replace = tmpDel->Rchild->Color != NIL ? tmpDel->Rchild : tmpDel->Lchild;</p> <p> if(replace == tmpDel->Rchild)<br /> delete tmpDel->Lchild;<br /> else<br /> delete tmpDel->Rchild;</p> <p> replace->Parent = tmpDel->Parent;</p> <p> if(replace->Parent == NULL)<br /> _root = replace;<br /> else if(tmpDel == tmpDel->Parent->Rchild)<br /> tmpDel->Parent->Rchild = replace;<br /> else<br /> tmpDel->Parent->Lchild = replace;</p> <p> if(BLACK == tmpDel->Color)<br /> {<br /> if(RED == replace->Color)<br /> replace->Color = BLACK;<br /> else<br /> DeleteFixup(replace);<br /> }<br /> delete tmpDel;<br /> }<br /> else<br /> {<br /> RBTNode* tmpDel = node->Rchild, *replace;</p> <p> while(NIL != tmpDel->Lchild->Color)<br /> tmpDel = tmpDel->Lchild;<br /> node->Obj = tmpDel->Obj; </p> <p> replace = tmpDel->Rchild->Color != NIL ? tmpDel->Rchild : tmpDel->Lchild;</p> <p> if(replace == tmpDel->Rchild)<br /> delete tmpDel->Lchild;<br /> else<br /> delete tmpDel->Rchild;</p> <p> replace->Parent = tmpDel->Parent;</p> <p> if(replace->Parent == NULL)<br /> _root = replace;<br /> else if(tmpDel == tmpDel->Parent->Rchild)<br /> tmpDel->Parent->Rchild = replace;<br /> else<br /> tmpDel->Parent->Lchild = replace;</p> <p> if(BLACK == tmpDel->Color)<br /> {<br /> if(RED == replace->Color)<br /> replace->Color = BLACK;<br /> else<br /> DeleteFixup(replace);<br /> }<br /> delete tmpDel;<br /> }</p> <p>}</p> <p>template<class K, class V, class C><br /> void map<K,V,C>::DeleteFixup(RBTNode* node)<br /> {<br /> if(NULL == node->Parent)<br /> return;</p> <p> RBTNode* brother = BrotherNode(node);</p> <p> if(RED == brother->Color)<br /> {<br /> node->Parent->Color = RED;<br /> brother->Color = BLACK;</p> <p> if(node == node->Parent->Lchild)<br /> RotateLeft(node->Parent);<br /> else<br /> RotateRight(node->Parent);<br /> }</p> <p> brother = BrotherNode(node);</p> <p> if(RED != node->Parent->Color &&/<br /> RED != brother->Color &&/<br /> RED != brother->Lchild->Color &&/<br /> RED != brother->Rchild->Color)<br /> {<br /> brother->Color = RED;<br /> DeleteFixup(node->Parent);<br /> }<br /> else<br /> {<br /> if(RED == node->Parent->Color &&/<br /> RED != brother->Color &&/<br /> RED != brother->Lchild->Color &&/<br /> RED != brother->Rchild->Color)<br /> {<br /> brother->Color = RED;<br /> node->Parent->Color = BLACK;<br /> }<br /> else<br /> {<br /> if(node == node->Parent->Lchild &&/<br /> brother->Lchild->Color == RED &&/<br /> brother->Rchild->Color != RED)<br /> {<br /> brother->Color = RED;<br /> brother->Lchild->Color = BLACK;<br /> RotateRight(brother);<br /> }<br /> else if(node == node->Parent->Rchild &&/<br /> brother->Lchild->Color != RED &&/<br /> brother->Rchild->Color == RED)<br /> {<br /> brother->Color = RED;<br /> brother->Rchild->Color = BLACK;<br /> RotateLeft(brother);<br /> }</p> <p> brother = BrotherNode(node);</p> <p> brother->Color = node->Parent->Color;<br /> node->Parent->Color = BLACK;</p> <p> if(node == node->Parent->Lchild)<br /> {<br /> brother->Rchild->Color = BLACK;<br /> RotateLeft(node->Parent);<br /> }<br /> else<br /> {<br /> brother->Lchild->Color = BLACK;<br /> RotateRight(node->Parent);<br /> }<br /> }<br /> }<br /> }</p> <p>#endif

基础不好的童鞋注意：模板中的class c是要自己实现的哟，比如：

struct Point<br /> {<br /> int x;<br /> int y;<br /> };</p> <p>class cmp<br /> {<br /> public:<br /> bool operator()(const Point& a, const Point& b) const<br /> {<br /> return a.x < b.x;<br /> }<br /> };