C++ 红黑树

淩亂°似流年 2022-08-20 12:16 176阅读 0赞

#ifndef WRAPPER_H
    #define WRAPPER_H
    #include "Except.h"
    template<class Objct>
    class Cref
    {
    public:
    	Cref() :obj(NULL){}
    	explicit Cref(const Objct &x) :obj(&x){}
    
    	const Objct &get()const
    	{
    		if (usNull())throw NullPointerException();
    		else
    			return *obj;
    	}
    	bool usNull()const
    	{
    		return obj == NULL;
    	}
    private:
    	const Objct *obj;
    };
    
    
    
    #endif

#ifndef EXCEPT_H
    #define EXCEPT_H
    
    #include <string>
    class DSException
    {
    public:
    	DSException(const std::string &msg = "") :message(msg){}
    	virtual ~DSException(){}
    	virtual std::string toString()const
    	{
    		return "Exception" + std::string(":") + what();
    	}
    	virtual std::string what()const
    	{
    		return message;
    	}
    private:
    	std::string message;
    };
    
    
    class DuplicateItemException :public DSException
    {
    public:
    	DuplicateItemException(const std::string &mag = "") :DSException(mag){}
    };
    
    class NullPointerException:public DSException
    {
    public:
    	NullPointerException(const std::string &mag = "") :DSException(mag){}
    };
    #endif

