work4/work_4.2/task1.cpp - develop - novd7/algirithms_sem2

work4/work_4.2/task1.cpp
155 строк4 KB
Новиков Владимир
Рабочая тетрадь 4.2
30 май 2026, 14:10
30 май 2026, 14:100a353cb
#include <iostream>
#include <string>
#include <vector>

const int ALPHABET_SIZE = 26;

int charToIndex(char ch) { return ch - 'a'; }

struct TrieNode {
  TrieNode* children[ALPHABET_SIZE];
  bool isEndOfWord;
  int childrenCount;

  TrieNode() : isEndOfWord(false), childrenCount(0) {
    for (int i = 0; i < ALPHABET_SIZE; ++i) {
      children[i] = nullptr;
    }
  }
};

class Trie {
 private:
  TrieNode* root;

  bool isEmptyNode(TrieNode* node) { return node->childrenCount == 0; }

  void deleteHelper(TrieNode* node, const std::string& word, size_t depth,
                    bool& found, bool& canDelete) {
    if (!node || found) return;

    if (depth == word.length()) {
      if (node->isEndOfWord) {
        found = true;
        node->isEndOfWord = false;
        canDelete = isEmptyNode(node);
      }
      return;
    }

    int index = charToIndex(word[depth]);
    bool childFound = false;
    bool childCanDelete = false;
    deleteHelper(node->children[index], word, depth + 1, childFound,
                 childCanDelete);

    if (childFound) {
      found = true;
      if (childCanDelete) {
        delete node->children[index];
        node->children[index] = nullptr;
        node->childrenCount--;
        canDelete = !node->isEndOfWord && isEmptyNode(node);
      } else {
        canDelete = false;
      }
    }
  }

  void deleteTrie(TrieNode* node) {
    if (!node) return;
    for (int i = 0; i < ALPHABET_SIZE; ++i) {
      if (node->children[i]) {
        deleteTrie(node->children[i]);
      }
    }
    delete node;
  }

 public:
  Trie() { root = new TrieNode(); }

  ~Trie() { deleteTrie(root); }

  void insert(const std::string& word) {
    TrieNode* current = root;
    for (char ch : word) {
      int index = charToIndex(ch);
      if (!current->children[index]) {
        current->children[index] = new TrieNode();
        current->childrenCount++;
      }
      current = current->children[index];
    }
    current->isEndOfWord = true;
  }

  bool search(const std::string& word) {
    TrieNode* current = root;
    for (char ch : word) {
      int index = charToIndex(ch);
      if (!current->children[index]) {
        return false;
      }
      current = current->children[index];
    }
    return current && current->isEndOfWord;
  }

  bool startsWith(const std::string& prefix) {
    TrieNode* current = root;
    for (char ch : prefix) {
      int index = charToIndex(ch);
      if (!current->children[index]) {
        return false;
      }
      current = current->children[index];
    }
    return true;
  }

  bool remove(const std::string& word) {
    bool found = false;
    bool canDelete = false;
    deleteHelper(root, word, 0, found, canDelete);
    return found;
  }
};

int main() {
  Trie trie;
  trie.insert("hello");
  trie.insert("helium");
  trie.insert("world");
  trie.insert("cat");
  trie.insert("catdog");

  std::cout << "После вставки:" << std::endl;
  std::cout << "Поиск 'hello': " << trie.search("hello") << std::endl;
  std::cout << "Поиск 'helium': " << trie.search("helium") << std::endl;
  std::cout << "Поиск 'cat': " << trie.search("cat") << std::endl;

  std::cout << "\nУдаляем 'hello':" << std::endl;
  bool removed = trie.remove("hello");
  std::cout << "Результат удаления: " << removed << std::endl;
  std::cout << "Поиск 'hello': " << trie.search("hello") << std::endl;
  std::cout << "Поиск 'helium': " << trie.search("helium") << std::endl;

  std::cout << "\n3. Удаляем 'cat' (имеет общий префикс с 'catdog'):"
            << std::endl;
  removed = trie.remove("cat");
  std::cout << "Результат удаления: " << removed << std::endl;
  std::cout << "Поиск 'cat': " << trie.search("cat") << std::endl;
  std::cout << "Поиск 'catdog': " << trie.search("catdog") << std::endl;

  std::cout << "\nУдаляем несуществующее слово 'test':" << std::endl;
  removed = trie.remove("test");
  std::cout << "Результат удаления: " << removed << std::endl;

  std::cout << "\nПроверка оставшихся слов:" << std::endl;
  std::cout << "Поиск 'helium': " << trie.search("helium") << std::endl;
  std::cout << "Поиск 'catdog': " << trie.search("catdog") << std::endl;
  std::cout << "Поиск 'world': " << trie.search("world") << std::endl;

  return 0;
}