红黑二叉查找树(RedBlackBST) -- C++实现


实现代码

// RedBlackBST.h
#ifndef RDRBLACKBST_H
#define RDRBLACKBST_H

#include<iostream>
using namespace std;

namespace jay{

	template<typename T>
	class RedBlackBST
	{
	private:
		// 内嵌的节点类
        class Node
		{
			public:
			T m_value;
			Node* m_pLeftChild;
			Node* m_pRightChild;
			bool m_isRed;

			//Node( T Value,bool isRed )
			Node( T Value)
			{
				m_value = Value;
				m_pLeftChild = NULL;
				m_pRightChild = NULL;
				m_isRed = true;
			}

		};
		Node *m_pRoot;

	public:
		void Insert( T Value );
		Node* Insert( Node* pNode, T Value );

		void Delete( T Value );
		Node* Delete( Node* pNode, T Value );

		void ClearMemory(Node *pNode);

		T Max();
		Node* GetMax(Node* pNode);
		T Min();
		Node* GetMin(Node* pNode);

		void DeleteMax();
		Node* DeleteMax(Node* pNode);
		void DeleteMin();
		Node* DeleteMin(Node* pNode);

		Node* RotateRight(Node* pNode);
		Node* RotateLeft(Node* pNode);

		void FlipColor(Node* pNode);

		bool isRed(Node* pNode);
		Node* MoveRedRight(Node* pNode);
		Node* MoveRedLeft(Node* pNode);
		bool isEmpty();

		Node* Balance(Node* pNode );
		bool isBalanced(Node* pNode,int iblack);
		bool isBalanced();

		// 前序后序中序遍历是针对根节点来说的
		void PreorderTraversal();  // 前序遍历 DLR 前序遍历首先访问根结点然后遍历左子树,最后遍历右子树
		void InorderTraversal();   // 中序遍历 LDR ,中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树
		void PostorderTraversal(); // 后序遍历 LRD 先左后右再根  即首先遍历左子树,然后遍历右子树,最后访问根结点

		void PreorderTraversal(Node *pNode);
		void InorderTraversal(Node *pNode);  
		void PostorderTraversal(Node *pNode);
		
		int Find(T value);
		Node* Get(Node* pNode,T value);
		RedBlackBST();
		~RedBlackBST();
		
	};

	template<typename T>
	RedBlackBST<T>::RedBlackBST()
	{
		m_pRoot = NULL;
	}

	template<typename T>
	RedBlackBST<T>::~RedBlackBST()
	{
		ClearMemory(m_pRoot);
	}

	template<typename T>
	void RedBlackBST<T>::PreorderTraversal()
	{
		cout << "前序遍历:";
		PreorderTraversal( m_pRoot );
		cout << endl;
	}

	template<typename T>
	void RedBlackBST<T>::PreorderTraversal(Node *pNode)
	{
		if (pNode == NULL)
			return;

		cout << " " << pNode->m_value << "(" << pNode->m_isRed << ") ";
		PreorderTraversal( pNode->m_pLeftChild);
		PreorderTraversal( pNode->m_pRightChild);
	}

	template<typename T>
	void RedBlackBST<T>::InorderTraversal()
	{
		cout << "中序遍历:";
		InorderTraversal( m_pRoot );
		cout << endl;
	}

	template<typename T>
	void RedBlackBST<T>::InorderTraversal(Node *pNode)
	{
		if (pNode == NULL)
			return;

		InorderTraversal( pNode->m_pLeftChild);
		cout << " " << pNode->m_value << " ";
		InorderTraversal( pNode->m_pRightChild);
	}

	template<typename T>
	void RedBlackBST<T>::PostorderTraversal()
	{
		cout << "后序遍历:";
		PostorderTraversal( m_pRoot );
		cout << endl;
	}

	template<typename T>
	void RedBlackBST<T>::PostorderTraversal(Node *pNode)
	{
		if (pNode == NULL)
			return;

		PostorderTraversal( pNode->m_pLeftChild);
		PostorderTraversal( pNode->m_pRightChild);
		cout << " " << pNode->m_value << " ";
	}

	template<typename T>
	void RedBlackBST<T>::ClearMemory(Node *pNode)
	{
		if ( pNode == NULL )
			return;

		// 遍历删除左子树
		if ( pNode->m_pLeftChild != NULL )
			ClearMemory( pNode->m_pLeftChild );

		// 遍历删除右子树
		if ( pNode->m_pRightChild != NULL )
			ClearMemory( pNode->m_pRightChild );

		delete pNode;
		pNode = NULL;
	}

