#include <iostream>

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

struct AVL {
  Node* top = nullptr;

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

  void UpdateHeightAndBalance(Node* node) {
  if (node == nullptr)
    return;

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

  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;

    UpdateHeightAndBalance(y);
    UpdateHeightAndBalance(x);

    return x;
  }

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

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

    UpdateHeightAndBalance(x);
    UpdateHeightAndBalance(y);

    return y;
  }

Node* BalanceTree(Node* node) {
  if (node == nullptr) return node;

  UpdateHeightAndBalance(node);

  if (node->balance == -2 && node->left->balance != -1) {
      return RightRotation(node);
  } else if (node->balance == -2 && node->left->balance == 1) {
      node->left = LeftRotation(node->left);
      return RightRotation(node);
  } else if (node->balance == 2 && node->right->balance != -1) {
      return LeftRotation(node);
  } else if (node->balance == 2 && node->right->balance == -1) {
      node->right = RightRotation(node->right);
      return LeftRotation(node);
  }

  return node;
}

  Node* Insert(Node* root, int key) {
    if (root == nullptr) {
      Node* newNode = new Node();
      newNode->data = key;
      newNode->height = 1;
      newNode->left = nullptr;
      newNode->right = nullptr;
      newNode->balance = 0;
      return newNode;
    }

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

  UpdateHeightAndBalance(root);

  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;
      }
    } else {
      Node* temp = minValueNode(root->right);
      root->data = temp->data;
      root->right = Delete(root->right, temp->data);
      delete temp;
    }
  }

  if (root == nullptr) return root;

  UpdateHeightAndBalance(root);

  return BalanceTree(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.top->balance);
      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.top->balance);
      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';
      }
    }
  }
}

добавь parent