work3/task1.cpp - develop - novd7/algirithms_sem2

work3/task1.cpp
143 строки3 KB
Новиков Владимир
контрольная работа 3
30 апр 2026, 19:48
30 апр 2026, 19:4806305cd
#include <algorithm>
#include <iostream>
using namespace std;

struct Node {
  int key;
  Node* left;
  Node* right;
  int height;  // высота узла

  Node(int val) : key(val), left(nullptr), right(nullptr), height(1) {}
};

// Высота узла
int getHeight(Node* node) { return node ? node->height : 0; }

// Обновление высоты
void updateHeight(Node* node) {
  if (node) {
    node->height = 1 + max(getHeight(node->left), getHeight(node->right));
  }
}

// Баланс-фактор (разница высот левого и правого)
int balanceFactor(Node* node) {
  return node ? getHeight(node->left) - getHeight(node->right) : 0;
}

// Правый поворот
Node* rotateRight(Node* y) {
  Node* x = y->left;
  Node* T2 = x->right;

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

  updateHeight(y);
  updateHeight(x);

  return x;
}

// Левый поворот
Node* rotateLeft(Node* x) {
  Node* y = x->right;
  Node* T2 = y->left;

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

  updateHeight(x);
  updateHeight(y);

  return y;
}

// Вставка с балансировкой
Node* insert(Node* root, int key) {
  if (!root) return new Node(key);

  if (key < root->key)
    root->left = insert(root->left, key);
  else if (key > root->key)
    root->right = insert(root->right, key);
  else
    return root;  // дубликаты не вставляем

  updateHeight(root);

  int balance = balanceFactor(root);

  // LL-случай
  if (balance > 1 && key < root->left->key) return rotateRight(root);

  // RR-случай
  if (balance < -1 && key > root->right->key) return rotateLeft(root);

  // LR-случай
  if (balance > 1 && key > root->left->key) {
    root->left = rotateLeft(root->left);
    return rotateRight(root);
  }

  // RL-случай
  if (balance < -1 && key < root->right->key) {
    root->right = rotateRight(root->right);
    return rotateLeft(root);
  }

  return root;
}

// Симметричный обход (in-order) - выводит в отсортированном порядке
void inorderTraversal(Node* root) {
  if (!root) return;
  inorderTraversal(root->left);
  cout << root->key << " ";
  inorderTraversal(root->right);
}

// Вывод баланс-факторов для всех узлов (прямой обход)
void printBalanceFactors(Node* root) {
  if (!root) return;
  cout << "Узел " << root->key << ": баланс-фактор = " << balanceFactor(root)
       << endl;
  printBalanceFactors(root->left);
  printBalanceFactors(root->right);
}

// Визуальный вывод дерева (для отладки)
void printTree(Node* root, int space = 0) {
  if (!root) return;
  space += 5;
  printTree(root->right, space);
  cout << endl;
  for (int i = 5; i < space; i++) cout << " ";
  cout << root->key << " (высота=" << root->height
       << ", бф=" << balanceFactor(root) << ")" << endl;
  printTree(root->left, space);
}

int main() {
  Node* root = nullptr;
  int arr[] = {30, 20, 40, 10, 25, 35, 50, 5, 15, 22, 28};
  int n = sizeof(arr) / sizeof(arr[0]);

  cout << "Вставка элементов: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
    root = insert(root, arr[i]);
  }

  cout << "\n\nСимметричный обход (отсортированный порядок):\n";
  inorderTraversal(root);

  cout << "\n\nВизуальное представление АВЛ-дерева:\n";
  printTree(root);

  cout << "\nБаланс-факторы всех узлов:\n";
  printBalanceFactors(root);

  return 0;
}