	template<typename T>
	void RedBlackBST<T>::DeleteMax()
	{
		m_pRoot = DeleteMax(m_pRoot);
	}

	// 删除操作存疑问 实现过程参考 算法第四版java语言实现
	template<typename T>
	typename RedBlackBST<T>::Node* RedBlackBST<T>::DeleteMax(Node* pNode)
	{
		// 如果当前节点的左子结点是红链接,则右旋
		// 考虑只有2个元素的树,比如 8和9,右旋后,8成为根节点,9是右子节点,可以直接删除9结点
		if (isRed(pNode->m_pLeftChild))
			pNode = RotateRight(pNode);

		// 找到最大值,删除,结束递归
		if (pNode->m_pRightChild == NULL)
		{
			delete pNode;
			pNode = NULL;
			return NULL;
		}
			
		// 如果当前节点的右子节点不是红,且当前节点的右子节点的左子结点也不是红
		if (!isRed(pNode->m_pRightChild) && !isRed(pNode->m_pRightChild->m_pLeftChild))
			pNode = MoveRedRight(pNode);

		// 递归删除
		pNode->m_pRightChild = DeleteMax(pNode->m_pRightChild);
 
 		return Balance(pNode);

	}

	template<typename T>
	typename RedBlackBST<T>::Node* RedBlackBST<T>::MoveRedRight(Node* pNode)
	{
		// 当前节点和子节点的颜色进行反转
		FlipColor(pNode);
		// 如果当前节点的左子结点的左子结点为红链接
		if (isRed(pNode->m_pLeftChild->m_pLeftChild)) 
		{ 
			// 当前节点右旋
			pNode = RotateRight(pNode);
			// 反转颜色
			FlipColor(pNode);
		}
		return pNode;
	}

	template<typename T>
	typename RedBlackBST<T>::Node* RedBlackBST<T>::MoveRedLeft(Node* pNode)
	{

		FlipColor(pNode);

		if (isRed(pNode->m_pRightChild->m_pLeftChild)) 
		{ 
			pNode->m_pRightChild = RotateRight(pNode->m_pRightChild);
			pNode = RotateLeft(pNode);

			FlipColor(pNode);
		}
		return pNode;
	}

	template<typename T>
	void RedBlackBST<T>::DeleteMin()
	{
		m_pRoot = DeleteMin(m_pRoot);
	}

	// 删除操作存疑问
	template<typename T>
	typename RedBlackBST<T>::Node* RedBlackBST<T>::DeleteMin(Node* pNode)
	{
		// 找到最小值,删除,结束递归
		if (pNode->m_pLeftChild == NULL)
		{
			delete pNode;
			pNode = NULL;
			return NULL;
		}

		if (!isRed(pNode->m_pLeftChild) && !isRed(pNode->m_pLeftChild->m_pLeftChild))
			pNode = MoveRedRight(pNode);

		// 递归删除
		pNode->m_pLeftChild = DeleteMin(pNode->m_pLeftChild);

		return Balance(pNode);
	}

	template<typename T>
	T RedBlackBST<T>::Max()
	{
		return GetMax(m_pRoot)->m_value;
	}

	template<typename T>
	typename RedBlackBST<T>::Node* RedBlackBST<T>::GetMax(Node* pNode)
	{
		if (pNode->m_pRightChild == NULL) 
			return pNode; 
		else                 
			return GetMax(pNode->m_pRightChild); 
	}

	template<typename T>
	T RedBlackBST<T>::Min()
	{
		return GetMin(m_pRoot)->m_value;
	}

	template<typename T>
	typename RedBlackBST<T>::Node* RedBlackBST<T>::GetMin(Node* pNode)
	{
		if (pNode->m_pLeftChild == NULL) 
			return pNode; 
		else                 
			return GetMin(pNode->m_pLeftChild); 
	}

	template<typename T>
	void RedBlackBST<T>::Delete(T Value)
	{
		m_pRoot = Delete(m_pRoot, Value);
	}

