#include <stdio.h>
#include <stdlib.h>

typedef struct nodeType *node;
struct nodeType {
    int value;
	node left;
	node right;
};

node node_new(int value, node left, node right) {
	node n = malloc(sizeof(struct nodeType));
	n->value = value;
	n->left = left;
	n->right = right;
	return n;
}

void node_dump(node n, int c) {
	int i;
	if (n == NULL) {
		return;
	}
	node_dump(n->right, c + 1);
	for (i = 0; i < c; i++) {
		printf("  ");
	}
	printf("%d\n", n->value);
	node_dump(n->left, c + 1);
}

node rightRotate1(node a) {
	node b = a->left;
	a->left = b->right;
	b->right = a;
	return b;
}

node rightRotate2(node a) {
	node e = a->left->right;
	a->left->right = e->left;
	e->left = a->left;
	a->left = e->right;
	e->right = a;
	return e;
}

void rightRotate1Test(void) {
	node e = node_new(3, NULL, NULL);
	node d = node_new(1, NULL, NULL);
	node b = node_new(2, d, e);
	node c = node_new(5, NULL, NULL);
	node a = node_new(4, b, c);
	
	printf("右へ一重回転\n");
	printf("  回転前\n");
	node_dump(a, 1);
	printf("\n");
	b = rightRotate1(a);
	printf("  回転後\n");
	node_dump(b, 1);
	printf("\n");
}

void rightRotate2Test(void) {
	node g = node_new(5, NULL, NULL);
	node f = node_new(3, NULL, NULL);
	node e = node_new(4, f, g);
	node d = node_new(1, NULL, NULL);
	node b = node_new(2, d, e);
	node c = node_new(7, NULL, NULL);
	node a = node_new(6, b, c);

	printf("右へ二重回転\n");
	printf("  回転前\n");
	node_dump(a, 1);
	printf("\n");
	e = rightRotate2(a);
	printf("  回転後\n");
	node_dump(e, 1);
	printf("\n");
}

int main(void) {
	rightRotate1Test();
	rightRotate2Test();
	
	return EXIT_SUCCESS;
}