[数据结构与算法]红黑树的自底向上插入

//.h声明
class RedBlackTree {
public:
	enum ColorType {red,black};
	struct RedBlackNode {
		elemenType val;
		RedBlackNode*left;
		RedBlackNode*right;
		ColorType color;
	};
	typedef RedBlackNode* pNode;
	

	RedBlackTree();
	~RedBlackTree();

	void Insert(elemenType);
	pNode Insert(elemenType,pNode);
	void ShowTree();
	pNode get_root();

private:
	pNode root;
	static pNode NullNode;

	void Init();
	pNode CreateNode(elemenType);
	void MakeEmpty();
	void MakeEmpty(pNode);
	short StateMachine(pNode,pNode,pNode);
	pNode L_L_Rotate(pNode);
	pNode L_R_Rotate(pNode);
	pNode R_R_Rotate(pNode);
	pNode R_L_Rotate(pNode);
	void DrawBlack(pNode);
	void DrawRed(pNode);

};

//定义.cpp 
RedBlackTree::pNode RedBlackTree::NullNode = nullptr;  //全体对象共享

 //private:
void RedBlackTree::Init(){
	if (NullNode == nullptr) {
		NullNode = new RedBlackTree::RedBlackNode;
		NullNode->color = black;
		NullNode->left = NullNode->right = NullNode;
	}
 }

RedBlackTree::pNode RedBlackTree::CreateNode(elemenType n) {
	pNode temp = new RedBlackNode;
	temp->left = temp->right = NullNode;
	temp->val = n;
	temp->color = red;
	return temp;
}

void RedBlackTree::MakeEmpty() {
	MakeEmpty(root);
	root = NullNode;
}

void RedBlackTree::MakeEmpty(pNode root) {
	if (root == NullNode)
		return;
	MakeEmpty(root->left);
	MakeEmpty(root->right);
	delete root;
}

short RedBlackTree::StateMachine(pNode son, pNode parent, pNode grandpa) {
	if (grandpa->val > parent->val &&parent->val > son->val)
		if (grandpa->right->color == black)
			return 1;
		else return 2;
	else if (grandpa->val < parent->val&&parent->val < son->val)
		if (grandpa->left->color == black)
			return 3;
		else return 4;
	else if (grandpa->val > parent->val &&parent->val < son->val)
		if (grandpa->right->color == black)
			return 5;
		else return 6;
	else {
		if (grandpa->left->color == black)
			return 7;
		else return 8;
	}
	return 0;
}

RedBlackTree::pNode RedBlackTree::L_L_Rotate(pNode T)	
{
	pNode temp = T->left;
	T->left = temp->right;
	temp->right = T;
	return temp;

}

RedBlackTree::pNode RedBlackTree::R_R_Rotate(pNode T) {
	pNode temp = T->right;
	T->right = temp->left;
	temp->left = T;
	return temp;
}

RedBlackTree::pNode RedBlackTree::L_R_Rotate(pNode T) {
	T->left = R_R_Rotate(T->left);
	T = L_L_Rotate(T);
	return T;
}

RedBlackTree::pNode RedBlackTree::R_L_Rotate(pNode T) {
	T->right = L_L_Rotate(T->right);
	T = R_R_Rotate(T);
	return T;
}

//public:
RedBlackTree::RedBlackTree() {
	if (NullNode == nullptr) {
		NullNode = new RedBlackNode;
		NullNode->color = black;
		NullNode->left = NullNode->right = NullNode;
	}
	root = NullNode;
}

RedBlackTree::~RedBlackTree() {
	MakeEmpty();
}

void RedBlackTree::Insert(elemenType n) {
	if (root == NullNode) {
		root = new RedBlackNode;
		root->left = root->right = NullNode;
		root->color = black;
		root->val = n; return;
	}
	root = Insert(n, root);
}

void RedBlackTree::DrawBlack(pNode root) {
	root->color = black;
	root->left->color = root->right->color = red;
}

void RedBlackTree::DrawRed(pNode root) {
	root->color = red;
	root->left->color = root->right->color = black;
}

RedBlackTree::pNode RedBlackTree::Insert(elemenType n,pNode root) {
	using std::vector;
	vector<pNode>stack;
	while (root != NullNode) {
		stack.push_back(root);
		if (root->val == n) {
			std::cout << "already exist\n";
			return RedBlackTree::root;
		}
		if (root->val > n) {
			root = root->left;
		}
		else root = root->right;
	}

	root = stack.back();
	if (root->val > n) {
		root->left = CreateNode(n);
		stack.push_back(root->left);
	}
	else {
		root->right = CreateNode(n);
		stack.push_back(root->right);
	}
	if (stack.size() <= 2) 
		return stack.at(0);

	pNode temp=NullNode;
	short son, parent, grandpa;
	short solve;
	while (stack.size() > 2) {
		son = stack.size() - 1;
		parent = son - 1;
		grandpa = parent - 1;
		if (stack.at(son)->color||stack.at(parent)->color) 
			return stack.at(0);
		solve = StateMachine(stack.at(son), stack.at(parent), stack.at(grandpa));
		switch (solve) {
		case 1:temp = L_L_Rotate(stack.at(grandpa)); DrawBlack(temp); break;
		case 2:temp = L_L_Rotate(stack.at(grandpa)); DrawRed(temp); break;
		case 3:temp = R_R_Rotate(stack.at(grandpa)); DrawBlack(temp); break;
		case 4:temp = R_R_Rotate(stack.at(grandpa)); DrawRed(temp); break;
		case 5:temp = L_R_Rotate(stack.at(grandpa)); DrawBlack(temp); break;
		case 6:temp = L_R_Rotate(stack.at(grandpa)); DrawRed(temp); break;
		case 7:temp = R_L_Rotate(stack.at(grandpa)); DrawBlack(temp); break;
		case 8:temp = R_L_Rotate(stack.at(grandpa)); DrawRed(temp); break;
		default:std::cout << "error !!!\n"; break;
		}

		if (grandpa) {
			int index = grandpa - 1;
			stack[index]->left == stack[grandpa] ? stack[index]->left = temp : stack[index]->right = temp;
		}
		for (int i = 3; i > 0; i--)
			stack.pop_back();
		stack.push_back(temp);

	}
	stack.at(0)->color = black;
	return stack.at(0);
}

void RedBlackTree::ShowTree() {
	using std::vector;
	if (root == NullNode)
		return;
	pNode temp;
	vector<pNode> stack;
	short index = 1, front = 0;
	stack.push_back(root);
	while (stack.size() > front) {
		while (index) {
			temp = stack.at(front++);
			if (temp != NullNode) {
				stack.push_back(temp->left);
				stack.push_back(temp->right);

				std::cout << temp->val;
				if (temp->color == black)
					std::cout << 'B';
				else std::cout << 'R';
				std::cout << ' ';
			}
			else {
				std::cout << 'N' << " ";
			}
			index--;
		}
		index = stack.size() - front;
		std::cout << std::endl;
	}
}

通常的红黑树的插入时自顶向下，为了实践实现了一下自底向上的方法，使用了NullNode以简化讨论，使用伪状态机（懒得改了）来实现简洁化代码。已经检验过，可以直接使用