C++ 2杈树完整

淡淡的烟草味﹌ 2022-08-20 12:17 123阅读 0赞

#ifndef RB_H_
    #define RB_H_
    
    #include <cstdlib>
    #include <queue>
    template<class T> class RB;
    
    template<typename T>
    class Node
    {
    	friend RB<T>;
    private:
    	Node() :zuo(0), you(0),data(0){}
    	Node(T *&s):data(s),zuo(0),you(0){}
    	~Node(){ delete data; }
    	Node *zuo;
    	Node *you;
    	T *data;
    	
    };
    
    
    template<typename T>
    class RB
    {
    public:
    	RB() :m_root(0),count(0){}
    	~RB()
    	{
    		deleteAll();
    	}
    	void deleteAll()
    	{
    		queue<Node<T>*>s;
    		s.push(m_root);
    		while (m_root != NULL || !s.empty())
    		{
    			m_root = s.front();
    			if (m_root->zuo)
    				s.push(m_root->zuo);
    			if (m_root->you)
    				s.push(m_root->you);
    			m_root = s.front();
    			s.pop();
    			delete m_root;
    			m_root = NULL;
    			cout << "11" << endl;
    		}
    		m_root = NULL;
    	}
    	RB(T* data) :m_root(new Node<T>(data)){}
    	bool insert(T *data);
    	void Deleteone(T &data);
    	int GetConut(){ return count; }
    	
    	void print()
    	{
    		if (m_root)
    			devis(m_root,1);
    	}
    private:
    	int count;
    	Node<T> *finmax(Node<T> *t)
    	{
    		if (t == NULL)
    			return NULL;
    		while (t->you != NULL)
    			t = t->you;
    		return t;
    	}
    	void remove(Node<T> *t)
    	{
    		if (t == NULL)
    			return;
    		Node<T> * q = t;
    		while (t->you)
    		{
    			q = t;
    			t = t->you;
    		}
    		
    			if (t->zuo)
    			{
    				q->you = t->zuo;
    				delete t;
    			}
    			else
    			{
    				q->you = NULL;
    				delete t;
    			}
    			 
    		
    
    	}
    	void Dele(Node<T> *root, T &data)
    	{
    		Node<T> *q = root;
    		while (root)
    		{
    			if (data < *root->data)
    			{
    				q = root;
    				root = root->zuo;
    			}
    			else if (data>*root->data)
    			{
    				q = root;
    				root=root->you;
    			}
    			else
    			{
    				Node<T> *temp = 0;
    				int ii ;
    				if (root->zuo)
    				{
    					for (temp = root->zuo,q=root,ii=0; temp->you;q=temp, temp = temp->you,ii++){}
    					*root->data = *temp->data;
    					if (!ii)
    					{
    						root->zuo = temp->zuo;
    						delete temp;
    						count--;
    						return;
    					}
    						q->you = temp->zuo;
    						delete temp;
    						count--;
    						return;
    				
    				}
    				if (root->you)
    				{
    					for (temp = root->you, q = root,ii=0; temp->zuo; q = temp, temp = temp->zuo,ii++){}
    					*root->data = *temp->data;
    					if (!ii)
    					{
    						root->you = temp->you;
    						delete temp;
    						count--;
    						return;
    					}
    						q->zuo = temp->you;
    						delete temp;
    						count--;
    						return;
    				
    				}
    				else
    				{
    					if (q == root)
    					{
    						delete m_root;
    						m_root = NULL;
    						count--;
    						return;
    					}
    					else if (q->you == root)
    					{
    						q->you = NULL;
    						delete root;
    						count--;
    						return;
    					}
    					else
    					{
    						q->zuo = NULL;
    						delete root;
    						count--;
    						return;
    					}
    				}
    
    
    
    			}
    		}
    	}
    	//void Dele(Node<T> *root, T &data)
    	//{
    	//	
    	//	Node<T> *q = 0;
    	//	q = root;
    	//	while (root)
    	//	{
    
    	//		if (data < *root->data)
    	//		{
    	//			q = root;
    	//			root = root->zuo;
    	//		}
    	//		else if (data>*root->data)
    	//		{
    	//			q = root;
    	//			root = root->you;
    	//		}
    	//		else
    	//		{
    	//			int fal = 0;
    	//			Node<T>* qq = 0;
    	//			 if (q->you == root)
    	//			{
    	//				fal = 0;
    	//			}
    	//			else if (q->zuo == root)
    	//			{
    	//				fal = 1;
    	//			}
    	//			 if (q == root)
    	//			 {
    	//				 fal = 3;
    	//			 }
    	//			if (root->zuo&&root->you)
    	//			{
    	//				
    	//				
    	//				qq = root;
    	//				root=RiatMovezuo(qq);
    	//				if (qq->you)
    	//				{
    	//					*qq->data = *finmax(q->you)->data;
    	//					remove(qq);
    	//					count--;
    	//					
    	//				}
    	//				else
    	//				{
    	//					root->zuo = qq->zuo;
    	//					delete qq;
    	//					count--;
    	//					
    	//				}
    	//				if (fal == 1)
    	//				{
    	//					q->zuo = root;
    	//				}
    	//				else if (fal == 0)
    	//					q->you = root;
    	//				else
    	//					m_root = root;
    	//				return;
    	//			}
    	//		
    	//			else
    	//			{
    	//				if (!root->you&&root->zuo)
    	//				{
    	//					if (root->zuo->zuo)
    	//					{
    	//						qq = root;
    	//						root=RiatMoveyou(root);
    	//						if (qq->zuo)
    	//						{
    	//							root->you = qq->zuo;
    	//							delete qq;
    	//							count--;
    	//						}
    	//						else
    	//						{
    	//							root->you = qq->you;
    	//							delete qq;
    	//							count--;
    	//						}
    	//						if (fal == 1||fal==0)
    	//						{
    	//							if (fal)
    	//							{
    	//								q->zuo = root;
    	//							}
    	//							else
    	//								q->you = root;
    	//							return;
    	//						}
    	//						else
    	//						{
    	//							m_root = root;
    	//							return;
    	//						}
    	//					}
    	//					else
    	//					{
    	//						if (fal != 3)
    	//						{
    	//							if (q->you == root)
    	//							{
    	//								q->you = root->zuo;
    	//								delete root;
    	//								count--;
    	//								return;
    	//							}
    	//							else
    	//							{
    	//								q->zuo = root->zuo;
    	//								delete root;
    	//								count--;
    	//								return;
    	//							}
    
    	//						}
    	//						else
    	//						{
    	//							m_root = q->zuo;
    	//							delete root;
    	//							count--;
    	//							return;
    	//						}
    	//						
    	//					}
    	//				}
    	//				else if (!root->zuo&&root->you)
    	//				{
    	//					if (root->you->you)
    	//					{
    	//						qq = root;
    	//						root=RiatMovezuo(root);
    	//						if (root->you)
    	//						{
    	//							root->zuo = qq->you;
    	//							delete qq;
    	//							count--;
    	//						}
    	//						if (fal == 1 || !fal)
    	//						{
    	//							if (fal)
    	//							{
    	//								q->zuo = root;
    	//							}
    	//							else
    	//								q->you = root;
    	//						}
    	//						return;
    	//					}
    	//					else
    	//					{
    	//						if (fal!=3)
    	//						{
    	//							if (q->you == root)
    	//							{
    	//								q->you = root->you;
    	//								delete root;
    	//								count--;
    	//								return;
    	//							}
    	//							else
    	//							{
    	//								q->zuo = root->you;
    	//								delete root;
    	//								count--;
    	//								return;
    	//							}
    	//						}
    	//						else
    	//						{
    	//							m_root = root->you;
    	//							delete root;
    	//							count--;
    	//							return;
    	//						}
    	//					
    	//					}
    	//				}
    	//				else
    	//				{
    	//					if (q == root)
    	//					{
    	//						delete m_root;
    	//						m_root = NULL;
    	//						count--;
    	//						return;
    	//					}
    	//					else
    	//					{
    	//						if (q->you == root)
    	//						{
    	//							q->you = NULL;
    	//							delete root;
    	//							count--;
    	//							return;
    	//						}
    	//						else
    	//						{
    	//							q->zuo = root->you;
    	//							delete root;
    	//							count--;
    	//							return;
    	//						}
    	//					}
    	//				}
    	//			}
    	//		}
    	//			
    
    	//	}
    	//
    	//		
    	//		
    	//
    	//	}
    		
    
    	Node<T>* m_root;
    	Node<T>*  RiatMoveyou(Node<T>* q1)
    	{
    		 Node<T> * q2 = q1->zuo;
    		q1->zuo = q2->you;
    		q2->you = q1;
    		q1 = q2;
    	   return q1;
    	}
    	 Node<T>*  RiatMovezuo(Node<T>* p2)
    	{
    		 Node<T> * p1 = p2->you;
    		p2->you = p1->zuo;
    		p1->zuo = p2;
    		p2 = p1;
    		return p2;
    	}
    	void devis(Node<T>*root, int i)
    	{
    		if (root)
    		{
    			if (root->zuo)
    			{
    				devis(root->zuo,2* i);
    			}
    			cout << "i==" << i << "   data==" << *root->data << endl;
    			if (root->you)
    				devis(root->you, 2*i+1);
    		}
    	}
    };
    template<typename T>
    bool RB<T>::insert(T *data)
    {
    	if (!data)
    		return false;
    	if (!m_root)
    	{
    		m_root = new Node<T>(data);
    		count++;
    		return true;
    	}
    	Node<T> *p, *q, *q1, *q2;
    	p=q=q1=q2=m_root;
    	
    	while (p)
    	{
    		q1 = q2;
    		q2 = q;
    		q = p;
    		if (*data < *p->data)
    		{
    			p = p->zuo;
    		}
    		else if (*data> *p->data)
    		{
    			p = p->you;
    		}
    		else
    		{
    			delete data;
    			return false;
    		}
    	}
    	p = new Node<T>(data);
    	if (*data < *q->data)
    	{
    		q->zuo = p;
    		if (count >= 2)
    		{
    
    			if (count == 2)
    			{
    				if (!q2->you)
    					m_root=RiatMoveyou(m_root);
    			}
    			else
    			{
    
    				if (q1->zuo == q2&&q2->zuo==q)
    				{
    					q1->zuo = RiatMoveyou(q1->zuo);
    				}
    				else if (q1->zuo == q2&&q2->zuo != q)
    					q1->zuo = RiatMovezuo(q1->zuo);
    			}
    		}
    		
    		count++;
    	}
    	else
    	{
    		q->you = p;
    		if (count >= 2)
    		{
    			if (count == 2)
    			{
    				if (!q2->zuo)
    					m_root=RiatMovezuo(m_root);
    			}
    		
    			else
    			{
    
    				if (q1->you == q2&&q2->you==q)
    				{
    					q1->you = RiatMovezuo(q1->you);
    				}
    				else if (q1->you == q2&&q2->you!=q)
    					q1->you = RiatMoveyou(q1->you);
    			}
    		}
    		count++;
    	}
    		
    	return true;
    
    }
    
    template<typename T>
    void RB<T>::Deleteone(T &data)
    {
    	if (!m_root&&!count)
    	{
    		return ;
    	}
    	else
    	{
    		Dele(m_root, data);
    	}
    	
    
    }
    
    
    
    #endif