C++红黑树收关 红黑树其他方法补全

1、本篇补全红黑树的其他方法

   find();

   findMin();

   findMax();

   isEmpty();

  makeEmpty();

2、上代码

#include <iostream>

using namespace std;

template < class T>
class RedBlackTree;  //红黑树

template <class T>
class RedBlackTreeNode; //红黑树节点


template <class T>
class RedBlackTree
{
	typedef RedBlackTreeNode<T> Node;

public:
	enum { BLACK, RED };

	RedBlackTree(const T &negInfo);  //构造函数主要初始化私有成员 header 和 nullNode
	~RedBlackTree();

	void insert(const T & x); //红黑树插入元素

	void rotateWithLeftChild(Node * & k2) const; //带着左孩子旋转即向右转 k2是旋转前的根节点

	void rotateWithRightChild(Node * &k1) const; //带着右孩子旋转即向左转 k1是旋转前的根节点

	void doubleRotateWithLeftChild(Node * &k3) const;//带着左孩子向右双旋转

	void doubleRotateWithRightChild(Node * &k1) const;//带着右孩子向左双旋转

	RedBlackTreeNode<T> * rotate(const T & item, Node * theParent) const; //根据当前元素和父节点的关系进行旋转

	void handleReorient(const T &item); //这个函数里面处理有两个红色孩子的节点;插入节点后处理红色的父节点

	bool isEmpty() const;

	void makeEmpty();

	void reclaimMemory(Node * t) const;

	T * findMin()const; //找最左边的node

	T* findMax()const; //找最右边的node

	T* find(const T & t) const;

//private:
	Node *header; //header 的左子节点和右子节点初始化指向nullNode,将来右子节点会指向根节点，
				  //header节点的元素是个无效值
	Node *nullNode; //空节点

	Node *current; //当前节点
	Node *parent; //当前节点的父节点
	Node *grand; //当前节点的祖父节点
	Node *great; //当前节点的曾祖父节点

};


template <class T>
RedBlackTree<T>::RedBlackTree(const T &negInfo)
{
	nullNode = new Node();
	nullNode->left = nullNode->right = NULL;

	header = new Node(negInfo);
	header->left = header->right = nullNode; //header的左右节点初始化为nullNode
}

template <class T >
RedBlackTree<T>::~RedBlackTree()
{
	delete header;
	delete nullNode;
}

template <class T>
void RedBlackTree<T>::insert(const T &x)
{
	current = parent = grand = great = header; // 刚开始都指向头结点
	nullNode->element = x;  //空节点的元素等于新元素

	while (current->element != x)  //红黑树不允许有重复的节点
	{
		great = grand;        //一辈一辈往下循环
		grand = parent;
		parent = current;

		current = x > current->element ? current->right : current->left; //左小、右大

		if (current != nullNode)
		{
			if ((current->left->color == RED) && (current->right->color == RED))//处理有两个红色孩子的节点
			{
				handleReorient(x);
			}
		}

	}

	if (current != nullNode)
	{
		cout << "有重复元素了" << endl;

		return;
	}

	current = new Node(x, nullNode, nullNode);

	if (x < parent->element)
		parent->left = current;
	else
		parent->right = current;

	handleReorient(x);
	return;
}

template <class T>
void RedBlackTree<T>::rotateWithLeftChild(Node * & k2) const  //k2是旋转前的根节点
{
	Node * k1 = k2->left;

	k2->left = k1->right;
	k1->right = k2;

	k2 = k1;

}

template <class T>
void RedBlackTree<T>::rotateWithRightChild(Node * &k1) const //k1是旋转前的根节点
{
	Node *k2 = k1->right;

	k1->right = k2->left;
	k2->left = k1;
	k1 = k2;

}

template <class T>
void RedBlackTree<T>::doubleRotateWithLeftChild(Node * &k3) const
{
	rotateWithRightChild(k3->left);  //先把k3的左子节点向左旋转
	rotateWithLeftChild(k3);  //再把整个k3向右旋转
}

