Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· OpenAIAi2 WildChat-4.8M (AI2)

Напиши программу на языке C+: Реализация класса «set» с использованием сбалансированных…

  1. User

    Напиши программу на языке C+: Реализация класса «set» с использованием сбалансированных деревьев. Запрещено использовать стандартные классы языка C++, включающие в себя название “set”. В реализации должны присутствовать такие методы как: find(), count()

  2. 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 не добавляется и не находится в наборе.