Напиши программу на языке C+: Реализация класса «set» с использованием сбалансированных…
- User
Напиши программу на языке C+: Реализация класса «set» с использованием сбалансированных деревьев. Запрещено использовать стандартные классы языка C++, включающие в себя название “set”. В реализации должны присутствовать такие методы как: find(), count()
- Assistant
Вот пример реализации класса "set" с использованием сбалансированных деревьев:
#include <iostream> class Set { private: struct Node { int data; Node* left; Node* right; int height; Node(int value) : data(value), left(nullptr), right(nullptr), height(1) {} }; Node* root; int getHeight(Node* node) { if (node == nullptr) return 0; return node->height; } int getBalanceFactor(Node* node) { if (node == nullptr) return 0; return getHeight(node->left) - getHeight(node->right); } Node* rotateRight(Node* node) { Node* newRoot = node->left; Node* tree = newRoot->right; newRoot->right = node; node->left = tree; node->height = std::max(getHeight(node->left), getHeight(node->right)) + 1; newRoot->height = std::max(getHeight(newRoot->left), getHeight(newRoot->right)) + 1; return newRoot; } Node* rotateLeft(Node* node) { Node* newRoot = node->right; Node* tree = newRoot->left; newRoot->left = node; node->right = tree; node->height = std::max(getHeight(node->left), getHeight(node->right)) + 1; newRoot->height = std::max(getHeight(newRoot->left), getHeight(newRoot->right)) + 1; return newRoot; } Node* insertNode(Node* node, int value) { if (node == nullptr) return new Node(value); if (value < node->data) node->left = insertNode(node->left, value); else if (value > node->data) node->right = insertNode(node->right, value); else return node; node->height = 1 + std::max(getHeight(node->left), getHeight(node->right)); int balanceFactor = getBalanceFactor(node); if (balanceFactor > 1 && value < node->left->data) return rotateRight(node); if (balanceFactor < -1 && value > node->right->data) return rotateLeft(node); if (balanceFactor > 1 && value > node->left->data) { node->left = rotateLeft(node->left); return rotateRight(node); } if (balanceFactor < -1 && value < node->right->data) { node->right = rotateRight(node->right); return rotateLeft(node); } return node; } Node* findNode(Node* node, int value) { if (node == nullptr || node->data == value) return node; if (value < node->data) return findNode(node->left, value); else return findNode(node->right, value); } int countNodes(Node* node) { if (node == nullptr) return 0; return 1 + countNodes(node->left) + countNodes(node->right); } public: Set() : root(nullptr) {} void insert(int value) { root = insertNode(root, value); } bool find(int value) { Node* foundNode = findNode(root, value); return foundNode != nullptr; } int count() { return countNodes(root); } }; int main() { Set set; set.insert(5); set.insert(10); set.insert(2); set.insert(8); std::cout << "Count: " << set.count() << std::endl; if (set.find(10)) std::cout << "Found" << std::endl; else std::cout << "Not found" << std::endl; if (set.find(7)) std::cout << "Found" << std::endl; else std::cout << "Not found" << std::endl; return 0; }Эта реализация класса "set" использует сбалансированные деревья для хранения уникальных элементов в отсортированном порядке. Метод
insert()позволяет добавить элемент в набор, методfind()проверяет, есть ли элемент в наборе, и методcount()возвращает количество элементов в наборе.Программа выводит количество элементов в наборе и сообщает, найден ли элемент в наборе. В данном примере, элементы 5, 10, 2 и 8 добавляются в набор, и они находятся в наборе. Элемент 7 не добавляется и не находится в наборе.