Mytests/rbt.cpp at master · Sakura-TA/Mytests · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <cstdlib>
#include <unistd.h>
#include <cstring>
using namespace std;

class node
{
public:
	node *lson;
	node *rson;
	node *parent;
	int value;
	bool islson;
	bool red;
	void turn(bool l)
	{
		if(!l)
		{
			if(lson!=NULL)parent->rson=lson,lson->islson=false,lson->parent=parent;
			else parent->rson=NULL;
			islson=parent->islson,lson=parent;
			if(parent->parent==NULL);
			else if(parent->islson) parent->parent->lson=this;
			else parent->parent->rson=this;
			parent=lson->parent,lson->parent=this,lson->islson=true;
		}
		else
		{
			parent->lson=rson;
			if(rson!=NULL) rson->islson=true,rson->parent=parent;
			islson=parent->islson,rson=parent;
			if(parent->parent==NULL);
			else if(parent->islson) parent->parent->lson=this;
			else parent->parent->rson=this;
			parent=rson->parent,rson->parent=this,rson->islson=false;
		}
	}
	void checkinsert()
	{
		if(parent==NULL) red=false;
		else if(!parent->red) return;
		else{
			node *pp=parent->parent;
			if(pp->lson!=NULL&&pp->rson!=NULL&&pp->lson->red&&pp->rson->red)
			{
				pp->lson->red=pp->rson->red=false;
				pp->red=true;
				pp->checkinsert();
			}
			else
			{
				if(parent->islson==islson)
				{
					parent->red=false;
					parent->parent->red=true;
					parent->turn(islson);
				}
				else
				{
					node *t=parent;
					turn(islson);
					t->checkinsert();
				}
			}
		}
	}
	node(int val,node *p,bool l)
	{
		value=val;
		lson=NULL;
		rson=NULL;
		islson=l;
		parent=p;
		red=true;
		checkinsert();
	}
	node* getlson(){return lson;}
	node* getrson(){return rson;}
	int getvalue(){return value;}
	void insert(int val)
	{
		if(val<value)
		{
			if(lson==NULL) lson=new node(val,this,true);
			else lson->insert(val);
		}
		else if(val==value) return;
		else
		{
			if(rson==NULL) rson=new node(val,this,false);
			else rson->insert(val);
		}
	}
	void mprint()
	{
		if(lson!=NULL) lson->mprint();
		cout<<value<<" "<<islson<<" "<<(lson==NULL?"NULL":"L")<<" "<<(rson==NULL?"NULL":"R")<<endl;
		if(rson!=NULL) rson->mprint();
	}
};

int main()
{
	srand(time(0));
	node *root=NULL,*t=NULL;
	int x;
	for(int i=0;i<3;i++)
	{
		cin>>x;
		if(root==NULL) root=new node(x,NULL,false);
		else root->insert(x);
		while(root->parent!=NULL) root=root->parent;
	}
	root->mprint();
	cout<<endl;
}