#include <iostream>

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

struct AVL {
  Node* top = nullptr;

int height(Node* node) {
    if (node == nullptr)
      return 0;
    return node->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* parent) {
    Node* node = new Node();
    node->data = value;
    node->left = nullptr;
    node->right = nullptr;
    node->parent = parent;
    node->height = 1;
    node->balance = 0;
    return node;
}

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

    x->parent = y->parent;
    
    if (y->parent != nullptr) {
        if (y->parent->left == y) {
            y->parent->left = x;
        } else {
            y->parent->right = x;
        }
    }

    x->right = y;
    y->parent = x;

    y->left = T2;
    if (T2 != nullptr) {
        T2->parent = y;
    }

    Node* temp1 = x;
    while (temp1) {
        UpdateHeightAndBalance(temp1);
        temp1 = temp1->parent;
    }
    Node* temp = y;
    while (temp) {
        UpdateHeightAndBalance(temp);
        temp = temp->parent;
    }

    return x;
}

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

    y->parent = x->parent;

    if (x->parent != nullptr) {
        if (x->parent->left == x) {
            x->parent->left = y;
        } else {
            x->parent->right = y;
        }
    }

    y->left = x;
    x->parent = y;

    x->right = T2;
    if (T2 != nullptr) {
        T2->parent = x;
    }

    Node* temp1 = x;
    while (temp1) {
        UpdateHeightAndBalance(temp1);
        temp1 = temp1->parent;
    }
    Node* temp = y;
    while (temp) {
        UpdateHeightAndBalance(temp);
        temp = temp->parent;
    }
    
    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* node, int key, Node* parent) {
    if (node == nullptr) {
        return newNode(key, parent);
    }

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

    UpdateHeightAndBalance(node);
    return BalanceTree(node);
}


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

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

  if (key < node->data) {
    node->left = Delete(node->left, key);
  } else if (key > node->data) {
    node->right = Delete(node->right, key);
  } else {
    if ((node->left == nullptr) || (node->right == nullptr)) {
      Node* temp = node->left ? node->left : node->right;
      Node* parent = node->parent;

      if (temp != nullptr) {
        temp->parent = parent;
      }

      if (parent) {
        if (parent->left == node) {
          parent->left = temp;
        } else {
          parent->right = temp;
        }
      } else {
        top = temp;
      }

      delete node;
      node = temp;
    } else {
      Node* temp = minValueNode(node->left);
      Node* temp_parent = temp->parent;
      node->data = temp->data;

      if (temp_parent->left == temp) {
        temp_parent->left = temp->right;
        if (temp->right) {
          temp->right->parent = temp_parent;
        }
      }

      if (temp_parent->right == temp) {
        temp_parent->right = temp->right;
        if (temp->right) {
          temp->right->parent = temp_parent;
        }
      }
      delete temp;

    }
  }
   Node* temp = node;
    while (temp) {
        UpdateHeightAndBalance(temp);
        temp = BalanceTree(temp);
        temp = temp->parent;
    }

    return node;
  
}

  bool Exists(Node* node, int key) {
    if (node == nullptr) return false;
    
    if (node->data == key) {
      return true;
    }
    else if (node->data > key) {
      return Exists(node->left, key);
    }
    else {
      return Exists(node->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, nullptr);
      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';
      }
    }
  }
}


сделай так чтобы в дереве слева хранилась большая вершина, справа меньшая, перепиши под это все функции