work3/task2.cpp - develop - novd7/algirithms_sem2

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

struct Node {
  int key, h;  // h - высота узла
  Node *left, *right;
  Node(int val) : key(val), h(1), left(nullptr), right(nullptr) {}
};

int height(Node* n) { return n ? n->h : 0; }

// Обновление высоты узла
void updHeight(Node* n) { n->h = 1 + max(height(n->left), height(n->right)); }

// Баланс-фактор (положительный - правое выше)
int bfactor(Node* n) { return height(n->right) - height(n->left); }

// Правый поворот - используется при левом перекосе (bf = -2)
Node* rotateRight(Node* y) {
  Node* x = y->left;
  Node* t = x->right;  // поддерево, которое переподвешивается
  x->right = y;
  y->left = t;
  updHeight(y);
  updHeight(x);
  return x;
}

// Левый поворот - используется при правом перекосе (bf = +2)
Node* rotateLeft(Node* x) {
  Node* y = x->right;
  Node* t = y->left;
  y->left = x;
  x->right = t;
  updHeight(x);
  updHeight(y);
  return y;
}

// Балансировка узла после вставки/удаления
Node* balance(Node* n) {
  updHeight(n);
  if (bfactor(n) == -2) {      // левый перекос
    if (bfactor(n->left) > 0)  // лево-правый случай
      n->left = rotateLeft(n->left);
    return rotateRight(n);
  }
  if (bfactor(n) == 2) {        // правый перекос
    if (bfactor(n->right) < 0)  // право-левый случай
      n->right = rotateRight(n->right);
    return rotateLeft(n);
  }
  return n;
}

// Вставка (обычная BST + балансировка на выходе)
Node* insert(Node* n, int key) {
  if (!n) return new Node(key);
  if (key < n->key)
    n->left = insert(n->left, key);
  else if (key > n->key)
    n->right = insert(n->right, key);
  else
    return n;  // дубликатов нет
  return balance(n);
}

void printTree(Node* n, int space = 0) {
  if (!n) return;
  space += 5;
  printTree(n->right, space);
  cout << endl;
  for (int i = 5; i < space; i++) cout << " ";
  cout << n->key << "(h=" << n->h << ",bf=" << bfactor(n) << ")\n";
  printTree(n->left, space);
}

void deleteTree(Node* n) {
    if (!n) return;
    deleteTree(n->left);
    deleteTree(n->right);
    delete n;
}

int main() {
  Node* root = nullptr;
  int arr[] = {10, 20, 30, 40, 50, 25, 5, 15, 35, 45};

  for (int v : arr) {
    root = insert(root, v);
    cout << "\nПосле вставки " << v << ":\n";
    printTree(root);
  }
  deleteTree(root);
  return 0;
}