	// 删除操作存疑问
	template<typename T>
	typename RedBlackBST<T>::Node* RedBlackBST<T>::Delete(Node* pNode,T Value)
	{
		if (Value < pNode->m_value)  
		{
			if (!isRed(pNode->m_pLeftChild) && !isRed(pNode->m_pLeftChild->m_pLeftChild))
				pNode = MoveRedLeft(pNode);
			pNode->m_pLeftChild = Delete(pNode->m_pLeftChild, Value);
		}
		else 
		{
			if (isRed(pNode->m_pLeftChild))
				pNode = RotateRight(pNode);

			if (pNode->m_value == Value && (pNode->m_pRightChild == NULL))
				return NULL;

			if (!isRed(pNode->m_pRightChild) && !isRed(pNode->m_pRightChild->m_pLeftChild))
				pNode = MoveRedRight(pNode);

			if (pNode->m_value == Value) 
			{
				Node *tmp = GetMin(pNode->m_pRightChild);
				pNode->m_value = tmp->m_value;
				// h.val = get(pNode->m_pRightChild, min(pNode->m_pRightChild).key);
				// pNode->m_value = min(pNode->m_pRightChild).key;
				pNode->m_pRightChild = DeleteMin(pNode->m_pRightChild);
			}
			else 
				pNode->m_pRightChild = Delete(pNode->m_pRightChild, Value);
		}
		return Balance(pNode);
		
	}

	template<typename T>
	int RedBlackBST<T>::Find(T value)
	{
		if (Get(m_pRoot,value) == NULL)
		{
			return 0;
		}

		return 1;
	}

	template<typename T>
	typename RedBlackBST<T>::Node* RedBlackBST<T>::Get(Node* pNode,T Value)
	{
		if ( pNode == NULL )
			return NULL;

		// 查找的值小于当前节点值,则查找左子树
		if ( Value < pNode->m_value )
		{
			return Get( pNode->m_pLeftChild, Value );
		}
		// 查找的值大于当前节点值,则查找右子树
		else if(Value > pNode->m_value )
		{
			return Get( pNode->m_pRightChild, Value );
		}
		//
		else
		{
			return pNode;
		}
	}

	template<typename T>
	void RedBlackBST<T>::Insert(T Value )
	{
		m_pRoot = Insert(m_pRoot, Value);
		// 根结点一定是black结点
		m_pRoot->m_isRed = false;
	}

	template<typename T>
	typename RedBlackBST<T>::Node* RedBlackBST<T>::Insert(Node* pNode, T Value )
	{
		// 当前结点用于保存新值,新增加的结点都设置为RED
		if (pNode == NULL) 
			return new Node(Value);

		// 新值较小,递归h的左子树寻找空间安置新值
		if (Value < pNode->m_value ) 
			pNode->m_pLeftChild  = Insert(pNode->m_pLeftChild ,Value); 
		// 新值较大,递归h的右子树寻找空间安置新值
		else if (Value > pNode->m_value ) 
			pNode->m_pRightChild = Insert(pNode->m_pRightChild ,Value); 
		// else
		// 新值已存在,不处理


		// 调整局部
		// fix-up any right-leaning links
		// 如果h的右子结点为RED,而左子结点为BLACK,则左旋
		if (isRed(pNode->m_pRightChild) && !isRed(pNode->m_pLeftChild))      
			pNode = RotateLeft(pNode);
		// 如果h的左子结点为RED,且h的左子结点的左子结点也为RED,则右旋
		if (isRed(pNode->m_pLeftChild)  &&  isRed(pNode->m_pLeftChild->m_pLeftChild))
			pNode = RotateRight(pNode);
		// 如果h的左右子结点均为为RED,则反转颜色(h置为RED h的左右结点置为BLACK)
		if (isRed(pNode->m_pLeftChild)  &&  isRed(pNode->m_pRightChild))     
			FlipColor(pNode);

		return pNode;
	}

	template<typename T>
	typename RedBlackBST<T>::Node* RedBlackBST<T>::Balance(Node* pNode )
	{
		// 调整局部
		// fix-up any right-leaning links
		// 如果h的右子结点为RED,而左子结点为BLACK,则左旋
		if (isRed(pNode->m_pRightChild) && !isRed(pNode->m_pLeftChild))      
			pNode = RotateLeft(pNode);
		// 如果h的左子结点为RED,且h的左子结点的左子结点也为RED,则右旋
		if (isRed(pNode->m_pLeftChild)  &&  isRed(pNode->m_pLeftChild->m_pLeftChild))
			pNode = RotateRight(pNode);
		// 如果h的左右子结点均为为RED,则反转颜色(h置为RED h的左右结点置为BLACK)
		if (isRed(pNode->m_pLeftChild)  &&  isRed(pNode->m_pRightChild))     
			FlipColor(pNode);

		return pNode;
	}

	template<typename T>
	typename RedBlackBST<T>::Node* RedBlackBST<T>::RotateRight(Node* pNode)
	{
		Node *tmp = pNode->m_pLeftChild;
		pNode->m_pLeftChild = tmp->m_pRightChild;
		tmp->m_pRightChild = pNode;
		tmp->m_isRed = tmp->m_pRightChild->m_isRed;
		tmp->m_pRightChild->m_isRed = true;
		return tmp;
	}

