Seminar11

#include <iostream>

struct AVLNode {
  int Key;
  int Height;
  int Count;  // Количество узлов в поддереве с корнем.
  AVLNode* Left;
  AVLNode* Right;

  explicit AVLNode(int key) : Key(key), Height(1), Count(1), Left(nullptr), Right(nullptr) {}
};

int Height(AVLNode* node) {
  return node ? node->Height : 0;
}

// Не забыть сделать FixCount(node) и вызывать в тех же местах, что и FixHeight.
void FixHeight(AVLNode* node) {
  node->Height = std::max(Height(node->Left), Height(node->Right)) + 1;
}

int Balance(AVLNode* node) {
  if (!node) return 0;
  return Height(node->Left) - Height(node->Right);
}

AVLNode* RotateLeft(AVLNode* root) {
  AVLNode* right = root->Right;
  root->Right = root->Right->Left;
  right->Left = root;
  FixHeight(root);
  FixHeight(right);
  return right;
}

void RotateLeft2(AVLNode*& root) {
  AVLNode* right = root->Right;
  root->Right = root->Right->Left;
  right->Left = root;
  root = right;
  FixHeight(root->Left);
  FixHeight(root);
}

void RotateRight(AVLNode*& /*root*/) {}

void FixTree(AVLNode*& node) {
  if (Balance(node) == 2) {

  } else if (Balance(node) == -2) {
    if (Balance(node->Right) == 1) {
      RotateRight(node->Right);
    }
    RotateLeft2(node);
  }
}

void Add(int key, AVLNode*& node) {
  if (!node) {
    node = new AVLNode(key);
    return;
  }
  if (node->Key < key) Add(key, node->Right);
  else Add(key, node->Left);

  FixHeight(node);
  FixTree(node);
}

int Count(AVLNode* node) {
  return node ? node->Count : 0;
}

int Statistics(AVLNode* node, int k) {
  if (Count(node->Left) == k) return node->Key;
  if (Count(node->Left) > k) return Statistics(node->Left, k);
  return Statistics(node->Right, k - Count(node->Left) - 1);
}

int main() {
  AVLNode* root = new AVLNode(5);
  root->Right = new AVLNode(7);
  FixHeight(root);

  std::cout << Height(root) << std::endl;
  std::cout << Balance(root) << std::endl;

  root = RotateLeft(root);
  std::cout << Height(root) << std::endl;
  std::cout << Balance(root) << std::endl;

  root->Right = new AVLNode(10);
  root->Count = 3;

  int k = 2;
  if (root->Count <= k) std::cout << "No stat" << std::endl;
  else std::cout << "Statistics = " << Statistics(root, k) << std::endl;
  return 0;
}