#ifndef RETREE_H
    #define RETREE_H
    #include "Except.h"
    #include "Wrapper.h"
    template <class T>
    class ReBlackTree;//红黑树
    
    template<class T>
    class ReBlackNode;//节点
    
    template <class T>
    class ReBlackTree/红黑树
    {
    public:
    	ReBlackTree(const T&neginf);
    	~ReBlackTree();
    	enum {hong,hei};
    	Cref<T> findMin()const;
    	Cref<T> findMax()const;
    	Cref<T> find(const  T &x)const;
    	void insert(const T &x);
    	bool isEmpty()const;
    	void makeEmpty();
    	typedef ReBlackNode<T> Node;
    //private:  //为了测试零时编程public
    public:
    	Node *headder;//头
    	Node *nullNode;///空节点
    
    	Node *curret;//指向当前的节点
    	Node *parent;//父节点
    	Node *grand;//祖父节点
    	Node *great;//曾祖父节点
    
    
    	void rotateWithZuo(Node *&k2)const;//带走左孩子先右转 
    	void rotateWithyou(Node *&k1)const;//带走右孩子先左转 
    
    	void doubleRotateWithzuo(Node *&k3)const;//双带旋转走左孩子先右转 
    	void doubleRotateWithyou(Node *&k4)const;//双旋转带走右孩子先左转 
    
    	void reclaimMemory(Node *t)const;
    	void handleReorient(const T &item);
    
    	ReBlackNode<T>*roate(const T &item,Node *parent)const;
    };
    
    
    //
    template<class T>
    class ReBlackNode/节点
    {
    //private://为了测试零时编程public
    public:
    	T  element;
    	ReBlackNode *zuo;
    	ReBlackNode *you;
    	int color;
    	ReBlackNode(const T&theElement = T(), ReBlackNode *m_zuo = NULL, ReBlackNode*m_you = NULL, int c = ReBlackTree<T>::hei) :element(theElement), zuo(m_zuo), you(m_you), color(c){}
    	friend class ReBlackTree<T>;
    };
    
    ///
    
    template<class T>
    ReBlackTree<T>::ReBlackTree(const T&negInf )//红黑树构造
    {
    	nullNode = new Node();
    	nullNode->zuo = nullNode->you = nullNode;
    	headder = new Node(negInf);
    	headder->zuo = headder->you = nullNode;
    }
    
    
    template<class T>
    ReBlackTree<T>::~ReBlackTree()//析构
    {
    	makeEmpty();
    	delete nullNode;
    	delete headder;
    }
    
    template<class T >
    void ReBlackTree<T>::insert(const T & x)
    {
    	curret = parent = grand = headder;//当前节点 父节点 祖父节点
    	nullNode->element = x;//零时保存插入的数据
    
    	while (curret->element != x)
    	{
    		great = grand;//曾祖父节点保存祖父点
    		grand = parent;//祖父点保存父节点
    		parent = curret;//父节点保存当前节点
    		curret = x < curret->element ? curret->zuo : curret->you;
    		if (curret->zuo->color == hong&&curret->you->color == hong)
    			handleReorient(x);
    	}
    	if (curret != nullNode)
    		throw DuplicateItemException();
    
    	curret = new Node(x, nullNode, nullNode);
    	if (x < parent->element) 
    		parent->zuo = curret;
    	else
    		parent->you = curret;
    
    	handleReorient(x);
    }
    
    template<class T>
    void ReBlackTree<T>::rotateWithZuo(Node * &k2)const//带走左孩子先右转   k2=树根
    {
    	Node *k1 = k2->zuo;
    	k2->zuo = k1->you;
    	k1->you = k2;
    	k2 = k1;
    
    }
    
    template<class T>
    void ReBlackTree<T>::rotateWithyou(Node *&k1)const//带走右孩子向左转
    {
    	Node *k2 = k1->you;
    	k1->you = k2->zuo;
    	k2->zuo = k1;
    	k1 = k2;
    }
    
    
    template < class T>
    void ReBlackTree<T>::doubleRotateWithzuo(Node *&k3)const//带走左孩子先右转 
    {
    	rotateWithyou(k3->zuo);//左转
    	rotateWithZuo(k3);//右转
    }
    template < class T>
    void ReBlackTree<T>::doubleRotateWithyou(Node *&k1)const//带走左孩子先右转 
    {
    	rotateWithZuo(k1->left);//右转
    	rotateWithyou(k1);//右转
    }
    
    template<class  T>
    void ReBlackTree<T>::handleReorient(const T &item)
    {//变色
    	curret->color = hong;
    	curret->zuo->color = hei;
    	curret->you->color = hei;
    
    	if (parent->color == hong)
    	{//单选转
    		//双旋转
    		grand->color = hong;//爷爷的颜色
    		if (item < grand->element != item < parent->element)
    			parent = roate(item, grand);
    		curret = roate(item, great);
    		curret->color = hei;
    	}
    	headder->you->color = hei;
    
    }
    template<class T>
    ReBlackNode<T>*ReBlackTree<T>::roate(const T &item, Node *theparent)const
    {
    	if (item < theparent->element)
    	{
    		item > theparent->zuo->element ?
    			rotateWithyou(theparent->zuo) ://右转
    			rotateWithZuo(theparent->zuo);//左转
    		return theparent->zuo;
    	}
    	else
    	{
    		item < theparent->you->element ?
    			rotateWithZuo(theparent->you) ://右转
    			rotateWithyou(theparent->you);//左转
    		return theparent->you;
    	}
    
    }
    
    template<typename T>
    bool ReBlackTree<T>::isEmpty()const
    {
    	return headder->you == nullNode;
    }
    template<class T>
    void ReBlackTree<T>::makeEmpty()
    {
    	reclaimMemory(headder->you);//清除数据全部
    	headder->you = nullNode;
    }
    
    template<typename T>
    void ReBlackTree<T>::reclaimMemory(Node *t)const//递归清除
    {
    	if ( t->zuo||t->you)
    	{
    		reclaimMemory(t->zuo);
    		reclaimMemory(t->you);
    		delete t;
    	}
    	
    }
    
    template<typename T>
    Cref<T> ReBlackTree<T>::findMin()const
    {
    	if (isEmpty())
    		return Cref<T>();
    	else
    	{
    		Node *itr = headder->you;
    		while (itr->zuo != headder->zuo)
    			itr = itr->zuo;
    		return Cref<T>(itr->element);
    	}
    	
    }
    
    template<class T>
    Cref<T> ReBlackTree<T>::findMax()const
    {
    	if (isEmpty())
    		return Cref<T>();
    	else
    	{
    		Node *itr = headder->you;
    		while (itr->you != headder->zuo)
    			itr = itr->you;
    		return Cref<T>(itr->element);
    	}
    	
    }
    
    template<class T>
    Cref<T> ReBlackTree<T>::find(const T &x)const
    {
    	nullNode->element = x;
    	Node *curr = headder->you;
    	for (;;)
    	{
    		if (x < curr->element)
    			curr = curr->zuo;
    		else if (x>curr->element)
    			curr = curr->you;
    		else if (curr != nullNode)
    		{
    			return Cref<T>(curr->element);
    		}
    		else
    			return Cref<T>();
    	}
    }
    
    #endif