Mars_Cat

Description

Input

Output

Sample Input

Sample Output

HINT

继续学习红黑树的结点删除QaQ

#include 
#include 

using namespace std;

struct node
{
	bool Color; //True: Red  False: Black
	int Key;
	node* p;
	node* left, * right;
};

int ans = 0;
node* Root;//根节点
node* NIL;//空节点

#ifdef _DEBUG
template
constexpr auto min(Type a, Type b) { if (a < b)return a; else return b; }
#else
#define min(a,b) ((a)<(b)?(a):(b))
#endif // _DEBUG

void Init()
{
	NIL = new node;					//定义空哨兵节点（叶子结点和根节点的父节点）
	NIL->Color = false;
	NIL->left = NIL->right = NULL;
	NIL->Key = 0;

	Root = NULL;
}

int Insert(node* pnt, node *z)		//插入元素 返回值为与树内结点差绝对值最小值
{
	if (pnt == NULL)				//空红黑树 p为根节点
	{
		Root = z;
		z->p = NIL;
		return z->Key;
	}
	int temp;//临时变量 用于记录下一层Insert返回值
	if (z->Key < pnt->Key)//z将被加入左子树豪华午餐
	{
		if (pnt->left == NIL)
		{
			pnt->left = z;
			z->p = pnt;
			return pnt->Key - z->Key;
		}
		else
		{
			temp = Insert(pnt->left, z);
			return min(temp, pnt->Key - z->Key);
		}
	}
	else //z将被加入右子树奢华晚餐
	{
		if (pnt->right == NIL)
		{
			pnt->right = z;
			z->p = pnt;
			return z->Key - pnt->Key;
		}
		else
		{
			temp = Insert(pnt->right, z);
			return min(temp, z->Key - pnt->Key);
		}
	}
}

void Shift_L(node* pnt)//树左旋
{
	node* temp = pnt->right;
	pnt->right = temp->left;
	temp->left->p = pnt;
	temp->p = pnt->p;
	if (pnt->p->left == pnt)pnt->p->left = temp;
	else pnt->p->right = temp;
	pnt->p = temp;
	temp->left = pnt;
	if (pnt == Root)Root = temp;
}

void Shift_R(node* pnt)//树右旋
{
	node* temp = pnt->left;
	pnt->left = temp->right;
	temp->right->p = pnt;
	temp->p = pnt->p;
	if (pnt->p->left == pnt)pnt->p->left = temp;
	else pnt->p->right = temp;
	pnt->p = temp;
	temp->right = pnt;
	if (pnt == Root)Root = temp;
}

void Fix_up(node* z)
{
	while (z->p->Color)//z的父节点为红色（z也为红色）不符合红黑树定义
	{
		if (z->p->p->left == z->p)//z的父节点在祖父节点的左子树上
		{
			if (z->p->p->right->Color)//叔节点为红色
			{
				z->p->p->Color = true;
				z->p->p->left->Color = z->p->p->right->Color = false;
				z = z->p->p;
			}
			else
			{
				if (z == z->p->right)//z在右节点上，左旋一下
				{
					z = z->p;
					Shift_L(z);
				}
				z->p->Color = false;
				z->p->p->Color = true;
				Shift_R(z->p->p);
			}
		}
		else //z的父节点在z的祖父节点右子树上 所有操作左右相反即可
		{
			if (z->p->p->left->Color)//叔节点为红色
			{
				z->p->p->Color = true;
				z->p->p->left->Color = z->p->p->right->Color = false;
				z = z->p->p;
			}
			else
			{
				if (z == z->p->left)//z在左节点上，右旋一下
				{
					z = z->p;
					Shift_R(z);
				}
				z->p->Color = false;
				z->p->p->Color = true;
				Shift_L(z->p->p);
			}
		}
	}
	Root->Color = false;
}

void TreeOut(node* Pos)
{
	if (Pos == NIL)return;
	printf("%d %d l:%d r:%d p:%d\n", Pos->Key, Pos->Color, Pos->left->Key, Pos->right->Key, Pos->p->Key);
	TreeOut(Pos->left);
	TreeOut(Pos->right);
}

int n, x;
int main()
{
	Init();
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &x);
		node* z = new node;
		z->Key = x;
		z->left = z->right = NIL;
		z->Color = true;
		ans += Insert(Root, z);
		Fix_up(z);
#ifdef _DEBUG
		printf("-------------%d------------\n", x);
		TreeOut(Root);
#endif // _DEBUG
	}
	printf("%d\n", ans);
	return 0;
}