#pragma once

//红黑树

class RBTree

{

private:

	typedef enum

	{

		E_TREE_BLACK,

		E_TREE_RED,

		E_TREE_COLOR_MAX

	}ETreeColor;

	const static char *s_pszColor[E_TREE_COLOR_MAX];

	typedef struct  __TreeNode

	{

		__TreeNode* pParent;

		__TreeNode* pLeft;

		__TreeNode* pRight;

		ETreeColor eColor;

		int nValue;

	}TreeNode, *PTreeNode;

public:

	RBTree();

	~RBTree();

	//插入数据

	void InsertData(int nValue);  //插入数据

	bool Empty();  //判空

	bool GetMax(PTreeNode pNode, int &nMax); // 获取最大值

	bool GetMin(PTreeNode pNode, int &nMin); //获取最小值

	void DeleteElement(int nDelete);  //删除指定的元素

	bool FindElement(int nFindValue); //查找数据,如果查找到返回true，否则返回false

	void BreadthEnum();  //广度遍历

private:

	void InsertFixUp(PTreeNode pInsertNode); //插入pInsertNode点后调整红黑树

	void DeleteFixUp(PTreeNode pFixNode); //删除后重新调整

	void SingleL(PTreeNode &pNode, PTreeNode &newTop); //左旋转,并且返回新的顶点

	void SingleR(PTreeNode &pNode, PTreeNode &newTop); //右旋转

	void ReplaceParent(PTreeNode pBeReplacedNode, PTreeNode pReplaceNode); //把pReplaceNode的父节点修改为pBeReplacedNode的

	bool GetMinNode(PTreeNode pNode, PTreeNode &pMinNode);//获取最小的节点

private:

	PTreeNode m_pRoot;  //根节点指针

	PTreeNode m_pNil;  //空节点

};