红黑树|定义、左旋函数、右旋函数和对插入结点的修复

红黑树|定义、左旋函数、右旋函数和对插入结点的修复

• 1.红黑树类的定义
• 2.左旋函数和右旋函数
• 3.对插入结点的修复

1.红黑树类的定义

enum class Color
{
	RED,
	BLACK
};

template<typename Key ,typename Value>
class RedBlackTree
{
	class Node 
	{
	public:
		Key key;
		Value value;
		Color color;
		Node* left;
		Node* right;
		Node* parent;
		
		Node()
			:color(Color::BLACK),left(NULL),right(NULL),parent(NULL)
		{}
		Node(const Key&key,const Value&value,Color color,Node*p=NULL)
			:key(key),value(value),color(color),left(NULL),right(NULL),parent(p)
		{}
	};

private:
	Node* root;
	size_t size;
	Node* Nil;
	};

2.左旋函数和右旋函数

//右旋函数
void rightRotate(Node* node)
{
	Node* p = node->left;
	//处理p的右孩子
	node->left = p->right;
	if (p->right != NULL)
		p->right->parent->node;
	//把p置为老大
	p->parent = node->parent;
	if (node->parent == NULL)
		root = p;
	if (node == node->parent->left)
		node->parent->left = p;
	else if (node == node->parent->right)
		node->parent->right = p;
	//让node成为p的右孩子
	p->right = node;
	node->parent = p;
}

//左旋函数
void leftRotate(Node* node)
{
	Node* p = node->right;
	node->right = p->left;
	if (p->left != NULL)
		p->left->parent = node;
	p->parent = node->parent;
	if (node->parent == NULL)
		root = p;
	if (node == node->parent->left)
		node->parent->left = p;
	else if (node == node->parent->right)
		node->parent->right = p;
	p->left = node;
	node->parent = p;
}

3.对插入结点的修复

void insertFixup(Node*target)
{
	while (target->parent != NULL && target->parent->color == Color::RED)
	{
		//父为祖左节点
		if (target->parent = target->parent->parent->left)
		{
			Node* uncle = target->parent->parent->right;
			//红叔
			if (uncle && uncle->color == Color::RED)
			{
				uncle->color == Color::BLACK;
				target->parent->color == Color::BLACK;
				target->parent->parent->color = Color::RED;
				target = target->parent->parent;
			}
			//黑叔
			else
			{
				//LR
				if (target == target->parent->right)
				{
					leftRotate(target->parent);
					rightRotate(target->parent);
					target->color = Color::BLACK;
					target->right->color = Color::RED;
				}
				//LL
				else if (target == target->parent->left)
				{
					rightRotate(target->parent->parent);
					target->parent->color = Color::BLACK;
					target->parent->right->color = Color::RED;
				}
			}
		}
		//父为祖的右节点
		else
		{
			Node* uncle = target->parent->left;
			//红叔
			if (uncle && uncle->color == Color::RED)
			{
				uncle->color == Color::BLACK;
				target->parent->color == Color::BLACK;
				target->parent->parent->color = Color::RED;
				target = target->parent->parent;
			}
			//黑叔
			else
			{
				//RL
				if (target == target->parent->left)
				{
					rightRotate(target->parent);
					leftRotate(target->parent);
					target->color = Color::BLACK;
					target->left->color = Color::RED;
				}
				//RR
				else if (target == target->parent->right)
				{
					leftRotate(target->parent->parent);
					target->parent->color = Color::BLACK;
					target->parent->left->color = Color::RED;
				}
			}	
		}
	}
	root->color = Color::BLACK;
}