#include

struct Node {
int data;
int height;
Node* left;
Node* right;
};

struct AVL {
Node* top = nullptr;

int height(Node* root) {
if (root == nullptr)
return 0;
return root->height;
}

Node* newNode(int value) {
Node* node = new Node();
node->data = value;
node->left = nullptr;
node->right = nullptr;
node->height = 1;
return(node);
}

Node* RightRotation(Node* y) {
Node* x = y->left;
Node* T2 = x->right;

x->right = y;
y->left = T2;

y->height = std::max(height(y->left), height(y->right)) + 1;
x->height = std::max(height(x->left), height(x->right)) + 1;

return x;
}

Node* LeftRotation(Node* x) {
Node* y = x->right;
Node* T2 = y->left;

y->left = x;
x->right = T2;

x->height = std::max(height(x->left), height(x->right)) + 1;
y->height = std::max(height(y->left), height(y->right)) + 1;

return y;
}

int Balance(Node* N) {
if (N == nullptr)
return 0;
return height(N->left) - height(N->right);
}


Node* MinValueNode(Node* node) {
Node* current = node;

while (current && current->left != NULL) {
current = current->left;
}
return current;
}

Node* Delete(Node* root, int value) {
if (root == nullptr)
return root;

if (value < root->data)
root->left = Delete(root->left, value);
else if(value > root->data)
root->right = Delete(root->right, value);
else {
if((root->left == nullptr) || (root->right == nullptr)) {
Node* temp = root->left ? root->left : root->right;

if(temp == nullptr) {
temp = root;
root = nullptr;
} else
root = temp;
delete temp;
} else {
Node temp = MinValueNode(root->right);
root->data = temp->data;
root->right = Delete(root->right, temp->data);
}
}

if (root == nullptr)
return root;

root->height = 1 + std::max(height(root->left), height(root->right));
int balance = Balance(root);

if (balance > 1 && Balance(root->left) >= 0)
return RightRotation(root);

if (balance > 1 && Balance(root->left) < 0) {
root->left = LeftRotation(root->left);
return RightRotation(root);
}

if (balance < -1 && Balance(root->right) <= 0)
return LeftRotation(root);

if (balance < -1 && Balance(root->right) > 0) {
root->right = RightRotation(root->right);
return LeftRotation(root);
}

return root;
}

Node Insert(Node* node, int value) {
if (node == nullptr)
return(newNode(value));

if (value < node->data)
node->left = Insert(node->left, value);
else if (value > node->data)
node->right = Insert(node->right, value);
else
return node;

node->height = 1 + std::max(height(node->left), height(node->right));
int balance = Balance(node);

if (balance > 1 && value < node->left->data) {
return RightRotation(node);
} else if (balance < -1 && value > node->right->data) {
return LeftRotation(node);
} else if (balance > 1 && value > node->left->data) {
node->left = LeftRotation(node->left);
return RightRotation(node);
} else if (balance < -1 && value < node->right->data) {
node->right = RightRotation(node->right);
return LeftRotation(node);
}

return node;
}

void Exists(int value) {
Node* current = top;

while (current != nullptr) {
if (value < current->data) {
current = current->left;
} else if (value > current->data) {
current = current->right;
} else {
std::cout << “Y” << ‘\n’;
return;
}
}
std::cout << “N” << ‘\n’;
}

};

int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
char cmd;
AVL tree;
int n;
std::cin >> n;
for (int i = 0; i < n; ++i) {
std::cin >> cmd;
if (cmd == ‘A’) {
int x;
std::cin >> x;
tree.top = tree.Insert(tree.top, x);
std::cout << -tree.Balance(tree.top) << ‘\n’;
} else if (cmd == ‘D’) {
int x;
std::cin >> x;
tree.top = tree.Delete(tree.top, x);
std::cout << -tree.Balance(tree.top) << ‘\n’;
} else if (cmd == ‘C’) {
int x;
std::cin >> x;
tree.Exists(x);
}
}

}

сделай проверку сбалансированности по аналогии с этим кодом
#include <iostream>
#include <vector>

struct Node {
int data;
int left;
int right;
int height;
};

int CalcHeight(int index, Node arr[]) {
if (index == -1) return 0;
if (arr[index].height > 0) return arr[index].height;

arr[index].height = 1 + std::max(CalcHeight(arr[index].left, arr), CalcHeight(arr[index].right, arr));

return arr[index].height;
}

int CalcBalance(int index, Node arr[]) {
if (index == -1) return 0;
return CalcHeight(arr[index].right, arr) - CalcHeight(arr[index].left, arr);
}

int main() {
int n;
int data;
int left;
int right;
std::cin >> n;

Node arr[n];

for (int i = 0; i < n; ++i) {
std::cin >> data >> left >> right;
arr[i].data = data;
arr[i].left = left - 1;
arr[i].right = right - 1;
arr[i].height = 0;
}

for (int i = 0; i < n; ++i) {
arr[i].height = CalcHeight(i, arr);
}

for (int i = 0; i < n; ++i) {
std::cout << CalcBalance(i, arr) << ‘\n’;
}
}