work3/task5.cpp - develop - novd7/algirithms_sem2

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

enum Color { RED, BLACK };

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

bool isRed(Node* n) { return n && n->color == RED; }
bool isBlack(Node* n) { return !n || n->color == BLACK; }

Node* grandparent(Node* n) { return n->parent ? n->parent->parent : nullptr; }
Node* uncle(Node* n) {
  Node* g = grandparent(n);
  if (!g) return nullptr;
  return (n->parent == g->left) ? g->right : g->left;
}

void rotateLeft(Node*& root, Node* x) {
  if (!x || !x->right) return;
  Node* y = x->right;
  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;
}

void rotateRight(Node*& root, Node* x) {
  if (!x || !x->left) return;
  Node* y = x->left;
  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 fixInsert(Node*& root, Node* n) {
  while (n != root && isRed(n->parent)) {
    Node* parent = n->parent;
    Node* grand = grandparent(n);
    Node* uncleNode = uncle(n);

    if (isRed(uncleNode)) {
      parent->color = BLACK;
      uncleNode->color = BLACK;
      grand->color = RED;
      n = grand;
    } else {
      if (parent == grand->left) {
        if (n == parent->right) {
          rotateLeft(root, parent);
          n = parent;
          parent = n->parent;
        }
        rotateRight(root, grand);
        swap(parent->color, grand->color);
        n = parent;
      } else {
        if (n == parent->left) {
          rotateRight(root, parent);
          n = parent;
          parent = n->parent;
        }
        rotateLeft(root, grand);
        swap(parent->color, grand->color);
        n = parent;
      }
    }
  }
  root->color = BLACK;
}

void insert(Node*& root, int key) {
  Node* newNode = new Node(key);

  if (!root) {
    root = newNode;
    root->color = BLACK;
    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 {
      delete newNode;
      return;
    }
  }

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

  fixInsert(root, newNode);
}

Node* findMin(Node* n) {
  while (n && n->left) n = n->left;
  return n;
}

void transplant(Node*& root, Node* u, Node* v) {
  if (!u) return;
  if (!u->parent)
    root = v;
  else if (u == u->parent->left)
    u->parent->left = v;
  else
    u->parent->right = v;
  if (v) v->parent = u->parent;
}

// ИСПРАВЛЕННАЯ fixErase
void fixErase(Node*& root, Node* x) {
  if (!x) return;

  while (x != root && isBlack(x)) {
    if (x == x->parent->left) {
      Node* brother = x->parent->right;

      if (isRed(brother)) {
        brother->color = BLACK;
        x->parent->color = RED;
        rotateLeft(root, x->parent);
        brother = x->parent->right;
      }

      if (!brother) {
        x = x->parent;
        continue;
      }

      if (isBlack(brother->left) && isBlack(brother->right)) {
        brother->color = RED;
        x = x->parent;
      } else {
        if (isBlack(brother->right)) {
          if (brother->left) brother->left->color = BLACK;
          brother->color = RED;
          rotateRight(root, brother);
          brother = x->parent->right;
        }
        if (brother) {
          brother->color = x->parent->color;
          x->parent->color = BLACK;
          if (brother->right) brother->right->color = BLACK;
          rotateLeft(root, x->parent);
        }
        x = root;
      }
    } else {
      Node* brother = x->parent->left;

      if (isRed(brother)) {
        brother->color = BLACK;
        x->parent->color = RED;
        rotateRight(root, x->parent);
        brother = x->parent->left;
      }

      if (!brother) {
        x = x->parent;
        continue;
      }

      if (isBlack(brother->left) && isBlack(brother->right)) {
        brother->color = RED;
        x = x->parent;
      } else {
        if (isBlack(brother->left)) {
          if (brother->right) brother->right->color = BLACK;
          brother->color = RED;
          rotateLeft(root, brother);
          brother = x->parent->left;
        }
        if (brother) {
          brother->color = x->parent->color;
          x->parent->color = BLACK;
          if (brother->left) brother->left->color = BLACK;
          rotateRight(root, x->parent);
        }
        x = root;
      }
    }
  }
  if (x) x->color = BLACK;
}

void erase(Node*& root, int key) {
  Node* z = root;
  while (z) {
    if (key < z->key)
      z = z->left;
    else if (key > z->key)
      z = z->right;
    else
      break;
  }
  if (!z) return;

  Node* y = z;
  Node* x = nullptr;
  Color yOriginalColor = y->color;

  if (!z->left) {
    x = z->right;
    transplant(root, z, z->right);
  } else if (!z->right) {
    x = z->left;
    transplant(root, z, z->left);
  } else {
    y = findMin(z->right);
    yOriginalColor = y->color;
    x = y->right;
    if (y->parent == z) {
      if (x) x->parent = y;
    } else {
      transplant(root, y, y->right);
      y->right = z->right;
      y->right->parent = y;
    }
    transplant(root, z, y);
    y->left = z->left;
    y->left->parent = y;
    y->color = z->color;
  }
  delete z;

  if (yOriginalColor == BLACK) {
    if (x)
      fixErase(root, x);
    else if (root)
      fixErase(root, root);
  }
}

void inorder(Node* n) {
  if (!n) return;
  inorder(n->left);
  cout << n->key << (n->color == RED ? "R " : "B ");
  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 << (n->color == RED ? "(R)" : "(B)");
  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;
}

int main() {
  Node* root = nullptr;

  cout << "Красно-черное дерево:\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=== Удаление 20 ===\n";
  erase(root, 20);
  printTree(root);
  cout << "Обход: ";
  inorder(root);
  cout << endl;

  cout << "\n=== Удаление 10 ===\n";
  erase(root, 10);
  printTree(root);
  cout << "Обход: ";
  inorder(root);
  cout << endl;

  cout << "\n=== Удаление 30 ===\n";
  erase(root, 30);
  printTree(root);
  cout << "Обход: ";
  inorder(root);
  cout << endl;

  cout << "\n=== Удаление 5 ===\n";
  erase(root, 5);
  printTree(root);
  cout << "Обход: ";
  inorder(root);
  cout << endl;

  deleteTree(root);
  cout << "\nПрограмма завершена успешно!\n";
  return 0;
}