template <class T>
void RedBlackTree<T>::doubleRotateWithRightChild(Node * &k1)const
{
	rotateWithLeftChild(k1->right); //先把k1的右子节点向右旋转
	rotateWithRightChild(k1); //再把k1整体向左旋转
}

template <class T>
RedBlackTreeNode<T> * RedBlackTree<T>::rotate(const T & item, Node * theParent) const
{
	if (item < theParent->element)
	{
		item < theParent->left->element ?					//判断是否小于左子节点的元素,来决定向左转还是向右转
			rotateWithLeftChild(theParent->left) :
			rotateWithRightChild(theParent->left);

		return theParent->left;
	}
	else
	{
		item < theParent->right->element ?
			rotateWithLeftChild(theParent->right) :
			rotateWithRightChild(theParent->left);

		return theParent->right;

	}
}

template <class T>
void RedBlackTree<T>::handleReorient(const T & item)
{
	//变色
	current->color = RED;
	current->left->color = BLACK;
	current->right->color = BLACK;

	if (parent->color == RED)  //如果父节点是红色的
	{
		grand->color = RED; //爷爷节点变成红色的
		if ((item < grand->element) != (item < parent->element))  //注意:这里是两个逻辑表达式不相等，即item < grand->element
		{														  // 和 item < parent->element 不同时成立,是内部孙子
			parent = rotate(item, grand);
		}
		current = rotate(item, great);
		current->color = BLACK;
	}
	header->right->color = BLACK;
}

template <class T>
bool RedBlackTree<T>::isEmpty() const
{
	return header->right == nullNode;
}

template <class T>
void RedBlackTree<T>::reclaimMemory(Node *t) const
{
	if (t && (t->left || t->right))
	{
		//cout << header << endl;
		if (t != t->left)  //递归终止的条件是 t == t->left 或者 t == t->right
		{
			reclaimMemory(t->left);
			reclaimMemory(t->right);
			delete t;
		}
	}

}

template <class T>
void RedBlackTree<T>::makeEmpty()
{

	reclaimMemory(header->right);
	header->right = nullNode;
}

template <class T>
T * RedBlackTree<T>::findMin(void) const
{
	if (isEmpty() == true)
		return NULL;

	Node* itr = header->right;

	while (itr->left != nullNode)
		itr = itr->left;

	return &itr->element;
}

template <class T>
T * RedBlackTree<T>::findMax(void) const
{
	if (isEmpty() == true)
		return NULL;

	Node* itr = header->right;

	while (itr->right != nullNode)
		itr = itr->right;

	return &itr->element;
}

template <class T>
T * RedBlackTree<T>::find(const T & t) const
{
	if (isEmpty())
		return NULL;

	Node *itr = header->right;

	for (;;)
	{
		if (t < itr->element)
			itr = itr->left;
		else if (t > itr->element)
			itr = itr->right;
		else if (itr == nullNode)
			return NULL;
		else
			return &itr->element;
	}

}

template <class T>
class RedBlackTreeNode
{
	friend  RedBlackTree<T>;

public:
	RedBlackTreeNode(const T & ele = T(),
		RedBlackTreeNode* lf = NULL,
		RedBlackTreeNode *rg = NULL,
		int c = RedBlackTree<T>::BLACK) :element(ele), left(lf), right(rg), color(c)
	{};//红黑树节点构造函数
//private:
	RedBlackTreeNode *left;  //左子节点
	RedBlackTreeNode *right; //右子节点
	T element;				 //元素
	int color;				//节点颜色

};

void insert_test(void)
{
	cout << "insert_test" << endl;
	const int NEG_INFO = -9999;

	RedBlackTree<int> redBlackTree(NEG_INFO);

	redBlackTree.insert(30);
	redBlackTree.insert(15);
	redBlackTree.insert(70);
	redBlackTree.insert(20);

	cout << "原始数据:" << endl;
	cout << redBlackTree.header->right->element << endl;
	cout << redBlackTree.header->right->left->element << endl;
	cout << redBlackTree.header->right->right->element << endl;
	cout << redBlackTree.header->right->left->right->element << endl;
}

