Node<T>* balance(Node<T>* node)
	{
		if (node->bfactor() == 2)
		{
			if (node->right->right->height() < (node->right->left)->height())
				node->right = rotate_right(node->right);
			return rotate_left(node);
		}
		else if (node->bfactor() == -2)
		{
			if ((node->left->left)->height() < (node->left->right)->height())
				node->left = rotate_left(node->left);
			return rotate_right(node);
		}
		return node;
	}

	Node<T>* rotate_right(Node<T>* node)
	{
		++rotate_c;
		Node<T>* p = node->left;
		node->left = p->right;
		if (node->left)
			node->left->parent = node;
		Node<T>* n_parent = node->parent;
		node->parent = p;
		p->parent = n_parent;
		if (n_parent)
		{
			if (n_parent->left == node)
				n_parent->left = p;
			else
				n_parent->right = p;
		}
		p->right = node;
		node->fixheight();
		p->fixheight();
		return p;
	}

Node<T>* rotate_left(Node<T>* node)
	{
		++rotate_c;
		Node<T>* q = node->right;
		node->right = q->left;
		if (node->right)
			node->right->parent = node;
		Node<T>* n_parent = node->parent;
		q->left = node;
		node->parent = q;
		q->parent = n_parent;
		if (n_parent)
		{
			if (n_parent->left == node)
				n_parent->left = q;
			else
				n_parent->right = q;
		}
		node->fixheight();
		q->fixheight();
		return q;
	}