/* coding by Leonardone @ NEETSDKASU */
#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
	struct _node *left;
	struct _node *right;
	int value;
} Node, *LPNode;

LPNode newNode(int value);
void releaseNode(LPNode node);
LPNode addNode(LPNode root, LPNode node);
int nodeDepth(LPNode node);
void calcDepth(LPNode node);
LPNode rotateR(LPNode node);
LPNode rotateL(LPNode node);

int iMax(int a, int b);

void seek(LPNode node) {
	if (node == NULL) {
		return;
	}
	printf("depth=%d, value=%d, left=%d, right=%d\n"
		, nodeDepth(node), node->value
		, nodeDepth(node->left), nodeDepth(node->right));
	printf("L[%d][%d]\n", nodeDepth(node), node->value);
	seek(node->left);
	printf("R[%d][%d]\n", nodeDepth(node), node->value);
	seek(node->right);
}

void n2bt(LPNode node, int *(*p), int i) {
	if (node == NULL || p == NULL) {
		return;
	}
	p[i] = &node->value;
	n2bt(node->left, p, (i << 1) + 1);
	n2bt(node->right, p, (i << 1) + 2);
}

void space(int n) {
	while (n-- > 0) {
		putchar(' ');
	}
}

void printTree(LPNode node) {
	int *(*a);
	int i, j, k;
	if (node == NULL) {
		return;
	}
	puts("----------------------------------");
	a = (int*(*))calloc(1 << nodeDepth(node), sizeof(int*));
	n2bt(node, a, 0);
	k = 0;
	for (i = 0; i < nodeDepth(node); i++) {
		space(2 * (nodeDepth(node) - i));
		for (j = 0; j < (1 << i); j++) {
			if (a[k] != NULL) {
				printf("%2d", *a[k]);
			} else {
				printf("--");
			}
			space(2 * (nodeDepth(node) - i));
			k++;
		}
		putchar('\n');
	}
	free(a);
}

int main(void) {
	
	LPNode root = NULL;
	
	root = addNode(root, newNode(5)); printTree(root);
	root = addNode(root, newNode(6)); printTree(root);
	root = addNode(root, newNode(9)); printTree(root);
	root = addNode(root, newNode(13)); printTree(root);
	root = addNode(root, newNode(11)); printTree(root);
	root = addNode(root, newNode(19)); printTree(root);
	root = addNode(root, newNode(7)); printTree(root);
	root = addNode(root, newNode(10)); printTree(root);
	root = addNode(root, newNode(8)); printTree(root);
	root = addNode(root, newNode(14)); printTree(root);
	root = addNode(root, newNode(4)); printTree(root);
	root = addNode(root, newNode(3)); printTree(root);
	root = addNode(root, newNode(16)); printTree(root);
	root = addNode(root, newNode(15)); printTree(root);
	root = addNode(root, newNode(2)); printTree(root);
	root = addNode(root, newNode(12)); printTree(root);

	puts("----------------------------------");

	seek(root);
	
	releaseNode(root);
	
	return 0;
}


int iMax(int a, int b) {
	return (a > b) ? a : b;
}

LPNode newNode(int value) {
	LPNode node = (LPNode)malloc(sizeof(Node));
	node->left = NULL;
	node->right = NULL;
	node->value = value;
	return node;
}

void releaseNode(LPNode node) {
	if (node == NULL) {
		return;
	}
	if (node->left != NULL) {
		releaseNode(node->left);
		node->left = NULL;
	}
	if (node->right != NULL) {
		releaseNode(node->right);
		node->right = NULL;
	}
	free(node);
}

int nodeDepth(LPNode node) {
	if (node != NULL) {
		return iMax(nodeDepth(node->left), nodeDepth(node->right)) + 1;
	} else {
		return 0;
	}
}

LPNode rotateR(LPNode node) {
	LPNode temp1, temp2;
	if (node == NULL || node->right == NULL) {
		return node;
	}
	temp1 = node->right;
	if (nodeDepth(temp1->left) > nodeDepth(temp1->right)) {
		temp2 = temp1->left;
		node->right = temp2->left;
		temp1->left = temp2->right;
		temp2->left = node;
		temp2->right = temp1;
		return temp2;
	} else {
		node->right = temp1->left;
		temp1->left = node;
		return temp1;
	}
}

LPNode rotateL(LPNode node) {
	LPNode temp1, temp2;
	if (node == NULL || node->left == NULL) {
		return node;
	}
	temp1 = node->left;
	if (nodeDepth(temp1->left) > nodeDepth(temp1->right)) {
		node->left = temp1->right;
		temp1->right = node;
		return temp1;
	} else {
		temp2 = temp1->right;
		temp1->right = temp2->left;
		node->left = temp2->right;
		temp2->left = temp1;
		temp2->right = node;
		return temp2;
	}
}

LPNode addNode(LPNode root, LPNode node) {
	LPNode temp;
	int diff, dl, dr;
	if (root == NULL) {
		return node;
	}
	if (node == NULL) {
		return root;
	}
	if (node->value <= root->value) {
		root->left = addNode(root->left, node);
	} else {
		root->right = addNode(root->right, node);
	}
	dl = nodeDepth(root->left);
	dr = nodeDepth(root->right);
	diff = dl - dr;
	if (diff < -1) {
		root = rotateR(root);
	} else if (diff > 1) {
		root = rotateL(root);
	}
	return root;
}