RT, Insert 操作中统计每个根节点的 Size 出错

应输出 1 2 3 2

实际输出 1 2 4 3

#include <iostream>
using namespace std;

template<class T>
class RB_Tree {
private:
	static const bool RED = 0;
	static const bool BLACK = 1;
	struct Node { //红黑树节点
		T Value;
		int Size;
		bool Color;
		Node* LeftTree, * RightTree, * Parent;
		Node() : Value(0), Size(0) , Color(RED), LeftTree(NULL), RightTree(NULL), Parent(NULL) { }
		Node* GrandParent() {
			if (Parent == NULL)
				return NULL;
			else 
				return Parent->Parent;
		}
		Node* Uncle() {
			if (GrandParent() == NULL)
				return NULL;
			if (Parent == GrandParent()->RightTree)
				return GrandParent()->LeftTree;
			else
				return GrandParent()->RightTree;
		}
		Node* Sibling() {
			if (Parent->LeftTree == this)
				return Parent->RightTree;
			else
				return Parent->LeftTree;
		}
	};
	void Rotate_Right(Node* p) { //右旋
		Node* gp = p->GrandParent();
		Node* fa = p->Parent;
		Node* y = p->RightTree;

		fa->LeftTree = y;

		if (y != NIL)
			y->Parent = fa;
		p->RightTree = fa;
		fa->Parent = p;

		if (root == fa)
			root = p;
		p->Parent = gp;

		if (gp != NULL) {
			if (gp->LeftTree == fa)
				gp->LeftTree = p;
			else
				gp->RightTree = p;
		}
	}  
	void Rotate_Left(Node* p) { //左旋
		if (p->Parent == NULL) {
			root = p;
			return;
		}
		Node* gp = p->GrandParent();
		Node* fa = p->Parent;
		Node* y = p->LeftTree;

		fa->RightTree = y;

		if (y != NIL)
			y->Parent = fa;
		p->LeftTree = fa;
		fa->Parent = p;

		if (root == fa)
			root = p;
		p->Parent = gp;

		if (gp != NULL) {
			if (gp->LeftTree == fa)
				gp->LeftTree = p;
			else
				gp->RightTree = p;
		}
	}
	void Inorder(Node* p) { //中根遍历
		if (p == NIL)
			return;

		if (p->LeftTree)
			inorder(p->LeftTree);

		cout << p->Value << " ";

		if (p->rightTree)
			inorder(p->RightTree);
	}
	string OutPutColor(bool color) { //输出颜色
		return color ? "BLACK" : "RED";
	}
	Node* GetSmallestChild(Node* p) { //最小键
		if (p->LeftTree == NIL)
			return p;
		return GetSmallestChild(p->LeftTree);
	}
	Node* GetBiggestChild(Node* p) { //最大键
		if (p->RightTree == NIL)
			return p;
		return GetSmallestChild(p->RightTree);
	}
	bool Delete_Child(Node* p, T Date) { //删除
		if (p->Value > Date) {
			if (p->LeftTree == NIL)
				return false;
			return Delete_Child(p->LeftTree, Date);
		}
		else if (p->Value < Date) {
			if (p->RightTree == NIL)
				return false;
			return Delete_Child(p->RightTree, Date);
		}
		else if (p->Value == Date) {
			if (p->RightTree == NIL) {
				p->Parent->Size--;
				Delete_One_Child(p);
				return true;
			}
			Node* smallest = GetSmallestChild(p->RightTree);
			swap(p->Value, smallest->Value);
			smallest->Parent->Size--;
			Delete_One_Child(smallest);
			return true;
		}
		else {
			return false;
		}
		p->Size = p->LeftTree->Size + p->RightTree->Size + 1;
	}
	void Delete_One_Child(Node* p) {
		Node* child = p->LeftTree == NIL ? p->RightTree : p->LeftTree;
		if (p->Parent == NULL && p->LeftTree == NIL && p->RightTree == NIL) {
			p = NULL;
			root = p;
			return;
		}

		if (p->Parent == NULL) {
			delete  p;
			child->Parent = NULL;
			root = child;
			root->Color = BLACK;
			return;
		}

		if (p->Parent->LeftTree == p)
			p->Parent->LeftTree = child;
		else
			p->Parent->RightTree = child;

		child->Parent = p->Parent;

		if (p->Color == BLACK) {
			if (child->Color == RED)
				child->Color = BLACK;
			else
				Delete_Case(child);
		}
		delete p;
	}
	void Delete_Case(Node* p) {
		if (p->Parent == NULL) {
			p->Color = BLACK;
			return;
		}
		if (p->Sibling()->Color == RED) {
			p->Parent->Color = RED;
			p->Sibling()->Color = BLACK;
			if (p == p->Parent->LeftTree)
				Rotate_Left(p->Parent);
			else
				Rotate_Right(p->Parent);
		}
		if (p->Parent->Color == BLACK && p->Sibling()->Color == BLACK && p->Sibling()->LeftTree->Color == BLACK && p->Sibling()->RightTree->Color == BLACK) {
			p->Sibling()->Color = RED;
			Delete_Case(p->Parent);
		}
		else if (p->Parent->Color == RED && p->Sibling()->Color == BLACK && p->Sibling()->LeftTree->Color == BLACK && p->Sibling()->RightTree->Color == BLACK) {
			p->Sibling()->Color = RED;
			p->Parent->Color = BLACK;
		}
		else {
			if (p->Sibling()->Color == BLACK) {
				if (p == p->Parent->LeftTree && p->Sibling()->LeftTree->Color == RED && p->Sibling()->RightTree->Color == BLACK) {
					p->Sibling()->Color = RED;
					p->Sibling()->LeftTree->Color = BLACK;
					Rotate_Right(p->Sibling()->LeftTree);
				}
				else if (p == p->Parent->RightTree && p->Sibling()->LeftTree->Color == BLACK && p->Sibling()->RightTree->Color == RED) {
					p->Sibling()->Color = RED;
					p->Sibling()->RightTree->Color = BLACK;
					Rotate_Left(p->Sibling()->RightTree);
				}
			}
			p->Sibling()->Color = p->Parent->Color;
			p->Parent->Color = BLACK;
			if (p == p->Parent->LeftTree) {
				p->Sibling()->RightTree->Color = BLACK;
				Rotate_Left(p->Sibling());
			}
			else {
				p->Sibling()->LeftTree->Color = BLACK;
				Rotate_Right(p->Sibling());
			}
		}
	}
	void Insert(Node* p, T Data) { //插入
		if (p->Value >= Data) {
			if (p->LeftTree != NIL)
				Insert(p->LeftTree, Data);
			else {
				Node* tmp = new Node();
				tmp->Value = Data;
				tmp->LeftTree = tmp->RightTree = NIL;
				tmp->Parent = p;
				p->LeftTree = tmp;
				tmp->Size = 1;
				Insert_case(tmp);
				p->Size = p->LeftTree->Size + p->RightTree->Size + 1; //错误
			}
		}
		else {
			if (p->RightTree != NIL)
				Insert(p->RightTree, Data);
			else {
				Node* tmp = new Node();
				tmp->Value = Data;
				tmp->LeftTree = tmp->RightTree = NIL;
				tmp->Parent = p;
				p->RightTree = tmp;
				tmp->Size = 1;
				Insert_case(tmp);
				p->Size = p->LeftTree->Size + p->RightTree->Size + 1;//错误
			}
		}
	}
	void Insert_case(Node* p) {
		if (p->Parent == NULL) {
			root = p;
			p->Color = BLACK;
			return;
		}
		if (p->Parent->Color == RED) {
			if (p->Uncle()->Color == RED) {
				p->Parent->Color = p->Uncle()->Color = BLACK;
				p->GrandParent()->Color = RED;
				Insert_case(p->GrandParent());
			}
			else {
				if (p->Parent->RightTree == p && p->GrandParent()->LeftTree == p->Parent) {
					Rotate_Left(p);
					p->Color = BLACK;
					p->Parent->Color = RED;
					Rotate_Right(p);
				}
				else if (p->Parent->LeftTree == p && p->GrandParent()->RightTree == p->Parent) {
					Rotate_Right(p);
					p->Color = BLACK;
					p->Parent->Color = RED;
					Rotate_Left(p);
				}
				else if (p->Parent->LeftTree == p && p->GrandParent()->LeftTree == p->Parent) {
					p->Parent->Color = BLACK;
					p->GrandParent()->Color = RED;
					Rotate_Right(p->Parent);
				}
				else if (p->Parent->RightTree == p && p->GrandParent()->RightTree == p->Parent) {
					p->Parent->Color = BLACK;
					p->GrandParent()->Color = RED;
					Rotate_Left(p->Parent);
				}
			}
		}
	}
	void Delete_Tree(Node* p) { //删除红黑树
		if (!p || p == NIL) {
			return;
		}
		Delete_Tree(p->LeftTree);
		Delete_Tree(p->RightTree);
		delete p;
	}
public:
	RB_Tree() {
		NIL = new Node;
		NIL->Color = BLACK;
		root = NULL;
	}

	~RB_Tree() {
		if (root)
			Delete_Tree(root);
		delete NIL;
	}

	void Inorder() { //中根遍历
		if (root == NULL)
			return;
		Inorder(root);
		cout << endl;
	}

	void Insert(T x) { //插入
		if (root == NULL) {
			root = new Node();
			root->Color = BLACK;
			root->LeftTree = root->RightTree = NIL;
			root->Size = 1;
			root->Value = x;
		}
		else {
			Insert(root, x);
		}
	}

	bool Delete(T data) { //删除
		return Delete_Child(root, data);
	}

	int Size() {
		if (root == NULL)
			return 0;
		return root->Size;
	}
private:
	Node* root, * NIL;
};

RB_Tree<int> test;

int main() {
	test.Insert(1);
	cout << test.Size() << endl;
	test.Insert(2);
	cout << test.Size() << endl;
	test.Insert(4);
	cout << test.Size() << endl;
	test.Delete(4);
	cout << test.Size() << endl;
	return 0;
}