[原创]红黑树. - C++教室 - C++论坛

问题点数：0 回复次数：1

[原创]红黑树.

希望对大家有帮助,,,,,一起进步......
PS: 在C区发过的，但是还是应该发在这里...

/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) [url]http://[/url] **
*****************************************************************/
enum COLOR { RED,BLACK };
template<typename Ty>
struct node
{
    int key;
    Ty data;
    node<Ty>* leftchild;
    node<Ty>* rightchild;
    node<Ty>* parent;
    COLOR color;
    node(const Ty& v,int k):data(v)
    {
        key = k;
        color = RED;
        leftchild = rightchild = parent =0;
    }
    node(){ color = BLACK; }
} ;
template<typename _value>
class BBST
{
public:
    virtual ~BBST() = 0;
    virtual void Insert(const _value& value,int key)=0;
    virtual const node<_value>* Delete(int key) =0;
    virtual const node<_value>* Search(int key) const;

    bool empty() const ;
    int size() const ;
    int height() const ;

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

        for(node<_Ty>* __node=current->parent;__node!=null;)
        {
            if(__node->leftchild == current)
            {
                current = __node;
                __node = null;
            }
            else
            {
                current = __node;
                __node = __node->parent;
            }
        }
    return current;
}
template<typename _Ty>
node<_Ty>* BBST<_Ty>::predecessor(node<_Ty>* current) const
{
        if( current->leftchild!=null) return Maximum(current->leftchild);

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

        _node->parent = _nodeParent->parent;

        if(_nodeParent->parent==null) root = _node;
        else if(_nodeParent == (_nodeParent->parent)->leftchild)
            (_nodeParent->parent)->leftchild = _node;
        else (_nodeParent->parent)->rightchild = _node;

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

搜索更多相关主题的帖子: 飞燕　 software　yzfy　