work3/task6.cpp - develop - novd7/algirithms_sem2

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

struct Node {
  int key;
  Node *left, *right, *parent;
  Node(int k) : key(k), left(nullptr), right(nullptr), parent(nullptr) {}
};

// Правый поворот
void rotateRight(Node*& root, Node* x) {
  Node* y = x->left;
  if (!y) return;

  x->left = y->right;
  if (y->right) y->right->parent = x;

  y->parent = x->parent;
  if (!x->parent)
    root = y;
  else if (x == x->parent->left)
    x->parent->left = y;
  else
    x->parent->right = y;

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

// Левый поворот
void rotateLeft(Node*& root, Node* x) {
  Node* y = x->right;
  if (!y) return;

  x->right = y->left;
  if (y->left) y->left->parent = x;

  y->parent = x->parent;
  if (!x->parent)
    root = y;
  else if (x == x->parent->left)
    x->parent->left = y;
  else
    x->parent->right = y;

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

// Splay - поднимает узел x в корень
void splay(Node*& root, Node* x) {
  if (!x) return;

  while (x->parent) {
    Node* p = x->parent;
    Node* g = p->parent;

    if (!g) {
      // Zig - один поворот
      if (x == p->left)
        rotateRight(root, p);
      else
        rotateLeft(root, p);
    } else if (x == p->left && p == g->left) {
      // Zig-Zig (лево-лево)
      rotateRight(root, g);
      rotateRight(root, p);
    } else if (x == p->right && p == g->right) {
      // Zig-Zig (право-право)
      rotateLeft(root, g);
      rotateLeft(root, p);
    } else if (x == p->right && p == g->left) {
      // Zig-Zag (лево-право)
      rotateLeft(root, p);
      rotateRight(root, g);
    } else {
      // Zig-Zag (право-лево)
      rotateRight(root, p);
      rotateLeft(root, g);
    }
  }
  root = x;
}

// Поиск максимума в поддереве (без splay)
Node* findMaxNoSplay(Node* n) {
  if (!n) return nullptr;
  while (n->right) n = n->right;
  return n;
}

// Поиск максимума с подъёмом в корень
Node* findMax(Node*& root, Node* n) {
  Node* maxNode = findMaxNoSplay(n);
  if (maxNode) splay(root, maxNode);
  return maxNode;
}

// Поиск узла по ключу (возвращает найденный узел или nullptr)
Node* find(Node*& root, int key) {
  if (!root) return nullptr;

  Node* cur = root;
  Node* last = nullptr;

  while (cur) {
    last = cur;
    if (key < cur->key)
      cur = cur->left;
    else if (key > cur->key)
      cur = cur->right;
    else {
      splay(root, cur);
      return cur;
    }
  }

  if (last) splay(root, last);
  return nullptr;
}

// Вставка
void insert(Node*& root, int key) {
  if (!root) {
    root = new Node(key);
    return;
  }

  Node* cur = root;
  Node* par = nullptr;

  while (cur) {
    par = cur;
    if (key < cur->key)
      cur = cur->left;
    else if (key > cur->key)
      cur = cur->right;
    else {
      // Дубликат - поднимаем существующий узел и выходим
      splay(root, cur);
      return;
    }
  }

  Node* newNode = new Node(key);
  newNode->parent = par;
  if (key < par->key)
    par->left = newNode;
  else
    par->right = newNode;

  splay(root, newNode);
}

// Удаление
void erase(Node*& root, int key) {
  Node* toErase = find(root, key);
  if (!toErase) return;

  Node* leftSub = root->left;
  Node* rightSub = root->right;

  // Обнуляем связи удаляемого узла
  if (leftSub) leftSub->parent = nullptr;
  if (rightSub) rightSub->parent = nullptr;

  delete root;
  root = nullptr;

  // Случай 1: нет левого поддерева
  if (!leftSub) {
    root = rightSub;
    return;
  }

  // Случай 2: нет правого поддерева
  if (!rightSub) {
    root = leftSub;
    return;
  }

  // Случай 3: есть оба поддерева
  // Находим максимум в левом поддереве (он станет новым корнем)
  root = leftSub;
  Node* maxLeft = findMax(root, root);  // maxLeft теперь корень

  // Присоединяем правое поддерево
  maxLeft->right = rightSub;
  rightSub->parent = maxLeft;
}

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

// Визуальный вывод дерева
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;
  if (n->parent) cout << "(p=" << n->parent->key << ")";
  cout << endl;
  printTree(n->left, space);
}

// Освобождение памяти
void deleteTree(Node* n) {
  if (!n) return;
  deleteTree(n->left);
  deleteTree(n->right);
  delete n;
}

// Проверка корректности дерева (для отладки)
bool isBST(Node* n, int minVal = -1e9, int maxVal = 1e9) {
  if (!n) return true;
  if (n->key < minVal || n->key > maxVal) return false;
  return isBST(n->left, minVal, n->key - 1) &&
         isBST(n->right, n->key + 1, maxVal);
}

// Проверка parent-связей
bool checkParents(Node* n, Node* parent = nullptr) {
  if (!n) return true;
  if (n->parent != parent) return false;
  return checkParents(n->left, n) && checkParents(n->right, n);
}

int main() {
  Node* root = nullptr;

  cout << "Splay-дерево\n";

  // Вставка элементов
  int arr[] = {10, 20, 30, 15, 25, 5, 1, 35};
  for (int v : arr) {
    insert(root, v);
    cout << "Вставка " << v << ", корень = " << root->key << endl;
  }

  cout << "\nДерево после вставок:\n";
  printTree(root);

  cout << "\nОбход: ";
  inorder(root);
  cout << endl;

  // Поиск
  cout << "\nПоиск 15:\n";
  find(root, 15);
  cout << "Корень после поиска = " << root->key << endl;
  printTree(root);

  // Удаление
  cout << "\nУдаление 20:\n";
  erase(root, 20);
  if (root) cout << "Новый корень = " << root->key << endl;
  printTree(root);

  cout << "\nУдаление 10:\n";
  erase(root, 10);
  if (root) cout << "Новый корень = " << root->key << endl;
  printTree(root);

  cout << "\nУдаление 1:\n";
  erase(root, 1);
  if (root) cout << "Новый корень = " << root->key << endl;
  printTree(root);

  cout << "\nИтоговый обход: ";
  inorder(root);
  cout << endl;

  deleteTree(root);
  return 0;
}