work3/task3.cpp - develop - novd7/algirithms_sem2

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

struct Node {
  int key, 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); }

Node* rotateRight(Node* y) {
  Node* x = y->left;
  Node* t = x->right;
  x->right = y;
  y->left = t;
  updHeight(y);
  updHeight(x);
  return x;
}

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;
}

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);
}

// Поиск минимального узла (самый левый)
Node* findMin(Node* n) {
  while (n->left) n = n->left;
  return n;
}

// Удаление узла
Node* erase(Node* n, int key) {
  if (!n) return nullptr;

  if (key < n->key) {
    n->left = erase(n->left, key);
  } else if (key > n->key) {
    n->right = erase(n->right, key);
  } else {  // нашли удаляемый узел
    if (!n->left || !n->right) {
      // 0 или 1 потомок
      Node* temp = n->left ? n->left : n->right;
      delete n;
      return temp;
    } else {
      // 2 потомка: заменяем на минимальный из правого поддерева
      Node* minRight = findMin(n->right);
      n->key = minRight->key;
      n->right = erase(n->right, minRight->key);
    }
  }
  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[] = {50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45};

  for (int v : arr) root = insert(root, v);

  cout << "Исходное дерево:\n";
  printTree(root);

  cout << "\nУдаление 20 (узел с двумя потомками):\n";
  root = erase(root, 20);
  printTree(root);

  cout << "\nУдаление 10 (лист):\n";
  root = erase(root, 10);
  printTree(root);

  cout << "\nУдаление 50 (корень):\n";
  root = erase(root, 50);
  printTree(root);

  deleteTree(root);
  return 0;
}