node *treeinsert(tree *t, int *key, int *info)
{
	node *y, *x, *newnode;

	x = (node*)malloc(sizeof(node));
	x->red = 1;
	x->info = info;
	x->key = key;

	bstinsert(t, x);

	newnode = x;

	while(x->parent->color == 1)
	{
		if(x->parent == x->parent->parent->left)
		{
			y = x->parent->parent->right;
			if(y->color)
			{
				x->parent->parent->color = 1;
				y->color = 0;
				x->parent->color = 0;
				x = x->parent->parent;
			}
			else
			{
				if(x == x->parent->right)
				{
					x = x->parent;
					leftrotate(tree, x);
				}

				x->parent->color = 0;
				x->parent->parent->color = 1;

				rightrotate(tree, x->parent->parent);
			}
		}
		else
		{
			y = x->parent->parent->left;
			if(y->color)
			{
				x->parent->parent->color = 1;
				y->color = 0;
				x->parent->color = 0;
				x = x->parent->parent;
			}
			else
			{
				if(x == x->parent->left)
				{
					x = x->parent;
					rightrotate(tree, x);
				}

				x->parent->color = 0;
				x->parent->parent->color = 1;

				leftrotate(tree, x->parent->parent);
			}
		}
	}

	t->root->left->red = 0;
	return newnode;
}