#include <iostream>

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* root = new Node();
    root->data = value;
    root->left = nullptr;
    root->right = nullptr;
    root->height = 1;
    return(root);
  }

  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->right) - height(N->left);
  }

  Node* BalanceTree(Node* root) {
  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* root, int key) { 
  if (root == nullptr) {
        Node* node = new Node;
        node->data = key;
        node->height = 1;
        node->left = nullptr;
        node->right = nullptr;
        return node;
    }

  if (key < root->data) {
    root->left = Insert(root->left, key);
  } else if (key > root->data) {
    root->right = Insert(root->right, key);
  } else {
    return root;
  }

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

  return BalanceTree(root);
}

Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left != nullptr)
        current = current->left;
    return current;
}

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

  if (key < root->data) {
    root->left = Delete(root->left, key);
  } else if (key > root->data) {
    root->right = Delete(root->right, key);
  } 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;
}

  bool Exists(Node* root, int key) {
    if (root == nullptr) return false;
    
    if (root->data == key) {
      return true;
    }
    else if (root->data > key) {
      return Exists(root->left, key);
    }
    else {
      return Exists(root->right, key);
    }
  }
};

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.top == nullptr? 0 : tree.Balance(tree.top));
      if (i < n - 1) {
        std::cout << '\n';
      }
    } else if (cmd == 'D') {
      int x;
      std::cin >> x;
      tree.top = tree.Delete(tree.top, x);
      std::cout << (tree.top == nullptr? 0 : tree.Balance(tree.top));
      if (i < n - 1) {
        std::cout << '\n';
      }
    } else if (cmd == 'C') {
      int x;
      std::cin >> x;
      tree.Exists(tree.top, x) ? std::cout << 'Y' : std::cout << 'N';
      if (i < n - 1) {
        std::cout << '\n';
      }
    }
  }
}


после выполнения ротаций баланс не всегда корректен(либо высота) исправь