	template<typename T>
	typename RedBlackBST<T>::Node* RedBlackBST<T>::RotateLeft(Node* pNode)
	{
		// 1.x保存左旋后的新局部根节[原根节点是h] 
		Node *tmp = pNode->m_pRightChild;
		// 2.原局部根节点右子树指向 原局部根结点右子树的左子树
		pNode->m_pRightChild = tmp->m_pLeftChild;
		// 3.新局部根结点的左子树指定为原根结点
		tmp->m_pLeftChild = pNode;
		// 经过以上三步已经完成了左旋,下面处理一下color标识
		// 原根结点的color赋给新根结点
		tmp->m_isRed = tmp->m_pLeftChild->m_isRed;
		// 原根结点设置为RED
		tmp->m_pLeftChild->m_isRed = true;

		return tmp;
	}

	template<typename T>
	void RedBlackBST<T>::FlipColor(Node* pNode)
	{
		pNode->m_isRed = !pNode->m_isRed;
		pNode->m_pLeftChild->m_isRed = !pNode->m_pLeftChild->m_isRed;
		pNode->m_pRightChild->m_isRed = !pNode->m_pRightChild->m_isRed;
	}

	template<typename T>
	bool RedBlackBST<T>::isRed(Node* pNode)
	{
		if (pNode == NULL)
		{
			return false;
		}

		return pNode->m_isRed;
	}

	template<typename T>
	bool RedBlackBST<T>::isEmpty()
	{
		if (m_pRoot == NULL)
		{
			return true;
		}

		return false;
	}

	template<typename T>
	bool RedBlackBST<T>::isBalanced()
	{
		int iBlack = 0;     // number of black links on path from root to min
		Node *tmp = m_pRoot;
		while (tmp != NULL) 
		{
			if (!isRed(tmp)) 
				iBlack++;
			tmp = tmp->m_pLeftChild;
		}

		return isBalanced(m_pRoot, iBlack);
	}

	template<typename T>
	bool RedBlackBST<T>::isBalanced(Node* pNode,int iblack)
	{
		if (pNode == NULL) 
			return iblack == 0;

		if (!isRed(pNode)) 
			iblack--;

		return isBalanced(pNode->m_pLeftChild, iblack) && isBalanced(pNode->m_pRightChild, iblack);
	}

};

#endif

测试代码

//main.cpp

#include <time.h>
#include<windows.h>

#include <iostream>
#include <vector>
using namespace std;

#include "Component.h"
#include "RedBlackBST.h"

using namespace jay;

int main(int argc, char* argv[])
{
	RedBlackBST<int> myBst;
	myBst.Insert(10);
	myBst.Insert(5);
	myBst.Insert(4);
	myBst.Insert(9);
	myBst.Insert(8);
	myBst.Insert(7);
	myBst.Insert(6);
	myBst.Insert(116);
	myBst.Insert(3);
	myBst.Insert(2);
	myBst.Insert(0);
	myBst.Insert(15);
	myBst.Insert(16);
	myBst.Insert(17);
	myBst.Insert(18);
	myBst.Insert(19);
	myBst.Insert(20);

	cout << "is balanced? " << myBst.isBalanced() << endl;
 
 	myBst.PreorderTraversal();


 	cout << "当前最大值: "<< myBst.Max()<<endl;
 	myBst.DeleteMax();
 	cout << "当前最大值: "<< myBst.Max()<<endl;
 	myBst.DeleteMax();
 	cout << "当前最大值: "<< myBst.Max()<<endl;
	cout << "is balanced? " << myBst.isBalanced() << endl;
 
 	cout << "当前最小值: "<< myBst.Min()<<endl;
	myBst.DeleteMin();
	cout << "当前最小值: "<< myBst.Min()<<endl;
	myBst.DeleteMin();
	cout << "当前最小值: "<< myBst.Min()<<endl;
	cout << "is balanced? " << myBst.isBalanced() << endl;
 
	cout << myBst.Find(4)<<endl;
	cout << myBst.Find(5)<<endl;
	cout << myBst.Find(6)<<endl;
	cout << myBst.Find(7)<<endl;
	cout << myBst.Find(181)<<endl;
// 
	myBst.Delete(4);
	myBst.Delete(5);
	myBst.Delete(6);
// 
	cout <<"after delete..."<<endl;
	cout << myBst.Find(4)<<endl;
	cout << myBst.Find(5)<<endl;
	cout << myBst.Find(6)<<endl;
	cout << myBst.Find(7)<<endl;
	cout << myBst.Find(8)<<endl;
	
}

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。