work3/task4.cpp - develop - novd7/algirithms_sem2

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

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

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

// Проверка свойств красно-чёрного дерева
struct CheckResult {
  bool isValid;           // Можно ли покрасить
  set<int> blackHeights;  // Все возможные чёрные высоты
};

CheckResult checkRedBlack(Node* n, bool parentRed = false) {
  if (!n) {
    // NIL-узел: чёрный, чёрная высота = 0 (не считая сам NIL)
    CheckResult res;
    res.isValid = true;
    res.blackHeights.insert(0);
    return res;
  }

  CheckResult result;
  result.isValid = false;

  // Вариант 1: текущий узел чёрный
  CheckResult leftBlack = checkRedBlack(n->left, false);
  CheckResult rightBlack = checkRedBlack(n->right, false);

  if (leftBlack.isValid && rightBlack.isValid) {
    for (int lh : leftBlack.blackHeights) {
      for (int rh : rightBlack.blackHeights) {
        if (lh == rh) {
          result.blackHeights.insert(lh + 1);  // +1 за текущий чёрный
          result.isValid = true;
        }
      }
    }
  }

  // Вариант 2: текущий узел красный (только если родитель не красный)
  if (!parentRed) {
    CheckResult leftRed = checkRedBlack(n->left, true);
    CheckResult rightRed = checkRedBlack(n->right, true);

    if (leftRed.isValid && rightRed.isValid) {
      for (int lh : leftRed.blackHeights) {
        for (int rh : rightRed.blackHeights) {
          if (lh == rh) {
            result.blackHeights.insert(lh);  // чёрная высота не меняется
            result.isValid = true;
          }
        }
      }
    }
  }

  return result;
}

// Проверка всех свойств красно-чёрного дерева
bool checkAllRedBlackProperties(Node* root) {
  if (!root) return true;

  CheckResult result = checkRedBlack(root, false);
  if (!result.isValid) return false;

  // Свойство 5: корень должен быть чёрным
  bool hasRootBlack = false;
  for (int h : result.blackHeights) {
    if (h > 0) hasRootBlack = true;
  }
  if (!hasRootBlack) return false;

  // Свойство 3: если узел красный, то оба его сына чёрные (проверка в fixErase)
  // Дополнительная проверка для задания 4 - убеждаемся, что при покраске
  // красные узлы имеют чёрных детей

  return true;
}

// Функция для проверки красно-черных свойств на конкретной раскраске
bool checkRedBlackColoring(Node* n, bool parentRed, int& blackHeight,
                           int targetBlackHeight) {
  if (!n) {
    blackHeight = 0;
    return true;
  }

  // Перебираем возможные цвета для текущего узла
  // Чёрный вариант
  int leftBH, rightBH;
  if (checkRedBlackColoring(n->left, false, leftBH, targetBlackHeight) &&
      checkRedBlackColoring(n->right, false, rightBH, targetBlackHeight) &&
      leftBH == rightBH) {
    blackHeight = leftBH + 1;
    if (blackHeight == targetBlackHeight) return true;
  }

  // Красный вариант (только если родитель не красный)
  if (!parentRed) {
    if (checkRedBlackColoring(n->left, true, leftBH, targetBlackHeight) &&
        checkRedBlackColoring(n->right, true, rightBH, targetBlackHeight) &&
        leftBH == rightBH) {
      blackHeight = leftBH;
      if (blackHeight == targetBlackHeight) return true;
    }
  }

  return false;
}

bool canBeRedBlackTree(Node* root) {
  if (!root) return true;

  CheckResult result = checkRedBlack(root, false);
  if (!result.isValid) return false;

  // Проверяем, может ли корень быть чёрным
  for (int h : result.blackHeights) {
    if (h > 0) return true;
  }
  return false;
}

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 << endl;
  printTree(n->left, space);
}

int main() {
  Node* root = nullptr;
  int arr[] = {50, 30, 70, 20, 40, 60, 80};
  // Тест для несбалансированного дерева
  // int arr[] = {50, 30, 20, 10, 5};  // Этот вариант не может быть
  // красно-чёрным

  cout << "Построенное BST:\n";
  for (int v : arr) root = insert(root, v);
  printTree(root);

  if (canBeRedBlackTree(root)) {
    cout << "\nДерево МОЖЕТ быть покрашено как красно-черное\n";
    CheckResult res = checkRedBlack(root, false);
    cout << "Возможные чёрные высоты (кроме NIL): ";
    for (int h : res.blackHeights) {
      if (h > 0) cout << h << " ";
    }
    cout << endl;
  } else {
    cout << "\nДерево НЕ МОЖЕТ быть покрашено как красно-черное\n";
    CheckResult res = checkRedBlack(root, false);
    if (!res.isValid) {
      cout << "Причина: пути имеют разную чёрную высоту\n";
    } else {
      bool hasBlackRoot = false;
      for (int h : res.blackHeights) {
        if (h > 0) hasBlackRoot = true;
      }
      if (!hasBlackRoot) {
        cout << "Причина: корень не может быть чёрным\n";
      } else {
        cout << "Причина: найден красный узел с красным родителем (нарушено "
                "свойство 3)\n";
      }
    }
  }

  return 0;
}