void single_rotate_test(void)
{
	cout << "single_rotate_test" << endl;
	const int NEG_INFO = -9999;
	RedBlackTree<int> redBlackTree(NEG_INFO);

	redBlackTree.insert(30);
	redBlackTree.insert(15);
	redBlackTree.insert(70);
	redBlackTree.insert(20);

	cout << "原始数据:" << endl;
	cout << redBlackTree.header->right->element << endl;
	cout << redBlackTree.header->right->left->element << endl;
	cout << redBlackTree.header->right->right->element << endl;
	cout << redBlackTree.header->right->left->right->element << endl;

	cout << "向右转:" << endl;
	redBlackTree.rotateWithLeftChild(redBlackTree.header->right);
	cout << redBlackTree.header->right->element << endl;
	cout << redBlackTree.header->right->right->element << endl;
	cout << redBlackTree.header->right->right->left->element << endl;
	cout << redBlackTree.header->right->right->right->element << endl;

	cout << "向左转:" << endl;
	redBlackTree.rotateWithRightChild(redBlackTree.header->right);
	cout << redBlackTree.header->right->element << endl;
	cout << redBlackTree.header->right->left->element << endl;
	cout << redBlackTree.header->right->right->element << endl;
	cout << redBlackTree.header->right->left->right->element << endl;
}

void double_rotate_test(void)
{
	cout << "double_rotate_test" << endl;
	const int NEG_INFO = -9999;
	RedBlackTree<int> tree(NEG_INFO);

	tree.insert(12);
	tree.insert(8);
	tree.insert(16);
	tree.insert(4);
	tree.insert(10);
	tree.insert(14);
	tree.insert(2);
	tree.insert(6);
	tree.insert(5);

	cout << "双旋转前:" << tree.header->right->left->left->right->left->element << endl;
	cout << "双旋转前:" << tree.header->right->right->left->element << endl;
	cout << "双旋转前:" << tree.header->right->left->right->element << endl;

	tree.doubleRotateWithLeftChild(tree.header->right->left);
	cout << "双旋转后:" << tree.header->right->left->left->left->element << endl;
	cout << "双旋转后:" << tree.header->right->left->left->right->element << endl;
}

void red_black_balance_test(void)
{
	cout << "red_black_balance_test" << endl;

	const int NEG_INFO = -9999;
	RedBlackTree<int> tree(NEG_INFO);

	tree.insert(50);
	tree.insert(40);
	tree.insert(30);

	cout << "树的根是:" << tree.header->right->element << endl; //没有平衡之前根是50，平衡之后根会变动
}

void red_black_empty_test(void)
{
	cout << "red_black_empty_test" << endl;
	const int NEG_INFO = -9999;
	RedBlackTree<int> tree(NEG_INFO);

	tree.insert(50);
	tree.insert(40);
	tree.insert(30);

	if (tree.isEmpty())
		cout << "是空的" << endl;
	else
		cout << "不是空的" << endl;

	tree.makeEmpty();

	if (tree.isEmpty())
		cout << "是空的" << endl;
	else
		cout << "不是空的" << endl;

}
void red_black_find_test(void)
{
	cout << "red_black_find_test" << endl;
	const int NEG_INFO = -9999;
	RedBlackTree<int> tree(NEG_INFO);

	tree.insert(50);
	tree.insert(40);

	tree.insert(30);


	cout << "最小值:" << *tree.findMin() << endl;
	cout << "最大值:" << *tree.findMax() << endl;

	int num = 40;

	int * p = tree.find(num);

	if (p != NULL)
		cout << "找到了:" << *p << endl;
	else
		cout << "没有找到" << endl;
}

int main()
{
	//insert_test();
	//single_rotate_test();
	//double_rotate_test();
	//red_black_balance_test();
	//red_black_empty_test();
	red_black_find_test();

	return 0;
}

运行结果：