[原创]红黑树.(页 1) - C++论坛 - C++教室

中学者 发表于 2008-5-24 19:25

[原创]红黑树.

希望对大家有帮助,,,,,一起进步......
PS:  在C区发过的，但是还是应该发在这里...
[quote][font=新宋体][size=2][color=#008000]/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) [url]http://yzfy.org[/url] **
*****************************************************************/
[/color][color=#0000FF]enum [/color][color=#800080]COLOR [/color][color=#800000]{ [/color][color=#800080]RED[/color],[color=#800080]BLACK [/color][color=#800000]}[/color];
[color=#0000FF]template[/color]<typename Ty>
[color=#0000FF]struct [/color]node
[color=#800000]{
[/color][color=#0000FF]int [/color]key;
Ty data;
node<Ty>* leftchild;
node<Ty>* rightchild;
node<Ty>* parent;
[color=#800080]COLOR [/color]color;
[color=#008080]node[/color]([color=#0000FF]const [/color]Ty& v,[color=#0000FF]int [/color]k):[color=#008080]data[/color](v)
[color=#800000]{
      [/color]key = k;
      color = [color=#800080]RED[/color];
      leftchild = rightchild = parent =[color=#800080]0[/color];
[color=#800000]}
[/color][color=#008080]node[/color]()[color=#800000]{ [/color]color = [color=#800080]BLACK[/color]; [color=#800000]}
} [/color];
[color=#0000FF]template[/color]<typename _value>
[color=#0000FF]class [/color][color=#800080]BBST
[/color][color=#800000]{
[/color][color=#0000FF]public[/color]:
[color=#0000FF]virtual [/color]~[color=#800080]BBST[/color]() = [color=#800080]0[/color];
[color=#0000FF]virtual void [/color][color=#008080]Insert[/color]([color=#0000FF]const [/color]_value& value,[color=#0000FF]int [/color]key)=[color=#800080]0[/color];
[color=#0000FF]virtual const [/color]node<_value>* [color=#008080]Delete[/color]([color=#0000FF]int [/color]key) =[color=#800080]0[/color];
[color=#0000FF]virtual const [/color]node<_value>* [color=#008080]Search[/color]([color=#0000FF]int [/color]key) [color=#0000FF]const[/color];

[color=#0000FF]bool [/color][color=#008080]empty[/color]() [color=#0000FF]const [/color];
[color=#0000FF]int [/color][color=#FF8000]size[/color]() [color=#0000FF]const [/color];
[color=#0000FF]int [/color][color=#008080]height[/color]() [color=#0000FF]const [/color];

[color=#0000FF]void [/color][color=#008080]InOrder[/color]() [color=#0000FF]const [/color];
[color=#0000FF]void [/color][color=#008080]PostOrder[/color]() [color=#0000FF]const [/color];
[color=#0000FF]void [/color][color=#008080]PreOrder[/color]() [color=#0000FF]const [/color];
[color=#0000FF]void [/color][color=#008080]LevelOrder[/color]() [color=#0000FF]const [/color];
[color=#0000FF]protected[/color]:
node<_value>* root;
node<_value>* null;
[color=#0000FF]int [/color]countNode;
[color=#0000FF]protected[/color]:
[color=#0000FF]virtual void [/color][color=#008080]LeftRotate[/color](node<_value>* parent,node<_value>* child) =[color=#800080]0[/color];
[color=#0000FF]virtual void [/color][color=#008080]RightRotate[/color](node<_value>* parent,node<_value>* child) =[color=#800080]0[/color];
node<_value>* [color=#008080]successor[/color](node<_value>* current) [color=#0000FF]const[/color];
node<_value>* [color=#008080]predecessor[/color](node<_value>* current) [color=#0000FF]const[/color];
node<_value>* [color=#008080]search[/color]([color=#0000FF]int [/color]skey) [color=#0000FF]const[/color];
[color=#0000FF]private[/color]:
[color=#0000FF]int [/color][color=#008080]height[/color]([color=#0000FF]const [/color]node<_value>* root) [color=#0000FF]const[/color];
[color=#0000FF]void [/color][color=#008080]inorder[/color]([color=#0000FF]const [/color]node<_value>* root) [color=#0000FF]const [/color];
[color=#0000FF]void [/color][color=#008080]inorder[/color](node<_value>& root) [color=#0000FF]const [/color];
[color=#0000FF]void [/color][color=#008080]postorder[/color]([color=#0000FF]const [/color]node<_value>* root) [color=#0000FF]const [/color];
[color=#0000FF]void [/color][color=#008080]postorder[/color](node<_value>& root) [color=#0000FF]const [/color];
[color=#0000FF]void [/color][color=#008080]preorder[/color]([color=#0000FF]const [/color]node<_value>* root) [color=#0000FF]const [/color];
[color=#0000FF]void [/color][color=#008080]preorder[/color](node<_value>& root) [color=#0000FF]const [/color];
node<_value>* [color=#008080]Minimum[/color](node<_value>* current) [color=#0000FF]const[/color];
node<_value>* [color=#008080]Maximum[/color](node<_value>* current) [color=#0000FF]const[/color];
[color=#800000]}[/color];
[color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]inline [/color][color=#800080]BBST[/color]<_Ty>::~[color=#800080]BBST[/color]() [color=#800000]{}
[/color][color=#008000]// const node<_Ty>* Search(int key) const
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]inline const [/color]node<_Ty>* [color=#800080]BBST[/color]<_Ty>::[color=#008080]Search[/color]([color=#0000FF]int [/color]skey) [color=#0000FF]const
[/color][color=#800000]{
      [/color][color=#0000FF]return [/color][color=#008080]search[/color](skey);
[color=#800000]}
[/color][color=#0000FF]template[/color]<typename _Ty>
node<_Ty>* [color=#800080]BBST[/color]<_Ty>::[color=#008080]search[/color]([color=#0000FF]int [/color]skey) [color=#0000FF]const
[/color][color=#800000]{
      [/color][color=#0000FF]for[/color](node<_Ty>* current=root;current!=null; )
      [color=#800000]{
      [/color][color=#0000FF]if[/color](current->key == skey) [color=#0000FF]return [/color]current;
      [color=#0000FF]if[/color](current->key < skey) current = current->rightchild;
      [color=#0000FF]else [/color]current = current->leftchild;
      [color=#800000]}
      [/color][color=#0000FF]return [/color]null;
[color=#800000]}
[/color][color=#008000]// Minimum  and  Maximum
[/color][color=#0000FF]template[/color]<typename _Ty>
node<_Ty>* [color=#800080]BBST[/color]<_Ty>::[color=#008080]Minimum[/color](node<_Ty>* _node) [color=#0000FF]const
[/color][color=#800000]{
      [/color][color=#0000FF]for[/color](node<_Ty>* current=_node;current!=null;)
      [color=#800000]{
      [/color][color=#0000FF]if[/color]( current->leftchild!=null) current = current->leftchild;
      [color=#0000FF]else return [/color]current;
      [color=#800000]}
[/color][color=#0000FF]return [/color]null;
[color=#800000]}
[/color][color=#0000FF]template[/color]<typename _Ty>
node<_Ty>* [color=#800080]BBST[/color]<_Ty>::[color=#008080]Maximum[/color](node<_Ty>* _node) [color=#0000FF]const
[/color][color=#800000]{
      [/color][color=#0000FF]for[/color](node<_Ty>* current=_node;current!=null;)
      [color=#800000]{
         [/color][color=#0000FF]if[/color]( current->rightchild!=null) current = current->rightchild;
         [color=#0000FF]else return [/color]current;
      [color=#800000]}
[/color][color=#0000FF]return [/color]null;
[color=#800000]}
[/color][color=#008000]// successor  and  predecessor
[/color][color=#0000FF]template[/color]<typename _Ty>
node<_Ty>* [color=#800080]BBST[/color]<_Ty>::[color=#008080]successor[/color](node<_Ty>* current) [color=#0000FF]const
[/color][color=#800000]{
      [/color][color=#0000FF]if[/color]( current->rightchild!=null) [color=#0000FF]return [/color][color=#008080]Minimum[/color](current->rightchild);

      [color=#0000FF]for[/color](node<_Ty>* __node=current->parent;__node!=null;)
      [color=#800000]{
         [/color][color=#0000FF]if[/color](__node->leftchild == current)
         [color=#800000]{
            [/color]current = __node;
            __node = null;
         [color=#800000]}
         [/color][color=#0000FF]else
         [/color][color=#800000]{
            [/color]current = __node;
            __node = __node->parent;
         [color=#800000]}
      }
[/color][color=#0000FF]return [/color]current;
[color=#800000]}
[/color][color=#0000FF]template[/color]<typename _Ty>
node<_Ty>* [color=#800080]BBST[/color]<_Ty>::[color=#008080]predecessor[/color](node<_Ty>* current) [color=#0000FF]const
[/color][color=#800000]{
      [/color][color=#0000FF]if[/color]( current->leftchild!=null) [color=#0000FF]return [/color][color=#008080]Maximum[/color](current->leftchild);

      [color=#0000FF]for[/color](node<_Ty>* __node=current->parent;__node!=null;)
      [color=#800000]{
         [/color][color=#0000FF]if[/color](__node->rightchild == current)
         [color=#800000]{
            [/color]current = __node;
            __node = null;
         [color=#800000]}
         [/color][color=#0000FF]else
         [/color][color=#800000]{
            [/color]current = __node;
            __node = __node->parent;
         [color=#800000]}
      }
[/color][color=#0000FF]return [/color]current;
[color=#800000]}
[/color][color=#008000]// bool empty() const
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]inline bool [/color][color=#800080]BBST[/color]<_Ty>::[color=#008080]empty[/color]() [color=#0000FF]const
[/color][color=#800000]{
[/color][color=#0000FF]return [/color]root == null;
[color=#800000]}
[/color][color=#008000]// int size() const
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]inline int [/color][color=#800080]BBST[/color]<_Ty>::[color=#FF8000]size[/color]() [color=#0000FF]const
[/color][color=#800000]{
[/color][color=#0000FF]return [/color]countNode;
[color=#800000]}
[/color][color=#008000]// int height() const
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]inline int [/color][color=#800080]BBST[/color]<_Ty>::[color=#008080]height[/color]() [color=#0000FF]const
[/color][color=#800000]{
[/color][color=#0000FF]return [/color][color=#008080]height[/color](root);
[color=#800000]}
[/color][color=#008000]//    int height(const node<_Ty>* root) const
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]int [/color][color=#800080]BBST[/color]<_Ty>::[color=#008080]height[/color]([color=#0000FF]const [/color]node<_Ty>* root) [color=#0000FF]const
[/color][color=#800000]{
[/color][color=#0000FF]if[/color]( root==null ) [color=#0000FF]return [/color][color=#800080]0[/color];
[color=#0000FF]else return [/color][color=#008080]height[/color](root->leftchild)>[color=#008080]height[/color](root->rightchild)?
            [color=#008080]height[/color](root->leftchild)+[color=#800080]1[/color]:[color=#008080]height[/color](root->rightchild)+[color=#800080]1[/color];
[color=#800000]}
[/color][color=#008000]//    void InOrder() const
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color][color=#800080]BBST[/color]<_Ty>::[color=#008080]InOrder[/color]() [color=#0000FF]const
[/color][color=#800000]{
[/color][color=#008000]// srand((unsigned int)time(0));
[/color][color=#008080]inorder[/color](*root);
[color=#800000]}
[/color][color=#0000FF]template[/color]<typename _Ty >
[color=#0000FF]void [/color][color=#800080]BBST[/color]<_Ty>::[color=#008080]inorder[/color]([color=#0000FF]const [/color]node<_Ty>* root) [color=#0000FF]const
[/color][color=#800000]{
[/color][color=#0000FF]if[/color]( root!=null )
[color=#800000]{
      [/color][color=#008080]inorder[/color](root->leftchild);
      [color=#FF0000]std[/color]::[color=#FF0000]cout[/color]<<current->data<<[color=#FF8000]','
                  [/color]<<current->color<<[color=#FF00FF]" "[/color];
      [color=#008080]inorder[/color](root->rightchild);
[color=#800000]}
}
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color][color=#800080]BBST[/color]<_Ty>::[color=#008080]inorder[/color]( node<_Ty> & root) [color=#0000FF]const
[/color][color=#800000]{
[/color][color=#0000FF]using [/color][color=#FF0000]std[/color]::[color=#FF0000]deque[/color];
[color=#FF0000]deque[/color]<node<_Ty>*> que;
[color=#0000FF]for[/color](node<_Ty>* current=&root; current!=null|| !que.[color=#008080]empty[/color](); )
[color=#800000]{
      [/color][color=#0000FF]for[/color](;current!=null ; )
      [color=#800000]{
         [/color]que.[color=#008080]push_front[/color](current);
         current = current->leftchild;
      [color=#800000]}
      [/color]current = que.[color=#008080]front[/color]();
      que.[color=#008080]pop_front[/color]();
      [color=#FF0000]std[/color]::[color=#FF0000]cout[/color]<<current->data<<[color=#FF8000]','
            [/color]<<current->color<<[color=#FF00FF]" "[/color];
      current = current->rightchild;
[color=#800000]}
}
[/color][color=#008000]//    void PostOrder() const
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color][color=#800080]BBST[/color]<_Ty>::[color=#008080]PostOrder[/color]() [color=#0000FF]const
[/color][color=#800000]{
[/color][color=#008000]// srand((unsigned int)time(0));
[/color][color=#008080]postorder[/color](*root);
[color=#800000]}
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color][color=#800080]BBST[/color]<_Ty>::[color=#008080]postorder[/color]([color=#0000FF]const [/color]node<_Ty>* root) [color=#0000FF]const
[/color][color=#800000]{
[/color][color=#0000FF]if[/color]( root!=null )
[color=#800000]{
      [/color][color=#008080]postorder[/color](root->leftchild);
      [color=#008080]postorder[/color](root->rightchild);
      [color=#FF0000]std[/color]::[color=#FF0000]cout[/color]<<current->data<<[color=#FF8000]','
                  [/color]<<current->color<<[color=#FF00FF]" "[/color];
[color=#800000]}
}
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color][color=#800080]BBST[/color]<_Ty>::[color=#008080]postorder[/color]( node<_Ty>& root) [color=#0000FF]const
[/color][color=#800000]{
[/color][color=#0000FF]using [/color][color=#FF0000]std[/color]::[color=#FF0000]deque[/color];
[color=#FF0000]deque[/color]<node<_Ty>* > que;
[color=#0000FF]for[/color](node<_Ty>* current=&root,*visited=[color=#800080]0[/color];
      current!=null || !que.[color=#008080]empty[/color](); )
[color=#800000]{
      [/color][color=#0000FF]for[/color](; current!=null; )
      [color=#800000]{
         [/color]que.[color=#008080]push_front[/color](current);
         current = current->leftchild;
      [color=#800000]}
      [/color]current = que.[color=#008080]front[/color]();
      que.[color=#008080]pop_front[/color]();
      [color=#0000FF]if[/color](current->rightchild!=null&&visited!=current->rightchild)
      [color=#800000]{
         [/color]que.[color=#008080]push_front[/color](current);
         current = current->rightchild;
      [color=#800000]}
      [/color][color=#0000FF]else
      [/color][color=#800000]{
         [/color]visited = current;
         [color=#FF0000]std[/color]::[color=#FF0000]cout[/color]<<current->data<<[color=#FF8000]','
                     [/color]<<current->color<<[color=#FF00FF]" "[/color];
         current = null;
      [color=#800000]}
}
}
[/color][color=#008000]//    void PreOrder() const
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color][color=#800080]BBST[/color]<_Ty>::[color=#008080]PreOrder[/color]() [color=#0000FF]const
[/color][color=#800000]{
[/color][color=#008000]// srand((unsigned int) time(0));
[/color][color=#008080]preorder[/color](*root);
[color=#800000]}
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color][color=#800080]BBST[/color]<_Ty>::[color=#008080]preorder[/color]([color=#0000FF]const [/color]node<_Ty>* root) [color=#0000FF]const
[/color][color=#800000]{
[/color][color=#0000FF]if[/color]( root!=null )
[color=#800000]{
      [/color][color=#FF0000]std[/color]::[color=#FF0000]cout[/color]<<current->data<<[color=#FF8000]','
            [/color]<<current->color<<[color=#FF00FF]" "[/color];
      [color=#008080]preorder[/color](root->leftchild);
      [color=#008080]preorder[/color](root->rightchild);
[color=#800000]}
}
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color][color=#800080]BBST[/color]<_Ty>::[color=#008080]preorder[/color]( node<_Ty>& root) [color=#0000FF]const
[/color][color=#800000]{
[/color][color=#0000FF]using [/color][color=#FF0000]std[/color]::[color=#FF0000]deque[/color];
[color=#FF0000]deque[/color]<node<_Ty>*> que;
[color=#0000FF]for[/color](node<_Ty>* current=&root;current!=null || !que.[color=#008080]empty[/color]();)
[color=#800000]{
         [/color][color=#0000FF]for[/color]( ; current!=null; )
         [color=#800000]{
            [/color][color=#FF0000]std[/color]::[color=#FF0000]cout[/color]<<current->data<<[color=#FF8000]','
                     [/color]<<current->color<<[color=#FF00FF]" "[/color];
            que.[color=#008080]push_front[/color](current);
            current = current->leftchild;
         [color=#800000]}
         [/color]current = que.[color=#008080]front[/color]();
         que.[color=#008080]pop_front[/color]();
         current = current->rightchild;
[color=#800000]}
}
[/color][color=#008000]//    void LevelOrder() const
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color][color=#800080]BBST[/color]<_Ty>::[color=#008080]LevelOrder[/color]() [color=#0000FF]const
[/color][color=#800000]{
[/color][color=#0000FF]using [/color][color=#FF0000]std[/color]::[color=#FF0000]deque[/color];
[color=#FF0000]deque[/color]<node<_Ty>*> que;
[color=#0000FF]for[/color](node<_Ty>* current=root;current!=null||!que.[color=#008080]empty[/color]();)
[color=#800000]{
      [/color][color=#FF0000]std[/color]::[color=#FF0000]cout[/color]<<current->data<<[color=#FF8000]','
            [/color]<<current->color<<[color=#FF00FF]" "[/color];
      [color=#0000FF]if[/color](current->leftchild!=null) que.[color=#008080]push_front[/color](current->leftchild);
      [color=#0000FF]if[/color](current->rightchild!=null) que.[color=#008080]push_front[/color](current->rightchild);
      [color=#0000FF]if[/color](!que.[color=#008080]empty[/color]())
      [color=#800000]{
      [/color]current = que.[color=#008080]back[/color]();
      que.[color=#FF8000]pop_back[/color]();
      [color=#800000]}
      [/color][color=#0000FF]else [/color]current = null;
[color=#800000]}
}
[/color][color=#008000]//------------------  RBT class ------------------------------------
//------------------------------------------------------------------
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]class [/color][color=#800080]RBT[/color]: [color=#0000FF]public [/color][color=#800080]BBST[/color]<_Ty>
[color=#800000]{
[/color][color=#0000FF]public [/color]:
      [color=#800080]RBT[/color]();
      ~[color=#800080]RBT[/color]();
      [color=#0000FF]void [/color][color=#008080]Insert[/color]([color=#0000FF]const [/color]_Ty& value,[color=#0000FF]int [/color]skey);
      [color=#0000FF]const [/color]node<_Ty>* [color=#008080]Delete[/color]([color=#0000FF]int [/color]skey);
[color=#0000FF]protected [/color]:
      [color=#0000FF]void [/color][color=#008080]LeftRotate[/color](node<_Ty>* __parent,node<_Ty>* child);
      [color=#0000FF]void [/color][color=#008080]RightRotate[/color](node<_Ty>* __parent,node<_Ty>* child);
[color=#0000FF]private[/color]:
      [color=#0000FF]void [/color][color=#FF8000]free[/color](node<_Ty>* current);
      [color=#0000FF]void [/color][color=#008080]insert_balance[/color](node<_Ty>* current);
      [color=#0000FF]void [/color][color=#008080]delete_balance[/color](node<_Ty>* current);
[color=#800000]}[/color];
[color=#008000]// intilization and destroy
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]inline [/color][color=#800080]RBT[/color]<_Ty>::[color=#800080]RBT[/color]()
[color=#800000]{
[/color]null = [color=#0000FF]new [/color]node<_Ty>;
countNode = [color=#800080]0[/color];
root = null;
[color=#800000]}
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color][color=#800080]RBT[/color]<_Ty>::[color=#FF8000]free[/color](node<_Ty>* current)
[color=#800000]{
[/color][color=#0000FF]if[/color]( current!=null )
[color=#800000]{
      [/color][color=#FF8000]free[/color](current->leftchild);
      [color=#FF8000]free[/color](current->rightchild);
      [color=#0000FF]delete [/color]current;
[color=#800000]}
}
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#800080]RBT[/color]<_Ty>::~[color=#800080]RBT[/color]()
[color=#800000]{
[/color][color=#FF8000]free[/color](root);
[color=#0000FF]delete [/color]null;
[color=#800000]}
[/color][color=#008000]//    Insert  and  Delete
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color][color=#800080]RBT[/color]<_Ty>::[color=#008080]Insert[/color]([color=#0000FF]const [/color]_Ty& value,[color=#0000FF]int [/color]skey)
[color=#800000]{
[/color]node<_Ty>* current = root ;
[color=#0000FF]if[/color]( current!=null )
[color=#800000]{
      [/color][color=#0000FF]for[/color](node<_Ty>* [color=#FF8000]find[/color]=current; [color=#FF8000]find[/color]!=null;)
      [color=#800000]{
         [/color][color=#0000FF]if[/color]([color=#FF8000]find[/color]->key == skey) [color=#0000FF]return[/color];
         current = [color=#FF8000]find[/color];
         [color=#0000FF]if[/color]([color=#FF8000]find[/color]->key<skey)  [color=#FF8000]find [/color]= [color=#FF8000]find[/color]->rightchild;
         [color=#0000FF]else  [/color][color=#FF8000]find [/color]= [color=#FF8000]find[/color]->leftchild;
      [color=#800000]}
      [/color]node<_Ty>* __node = [color=#0000FF]new [/color]node<_Ty>(value,skey);
      __node->leftchild=__node->rightchild=__node->parent=null;
      __node->parent = current;
      [color=#0000FF]if[/color](current->key<__node->key) current->rightchild = __node;
      [color=#0000FF]else [/color]current->leftchild = __node;
      [color=#008080]insert_balance[/color](__node);
[color=#800000]}
[/color][color=#0000FF]else
[/color][color=#800000]{
      [/color]node<_Ty>* __node = [color=#0000FF]new [/color]node<_Ty>(value,skey);
      __node->leftchild=__node->rightchild=__node->parent=null;
      __node->parent = root;
      root  = __node;
      root->color = [color=#800080]BLACK[/color];
[color=#800000]}
[/color]++countNode;
[color=#800000]}
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]const [/color]node<_Ty>* [color=#800080]RBT[/color]<_Ty>::[color=#008080]Delete[/color]([color=#0000FF]int [/color]skey)
[color=#800000]{
[/color]node<_Ty>* [color=#FF8000]find [/color]= [color=#008080]search[/color](skey);
[color=#0000FF]if[/color]([color=#FF8000]find[/color]!=null )
[color=#800000]{
      [/color]node<_Ty>* _node,*_nodeParent;
      [color=#0000FF]if[/color]([color=#FF8000]find[/color]->leftchild!=null&&[color=#FF8000]find[/color]->rightchild!=null)
         _nodeParent = [color=#008080]successor[/color]([color=#FF8000]find[/color]);
      [color=#0000FF]else
         [/color]_nodeParent = [color=#FF8000]find[/color];
      [color=#0000FF]if[/color](_nodeParent->leftchild!=null)  _node=_nodeParent->leftchild ;
      [color=#0000FF]else [/color]_node=_nodeParent->rightchild;

      _node->parent = _nodeParent->parent;

      [color=#0000FF]if[/color](_nodeParent->parent==null) root = _node;
      [color=#0000FF]else if[/color](_nodeParent == (_nodeParent->parent)->leftchild)
         (_nodeParent->parent)->leftchild = _node;
      [color=#0000FF]else [/color](_nodeParent->parent)->rightchild = _node;

      [color=#0000FF]if[/color]([color=#FF8000]find[/color]!=_nodeParent)
      [color=#800000]{
         [/color][color=#FF8000]find[/color]->data = _nodeParent->data;
         [color=#FF8000]find[/color]->key = _nodeParent->key;
      [color=#800000]}
      [/color]--countNode;
      [color=#0000FF]if[/color](_node->color==[color=#800080]BLACK[/color])
      [color=#008080]delete_balance[/color](_node);
      [color=#0000FF]return [/color]_nodeParent;
[color=#800000]}
[/color][color=#0000FF]else return [/color][color=#800080]0[/color];
[color=#800000]}
[/color][color=#008000]//    LeftRotate  and  RightRotate
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color][color=#800080]RBT[/color]<_Ty>::[color=#008080]LeftRotate[/color](node<_Ty>* __parent,node<_Ty>* child)
[color=#800000]{
[/color]__parent->rightchild = child->leftchild;
(child->leftchild)->parent = __parent;
child->parent = __parent->parent;
[color=#0000FF]if[/color](__parent->parent==null)  root = child;
[color=#0000FF]else if[/color]((__parent->parent)->leftchild==__parent)
      (__parent->parent)->leftchild = child;
[color=#0000FF]else
      [/color](__parent->parent)->rightchild = child;
child->leftchild = __parent;
__parent->parent = child;
[color=#800000]}
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color][color=#800080]RBT[/color]<_Ty>::[color=#008080]RightRotate[/color](node<_Ty>* __parent,node<_Ty>* child)
[color=#800000]{
[/color]__parent->leftchild = child->rightchild;
(child->rightchild)->parent = __parent;
child->parent = __parent->parent;
[color=#0000FF]if[/color](__parent->parent==null) root = child;
[color=#0000FF]else if[/color]((__parent->parent)->leftchild==__parent)
      (__parent->parent)->leftchild = child;
[color=#0000FF]else
      [/color](__parent->parent)->rightchild = child;
child->rightchild = __parent;
__parent->parent = child;
[color=#800000]}
[/color][color=#008000]//    insert_balance  and  delete_balance
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color][color=#800080]RBT[/color]<_Ty>::[color=#008080]insert_balance[/color](node<_Ty>* current)
[color=#800000]{
[/color][color=#0000FF]for[/color](node<_Ty>* cParent=current->parent; cParent->color==[color=#800080]RED[/color]; )
[color=#800000]{
      [/color][color=#0000FF]if[/color](cParent==cParent->parent->leftchild)
      [color=#800000]{
      [/color][color=#008000]// case 1
         [/color][color=#0000FF]if[/color](cParent->parent->rightchild->color==[color=#800080]RED[/color])
         [color=#800000]{
         [/color]cParent->color = [color=#800080]BLACK[/color];
         cParent->parent->rightchild->color = [color=#800080]BLACK[/color];
         cParent->parent->color = [color=#800080]RED[/color];
         current = cParent->parent;
         [color=#800000]}
         [/color][color=#0000FF]else
         [/color][color=#800000]{
      [/color][color=#008000]// case 2
         [/color][color=#0000FF]if[/color](current== cParent->rightchild)
            [color=#008080]LeftRotate[/color](cParent,current);
      [color=#008000]// case 3
         [/color]cParent->color = [color=#800080]BLACK[/color];
         cParent->parent->color = [color=#800080]RED[/color];
         [color=#008080]RightRotate[/color](cParent->parent,cParent);
         [color=#800000]}
      }
      [/color][color=#0000FF]else
      [/color][color=#800000]{
         [/color][color=#0000FF]if[/color](cParent->parent->leftchild->color==[color=#800080]RED[/color])
         [color=#800000]{
            [/color]cParent->color = [color=#800080]BLACK[/color];
            cParent->parent->leftchild->color = [color=#800080]BLACK[/color];
            cParent->parent->color = [color=#800080]RED[/color];
            current = cParent->parent;
            [color=#800000]}
         [/color][color=#0000FF]else
         [/color][color=#800000]{
            [/color][color=#0000FF]if[/color](current==cParent->leftchild)
                  [color=#008080]RightRotate[/color](cParent,current);
            cParent->color =[color=#800080]BLACK[/color];
            cParent->parent->color = [color=#800080]RED[/color];
            [color=#008080]LeftRotate[/color](cParent->parent,cParent);
            [color=#800000]}
      }
}
[/color]root->color = [color=#800080]BLACK[/color];
[color=#800000]}
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color][color=#800080]RBT[/color]<_Ty>::[color=#008080]delete_balance[/color](node<_Ty>* current)
[color=#800000]{
[/color][color=#0000FF]for[/color](node<_Ty>* cParent=current->parent;
      current!=null&&current->color==[color=#800080]BLACK[/color];)
[color=#800000]{
      [/color][color=#0000FF]if[/color](current==cParent->leftchild)
      [color=#800000]{
         [/color][color=#0000FF]if[/color](cParent->rightchild->color==[color=#800080]RED[/color])
         [color=#800000]{
            [/color][color=#008080]LeftRotate[/color](cParent,cParent->rightchild);
            cParent->color = [color=#800080]RED[/color];
            cParent->rightchild->color = [color=#800080]BLACK[/color];
         [color=#800000]}
         [/color][color=#0000FF]else
         [/color][color=#800000]{
            [/color][color=#0000FF]if[/color](cParent->rightchild->leftchild->color==[color=#800080]BLACK[/color]&&
                  cParent->rightchild->rightchild->color==[color=#800080]BLACK[/color])
            [color=#800000]{
                  [/color]current = cParent;
                  cParent->rightchild->color = [color=#800080]RED[/color];
            [color=#800000]}
            [/color][color=#0000FF]else if[/color](cParent->rightchild->leftchild->color==[color=#800080]RED[/color])
            [color=#800000]{
                  [/color][color=#008080]RightRotate[/color](cParent->rightchild,cParent->rightchild->leftchild);
                  cParent->rightchild->color = [color=#800080]BLACK[/color];
                  cParent->rightchild->rightchild->color = [color=#800080]RED[/color];
            [color=#800000]}
            [/color][color=#008080]LeftRotate[/color](cParent,cParent->rightchild);
            current = root;
         [color=#800000]}
      }
      [/color][color=#0000FF]else
      [/color][color=#800000]{
         [/color][color=#0000FF]if[/color](cParent->leftchild->color==[color=#800080]RED[/color])
         [color=#800000]{
            [/color][color=#008080]RightRotate[/color](cParent,cParent->leftchild);
            cParent->color = [color=#800080]RED[/color];
            cParent->leftchild->color = [color=#800080]BLACK[/color];
         [color=#800000]}
         [/color][color=#0000FF]else
         [/color][color=#800000]{
            [/color][color=#0000FF]if[/color](cParent->leftchild->rightchild->color==[color=#800080]BLACK[/color]&&
                  cParent->leftchild->leftchild->color==[color=#800080]BLACK[/color])
            [color=#800000]{
                  [/color]current = cParent;
                  cParent->leftchild->color = [color=#800080]RED[/color];
            [color=#800000]}
            [/color][color=#0000FF]else if[/color](cParent->leftchild->rightchild->color==[color=#800080]RED[/color])
            [color=#800000]{
                  [/color][color=#008080]RightRotate[/color](cParent->leftchild,cParent->leftchild->rightchild);
                  cParent->leftchild->color = [color=#800080]BLACK[/color];
                  cParent->leftchild->leftchild->color = [color=#800080]RED[/color];
            [color=#800000]}
            [/color][color=#008080]LeftRotate[/color](cParent,cParent->leftchild);
            current = root;
            [color=#800000]}
         }
}
[/color]current->color = [color=#800080]BLACK[/color];
[color=#800000]}[/color][/size][/font][/quote]

aipb2007 发表于 2008-5-25 02:42

越来越厉害了，恭喜！

justtest 发表于 2008-7-27 10:41

红黑树实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

typedef struct node
{
int data;
int color;
struct node * parent;
struct node * left;
struct node * right;
}node_t, *node_tp;

static node_tp rb_tab_p = NULL;

void free_tab_s(node_tp node)
{
if(!node)
return;
free_tab_s(node->left);
free_tab_s(node->right);
printf("\nfree data=%d", node->data);
free(node);
}

void free_tab(void)
{
free_tab_s(rb_tab_p);
}

int node_depth(node_tp node, int * blance)
{
int l,r;
if(!node || !node->left || !node->right)
return 0;
l = node_depth(node->left, blance);
r = node_depth(node->right,blance);

if(l - r > 1 || l - r < -1)
{
printf("\n data=%d depth=%d", node->data, r - l);
if(blance && *blance*(*blance) < (r - l)*(r-l))
*blance = r - l;
}
return (l > r? l: r) + 1;
}

int travesal_mid_s(node_tp node)
{
int l,r,depth = node_depth(node,NULL);
if(!node || !node->left || !node->right)
return 0;
l = travesal_mid_s(node->left );
printf(" %d(%d, %d) ", node->data, node->color, depth);
r = travesal_mid_s(node->right);
return l + r + 1;
}

void travesal_mid(void)
{
int count, depth, blance = 0;
depth = node_depth(rb_tab_p, &blance);
printf("\n---------tree is-------------\n");
count = travesal_mid_s(rb_tab_p);
printf("\n-----count=%d--depth=%d--blance=%d----------", count, depth, blance);
}

node_tp find_node(node_tp node, int data)
{
if(!node || !node->left || !node->right)
return node;
else if(node->data > data)
return find_node(node->left, data);
else if(node->data < data)
return find_node(node->right, data);
else
return node;
}

node_tp max_node(node_tp node)
{
if(!node || !node->right || !node->right->right)
return node;
return max_node(node->right);
}

void init_node(node_tp node, int data, int color)
{
if(!node)
return;
node->data = data;
node->color = color;
node->parent = node->left = node->right = NULL;
}

void left_rotate(node_tp node)
{
node_tp p;
int itmp;
if(node && node->right)
{
if(node->right->color == -1 )
node->right->right->color = -1;
itmp = node->color;
node->color = node->right->color;
node->right->color = itmp;

p = node->right;
node->right = p->left;
p->left = node;

p->parent = node->parent;
if(!p->parent)
rb_tab_p = p;
else
{
if(p->parent->left == node)
p->parent->left = p;
else
p->parent->right = p;
}
node->parent = p;
if(node->right)
node->right->parent = node;
}
}

void right_rotate(node_tp node)
{
node_tp p;
int itmp;
if(node && node->left)
{
if(node->left->color == -1)
node->left->left->color = -1;
            itmp = node->color;
            node->color = node->left->color;
            node->left->color = itmp;

p = node->left;
node->left = p->right;
p->right = node;

p->parent = node->parent;
if(!p->parent)
rb_tab_p = p;
else
{
if(p->parent->left == node)
p->parent->left = p;
else
p->parent->right = p;
}
node->parent = p;
if(node->left)
node->left->parent = node;
}

}

void left_right_rotate(node_tp node)
{
node_tp p;
int itmp;
if(node && node->left && node->left->right)
{
            itmp = node->color;
            node->color = node->left->right->color;
            node->left->right->color = itmp;
node->color = node->left->color;

p = node->left->right;
node->left->right = p->left;
p->left = node->left;

node->left = p->right;
p->right = node;

p->parent = node->parent;
if(!p->parent)
rb_tab_p = p;
else
{
if(p->parent->left == node)
p->parent->left = p;
else
p->parent->right = p;
}
p->left->parent = p;
p->right->parent = p;
if(p->left->right)
p->left->right->parent = p->left;
if(p->right->left)
p->right->left->parent = p->right;

}
}

void right_left_rotate(node_tp node)
{
node_tp p;
int itmp;
if(node && node->right && node->right->left)
{
            itmp = node->color;
            node->color = node->right->left->color;
            node->right->left->color = itmp;
node->color = node->right->color;

p = node->right->left;
node->right->left = p->right;
p->right = node->right;

node->right = p->left;
p->left = node;

p->parent = node->parent;
if(!p->parent)
rb_tab_p = p;
else
{
if(p->parent->left == node)
p->parent->left = p;
else
p->parent->right = p;
}
p->left->parent = p;
p->right->parent = p;
if(p->left->right)
p->left->right->parent = p->left;
if(p->right->left)
p->right->left->parent = p->right;

}
}

int insert_rotate_type(node_tp node)
{
if(node && node->parent->right == node && node->parent->parent->right ==node->parent)
return -1;
else if(node && node->parent->left == node && node->parent->parent->left ==node->parent)
return 1;
else if(node && node->parent->right == node && node->parent->parent->left ==node->parent)
return -2;
else if(node && node->parent->left == node && node->parent->parent->right ==node->parent)
return 2;
else
return 0;

}

void rb_rotate(node_tp node, int type)
{
switch(type)
{
case -1:
left_rotate(node);
break;
case 1:
right_rotate(node);
break;
case -2:
left_right_rotate(node);
break;
case 2:
right_left_rotate(node);
break;
default:
break;
}
}

void insert_rb_rotate(node_tp node)
{
printf("\n11");
rb_rotate(node->parent->parent, insert_rotate_type(node));
}

void insert_color_adjust(node_tp node)
{
node_tp p;
if(!node)
return;
else if(!node->parent)
{
node->color = -1;
return;
}

if(node->color == 1 && node->parent->color == 1)
      {
            p = node->parent->parent;
            if(p->left->color == p->right->color)
            {
                     p->left->color = p->right->color = -1;
                     p->color = 1;
                     node = p;
insert_color_adjust(node);
            }
else
         insert_rb_rotate(node);

}
}

int insert_node_s(node_tp node, int data)
{
node_tp cur_p, p;
cur_p = find_node(node, data);
if(cur_p && cur_p->left && cur_p->right)
return -1;

if(!cur_p)
{
cur_p = (node_tp)malloc(sizeof(node_t));
assert(cur_p != NULL);
init_node(cur_p, data, -1);
rb_tab_p = cur_p;
}

p = (node_tp)malloc(sizeof(node_t));
assert(p != NULL);
init_node(p, 0,-1);
cur_p->left = p;
p->parent = cur_p;

p = (node_tp)malloc(sizeof(node_t));
assert(p != NULL);
init_node(p, 0,-1);
cur_p->right = p;
p->parent = cur_p;

cur_p->data = data;
cur_p->color = 1;

insert_color_adjust(cur_p);
return 0;
}

int insert_node(int data)
{
return insert_node_s(rb_tab_p, data);
}

int del_rotate_type(node_tp black_p)
{
node_tp parent_p, brother_p;
if(black_p && black_p->parent)
{
         parent_p = black_p->parent;
      if(parent_p->left == black_p)
            brother_p = parent_p->right;
         else
                 brother_p = parent_p->left;

if(brother_p->color == 1 && brother_p == parent_p->right)
               return -1;
      else if(brother_p->color == 1 && brother_p == parent_p->left)
            return 1;
      else if(brother_p->color == -1 && brother_p == parent_p->right &&  brother_p->right->color == 1)
            return -1;
      else if(brother_p->color == -1 && brother_p == parent_p->left &&  brother_p->left->color == 1)
            return 1;
      else if(brother_p->color == -1 && brother_p == parent_p->right && brother_p->left->color == 1 && brother_p->right->color == -1)
            return 2;
      else if(brother_p->color == -1 && brother_p == parent_p->left && brother_p->left->color == -1 && brother_p->right->color == 1)
            return -2;
}
return 0;
}

void del_rb_rotate(node_tp node)
{
   rb_rotate(node->parent, del_rotate_type(node));
}

void del_color_adjust(node_tp black_p)
{
node_tp parent_p, brother_p;
if(!black_p)
return;
else if(black_p == rb_tab_p || black_p->color == 1)
{
black_p->color = -1;
return;
}
parent_p = black_p->parent;
if(parent_p->left == black_p)
brother_p = parent_p->right;
else
brother_p = parent_p->left;

if(brother_p->color == -1 && brother_p->left->color == -1 && brother_p->right->color == -1)
{
brother_p->color = 1;
black_p = black_p->parent;
}
else if(brother_p->color == 1)
{
del_rb_rotate(black_p);
}
else
{
del_rb_rotate(black_p);
black_p = NULL;
}
del_color_adjust(black_p);

}

int del_node_s(node_tp node, int data)
{
node_tp pre_p, cur_p, black_p = NULL;
cur_p = find_node(node, data);
if(!cur_p || !cur_p->left || !cur_p->right)
return -1;

if(!cur_p->left->left)
{
if(cur_p->color == -1)
black_p = cur_p->right;

if(!cur_p->parent)
{
rb_tab_p = cur_p->right;
rb_tab_p->parent = NULL;
}
else
{
if(cur_p->parent->left == cur_p)
cur_p->parent->left = cur_p->right;
else
cur_p->parent->right = cur_p->right;
cur_p->right->parent = cur_p->parent;
}
printf("\nfree data=%d", cur_p->data);
free(cur_p->left);
free(cur_p);
if(!rb_tab_p->left || !rb_tab_p->right)
{
free(rb_tab_p);
rb_tab_p = NULL;
black_p = NULL;
}
}
else
{
pre_p = max_node(cur_p->left);
if(pre_p->color == -1)
black_p = pre_p->left;
cur_p->data = pre_p->data;

if(pre_p->parent->left == pre_p)
pre_p->parent->left = pre_p->left;
else
pre_p->parent->right = pre_p->left;
pre_p->left->parent = pre_p->parent;

printf("\nfree data=%d", pre_p->data);
free(pre_p->right);
free(pre_p);
}

del_color_adjust(black_p);
return 0;

}

int del_node(int data)
{
return del_node_s(rb_tab_p, data);
}

void input_data(void)
{

char str[20];
int data;
int ret;
int i;
for(i = 0; i < 255; i++)
insert_node(i);

while(1)
{

/* printf("\n\nenter data=");
scanf("%s", str);
if(strncmp(str, "ok", 2) == 0)
break;
ret = sscanf(str, "%d", &data);
if(ret == 1)
{
travesal_mid();
ret = insert_node(data);
if(ret == 0)
printf("\ninsert %d successful", data);
travesal_mid();
}

*/

            travesal_mid();
            printf("\n\ndel data=");
            scanf("%s", str);
            if(strncmp(str, "ok", 2) == 0)
                     break;
            ret = sscanf(str, "%d", &data);
            if(ret == 1)
            {
                     ret = del_node(data);
                     if(ret == 0)
                              printf("\ndel %d successful", data);
                     travesal_mid();
            }

}
free_tab();

}

int main(int argc, char **argv)
{

input_data();

return 0;
}

中学者 发表于 2008-7-28 00:16

这么老的贴都被翻出来了，佩服 - -

bianchengwa 发表于 2008-7-30 09:35

强好长的源代码不过那位能指教一下什么是红黑树啊

页: [1]