#include<stdio.h>
#include<stdlib.h>
struct node {
int data;
char colour;
struct node *leftChild;
struct node *rightChild;
struct node *parent;
};
struct node *rotateL(struct node *Root, struct node *x) {
struct node *right;
right=x->rightChild;
x->rightChild=right->leftChild;
if(right->leftChild != NULL) {
right->leftChild->parent = x;
}
right->parent=x->parent;
if(x->parent == NULL) {
Root=right;
}
else if(x==x->parent->leftChild) {
x->parent->leftChild=right;
}
else {
x->parent->rightChild=right;
}
right->leftChild=x;
x->parent=right;
}
struct node *rotateR(struct node *Root, struct node *x) {
struct node *left;
left=x->leftChild;
x->leftChild=left->rightChild;
if(left->rightChild!= NULL) {
left->rightChild->parent = x;
}
left->parent=x->parent;
if(x->parent == NULL) {
Root=left;
}
else if(x==x->parent->rightChild) {
x->parent->rightChild=left;
}
else {
x->parent->leftChild=left;
}
left->rightChild=x;
x->parent=left;
}
void rebalance(struct node *Root, struct node *x) {
struct node *y;
while (x != Root && x->colour=='R' && x->parent->colour=='R') {
if (x->parent==x->parent->parent->leftChild) {
y=x->parent->parent->rightChild;
if (y!= NULL && y->colour=='R') {
x->parent->parent->colour='R';
x->parent->colour='B';
y->colour='B';
x=x->parent->parent;
}
else {
if (x==x->parent->rightChild) {
x=x->parent;
rotateL(Root, x);
}
rotateR(Root, x->parent->parent);
x->parent->colour='B';
x->parent->parent->colour='R';
x=x->parent;
}
}
else {
y = x->parent->parent->leftChild;
if (y!=NULL && y->colour=='R') {
x->parent->parent->colour='R';
x->parent->colour='B';
y->colour='B';
x=x->parent->parent;
}
else {
if (x==x->parent->leftChild) {
x=x->parent;
rotateR(Root, x->parent);
}
rotateL(Root, x->parent->parent);
x->parent->colour='B';
x->parent->parent->colour='R';
x=x->parent;
}
}
}
Root->colour='B';
}
struct node rbtinsert(struct node *Root, struct node *val)
{
struct node *x, *y;
y=NULL;
x=Root;
while (x!=NULL) {
y=x;
if(val->data<x->data) {
x=x->leftChild;
}
else {
x=x->rightChild;
}
}
val->parent=y;
if (y==NULL) {
Root=val;
}
else if (val->data<y->data) {
y->leftChild=val;
}
else {
y->rightChild=val;
}
val->leftChild=NULL;
val->rightChild=NULL;
val->colour='R';
rebalance(Root, val);
return *Root;
}
void Visit(struct node *x, struct node *Root) {
if(x==NULL) {
return;
}
Visit(x->leftChild, Root);
if(x==Root) {
printf("%d %c %s\n", x
->data
, x
->colour
, "NIL"); }
else {
printf("%d %c %d\n", x
->data
, x
->colour
, x
->parent
->data
); }
Visit(x->rightChild, Root);
}
int Pre_fix_Tour(struct node *Root) {
if(Root==NULL) {
return -1;
}
else {
Visit(Root, Root);
}
}
int main(void) {
int n;
struct node a[n];
for(int i=0;i<n;i++) {
a[i].colour='R';
a[i].leftChild=NULL;
a[i].rightChild=NULL;
a[i].parent=NULL;
}
struct node *temp;
temp=&a[0];
for(int i=0; i<n; i++) {
*temp=rbtinsert(temp, &a[i]);
}
int t=Pre_fix_Tour(temp);
if(t==-1){
}
return 0;
/*printf("%d", temp->data);*/
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8c3RkbGliLmg+CnN0cnVjdCBub2RlIHsKICAgIGludCBkYXRhOwogICAgY2hhciBjb2xvdXI7CiAgICBzdHJ1Y3Qgbm9kZSAqbGVmdENoaWxkOwogICAgc3RydWN0IG5vZGUgKnJpZ2h0Q2hpbGQ7CiAgICBzdHJ1Y3Qgbm9kZSAqcGFyZW50Owp9OwpzdHJ1Y3Qgbm9kZSAqcm90YXRlTChzdHJ1Y3Qgbm9kZSAqUm9vdCwgc3RydWN0IG5vZGUgKngpIHsKICAgIHN0cnVjdCBub2RlICpyaWdodDsKICAgIHJpZ2h0PXgtPnJpZ2h0Q2hpbGQ7CiAgICB4LT5yaWdodENoaWxkPXJpZ2h0LT5sZWZ0Q2hpbGQ7CiAgICBpZihyaWdodC0+bGVmdENoaWxkICE9IE5VTEwpIHsKICAgICAgICByaWdodC0+bGVmdENoaWxkLT5wYXJlbnQgPSB4OwogICAgfQogICAgcmlnaHQtPnBhcmVudD14LT5wYXJlbnQ7CiAgICBpZih4LT5wYXJlbnQgPT0gTlVMTCkgewogICAgICAgIFJvb3Q9cmlnaHQ7CiAgICB9CiAgICBlbHNlIGlmKHg9PXgtPnBhcmVudC0+bGVmdENoaWxkKSB7CiAgICAgICAgeC0+cGFyZW50LT5sZWZ0Q2hpbGQ9cmlnaHQ7CiAgICB9CiAgICBlbHNlIHsKICAgICAgICB4LT5wYXJlbnQtPnJpZ2h0Q2hpbGQ9cmlnaHQ7CiAgICB9CiAgICByaWdodC0+bGVmdENoaWxkPXg7CiAgICB4LT5wYXJlbnQ9cmlnaHQ7Cn0Kc3RydWN0IG5vZGUgKnJvdGF0ZVIoc3RydWN0IG5vZGUgKlJvb3QsIHN0cnVjdCBub2RlICp4KSB7CiAgICBzdHJ1Y3Qgbm9kZSAqbGVmdDsKICAgIGxlZnQ9eC0+bGVmdENoaWxkOwogICAgeC0+bGVmdENoaWxkPWxlZnQtPnJpZ2h0Q2hpbGQ7CiAgICBpZihsZWZ0LT5yaWdodENoaWxkIT0gTlVMTCkgewogICAgICAgIGxlZnQtPnJpZ2h0Q2hpbGQtPnBhcmVudCA9IHg7CiAgICB9CiAgICBsZWZ0LT5wYXJlbnQ9eC0+cGFyZW50OwogICAgaWYoeC0+cGFyZW50ID09IE5VTEwpIHsKICAgICAgICBSb290PWxlZnQ7CiAgICB9CiAgICBlbHNlIGlmKHg9PXgtPnBhcmVudC0+cmlnaHRDaGlsZCkgewogICAgICAgIHgtPnBhcmVudC0+cmlnaHRDaGlsZD1sZWZ0OwogICAgfQogICAgZWxzZSB7CiAgICAgICAgeC0+cGFyZW50LT5sZWZ0Q2hpbGQ9bGVmdDsKICAgIH0KICAgIGxlZnQtPnJpZ2h0Q2hpbGQ9eDsKICAgIHgtPnBhcmVudD1sZWZ0Owp9CnZvaWQgcmViYWxhbmNlKHN0cnVjdCBub2RlICpSb290LCBzdHJ1Y3Qgbm9kZSAqeCkgewogICAgc3RydWN0IG5vZGUgKnk7CiAgICB3aGlsZSAoeCAhPSBSb290ICYmIHgtPmNvbG91cj09J1InICYmIHgtPnBhcmVudC0+Y29sb3VyPT0nUicpIHsKICAgICAgICBpZiAoeC0+cGFyZW50PT14LT5wYXJlbnQtPnBhcmVudC0+bGVmdENoaWxkKSB7CiAgICAgICAgICAgIHk9eC0+cGFyZW50LT5wYXJlbnQtPnJpZ2h0Q2hpbGQ7CiAgICAgICAgICAgIGlmICh5IT0gTlVMTCAmJiB5LT5jb2xvdXI9PSdSJykgewogICAgICAgICAgICAgICAgeC0+cGFyZW50LT5wYXJlbnQtPmNvbG91cj0nUic7CiAgICAgICAgICAgICAgICB4LT5wYXJlbnQtPmNvbG91cj0nQic7CiAgICAgICAgICAgICAgICB5LT5jb2xvdXI9J0InOwogICAgICAgICAgICAgICAgeD14LT5wYXJlbnQtPnBhcmVudDsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIHsKICAgICAgICAgICAgICAgIGlmICh4PT14LT5wYXJlbnQtPnJpZ2h0Q2hpbGQpIHsKICAgICAgICAgICAgICAgICAgICB4PXgtPnBhcmVudDsKICAgICAgICAgICAgICAgICAgICByb3RhdGVMKFJvb3QsIHgpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgcm90YXRlUihSb290LCB4LT5wYXJlbnQtPnBhcmVudCk7CiAgICAgICAgICAgICAgICB4LT5wYXJlbnQtPmNvbG91cj0nQic7CiAgICAgICAgICAgICAgICB4LT5wYXJlbnQtPnBhcmVudC0+Y29sb3VyPSdSJzsKICAgICAgICAgICAgICAgIHg9eC0+cGFyZW50OwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGVsc2UgewogICAgICAgICAgICB5ID0geC0+cGFyZW50LT5wYXJlbnQtPmxlZnRDaGlsZDsKICAgICAgICAgICAgaWYgKHkhPU5VTEwgJiYgeS0+Y29sb3VyPT0nUicpIHsKICAgICAgICAgICAgICAgIHgtPnBhcmVudC0+cGFyZW50LT5jb2xvdXI9J1InOwogICAgICAgICAgICAgICAgeC0+cGFyZW50LT5jb2xvdXI9J0InOwogICAgICAgICAgICAgICAgeS0+Y29sb3VyPSdCJzsKICAgICAgICAgICAgICAgIHg9eC0+cGFyZW50LT5wYXJlbnQ7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZSB7CiAgICAgICAgICAgICAgICBpZiAoeD09eC0+cGFyZW50LT5sZWZ0Q2hpbGQpIHsKICAgICAgICAgICAgICAgICAgICB4PXgtPnBhcmVudDsKICAgICAgICAgICAgICAgICAgICByb3RhdGVSKFJvb3QsIHgtPnBhcmVudCk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICByb3RhdGVMKFJvb3QsIHgtPnBhcmVudC0+cGFyZW50KTsKICAgICAgICAgICAgICAgIHgtPnBhcmVudC0+Y29sb3VyPSdCJzsKICAgICAgICAgICAgICAgIHgtPnBhcmVudC0+cGFyZW50LT5jb2xvdXI9J1InOwogICAgICAgICAgICAgICAgeD14LT5wYXJlbnQ7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBSb290LT5jb2xvdXI9J0InOwp9CnN0cnVjdCBub2RlIHJidGluc2VydChzdHJ1Y3Qgbm9kZSAqUm9vdCwgc3RydWN0IG5vZGUgKnZhbCkKewogICAgc3RydWN0IG5vZGUgKngsICp5OwogICAgeT1OVUxMOwogICAgeD1Sb290OwogICAgd2hpbGUgKHghPU5VTEwpIHsKICAgICAgICB5PXg7CiAgICAgICAgaWYodmFsLT5kYXRhPHgtPmRhdGEpIHsKICAgICAgICAgICAgeD14LT5sZWZ0Q2hpbGQ7CiAgICAgICAgfQogICAgICAgIGVsc2UgewogICAgICAgICAgICB4PXgtPnJpZ2h0Q2hpbGQ7CiAgICAgICAgfQogICAgfQogICAgdmFsLT5wYXJlbnQ9eTsKICAgIGlmICh5PT1OVUxMKSB7CiAgICAgICAgUm9vdD12YWw7CiAgICB9CiAgICBlbHNlIGlmICh2YWwtPmRhdGE8eS0+ZGF0YSkgewogICAgICAgIHktPmxlZnRDaGlsZD12YWw7CiAgICB9CiAgICBlbHNlIHsKICAgICAgICB5LT5yaWdodENoaWxkPXZhbDsKICAgIH0KICAgIHZhbC0+bGVmdENoaWxkPU5VTEw7CiAgICB2YWwtPnJpZ2h0Q2hpbGQ9TlVMTDsKICAgIHZhbC0+Y29sb3VyPSdSJzsKICAgIHJlYmFsYW5jZShSb290LCB2YWwpOwogICAgcmV0dXJuICpSb290Owp9CnZvaWQgVmlzaXQoc3RydWN0IG5vZGUgKngsIHN0cnVjdCBub2RlICpSb290KSB7CiAgICBpZih4PT1OVUxMKSB7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgVmlzaXQoeC0+bGVmdENoaWxkLCBSb290KTsKICAgIGlmKHg9PVJvb3QpIHsKICAgICAgICBwcmludGYoIiVkICVjICVzXG4iLCB4LT5kYXRhLCB4LT5jb2xvdXIsICJOSUwiKTsKICAgIH0KICAgIGVsc2UgewogICAgICAgIHByaW50ZigiJWQgJWMgJWRcbiIsIHgtPmRhdGEsIHgtPmNvbG91ciwgeC0+cGFyZW50LT5kYXRhKTsKICAgIH0KCiAgICBWaXNpdCh4LT5yaWdodENoaWxkLCBSb290KTsKfQoKaW50IFByZV9maXhfVG91cihzdHJ1Y3Qgbm9kZSAqUm9vdCkgewogICAgaWYoUm9vdD09TlVMTCkgewogICAgICAgIHJldHVybiAtMTsKICAgIH0KICAgIGVsc2UgewogICAgICAgIFZpc2l0KFJvb3QsIFJvb3QpOwogICAgfQp9CmludCBtYWluKHZvaWQpIHsKICAgIGludCBuOwogICAgc2NhbmYoIiVkIiwgJm4pOwogICAgc3RydWN0IG5vZGUgYVtuXTsKICAgIGZvcihpbnQgaT0wO2k8bjtpKyspIHsKICAgICAgICBzY2FuZigiJWQiLCAmYVtpXS5kYXRhKTsKICAgICAgICBhW2ldLmNvbG91cj0nUic7CiAgICAgICAgYVtpXS5sZWZ0Q2hpbGQ9TlVMTDsKICAgICAgICBhW2ldLnJpZ2h0Q2hpbGQ9TlVMTDsKICAgICAgICBhW2ldLnBhcmVudD1OVUxMOwogICAgfQogICAgc3RydWN0IG5vZGUgKnRlbXA7CiAgICB0ZW1wPSZhWzBdOwogICAgZm9yKGludCBpPTA7IGk8bjsgaSsrKSB7CiAgICAgICAgKnRlbXA9cmJ0aW5zZXJ0KHRlbXAsICZhW2ldKTsKICAgIH0KICAgIGludCB0PVByZV9maXhfVG91cih0ZW1wKTsKICAgIGlmKHQ9PS0xKXsKICAgICAgICBwcmludGYoImVtcHR5IHRyZWUiKTsKICAgIH0KICAgIHJldHVybiAwOwogICAgLypwcmludGYoIiVkIiwgdGVtcC0+ZGF0YSk7Ki8KfQ==