Skip to content
The Chat Archive
gpt-3.5-turbo-0125· OpenAI WildChat-4.8M (AI2)

Такая проблема: при удалении корневого элемента с обоими поддеревьями не выполняется…

  1. User

    Такая проблема: при удалении корневого элемента с обоими поддеревьями не выполняется балансировка. Исправь метод delet так, чтобы в этом случае выполнялась балансировка: class Tree { private: int hashTableSize = 10; std::vector readFromFile(const std::string& filename) { std::vector sorts; std::ifstream file(filename);

    if (file.is_open()) { long long int vc; std::string pn; long long int t; int day; int month; int year; char divider = ‘|’;

    while (file >> vc >> divider >> pn >> divider >> t >> divider >> day >> month >> year) { VendorCode vendorcode(vc); ProdName productname(pn); TIN tin(t); Date date(day, month, year);

    sorts.push_back(Sorts(vendorcode, productname, tin, date)); }

    file.close(); } else { std::cerr << “Enable open file” << filename << std::endl; }

    return sorts; } void add(long long int vc, std::string pn, long long int t, int d, int m, int y, Node*& p, bool& h) // поиск и добавление элемента { VendorCode vendorcode(vc); ProdName productname(pn); TIN tin(t); Date date(d, m, y); Sorts s(vendorcode, productname, tin, date); if (p == NULL) // слова нет в дереве; включить его { p = new Node; h = true; p->key = s.productnames.productname; p->ht.changeSize(hashTableSize); p->ht.insertItem(s); p->balance = 0; p->left = NULL; p->right = NULL; } else if (pn < p->key) { add(vc, pn, t, d, m, y, p->left, h); if (h) // выросла левая ветвь { switch (p->balance) { case 1: p->balance = 0; h = false; break; case 0: p->balance = -1; break; case -1: // балансировка Node * p1 = p->left; if (p1->balance == -1) // L-поворот { p->left = p1->right; p1->right = p; p->balance = 0; p = p1; } else // LR-поворот { Node* p2 = p1->right; p1->right = p2->left; p2->left = p1; p->left = p2->right; p2->right = p; if (p2->balance == -1) p->balance = 1; else p->balance = 0; if (p2->balance == 1) p1->balance = -1; else p1->balance = 0; p = p2; } p->balance = 0; h = false; break; } } } else if (pn > p->key) { add(vc, pn, t, d, m, y, p->right, h); if (h == true) // выросла правая ветвь { switch (p->balance) { case -1: p->balance = 0; h = false; break; case 0: p->balance = 1; break; case 1: // балансировка Node * p1 = p->right; if (p1->balance == 1) //R-поворот { p->right = p1->left; p1->left = p; p->balance = 0; p = p1; } else // RL-поворот { Node* p2 = p1->left; p1->left = p2->right; p2->right = p1; p->right = p2->left; p2->left = p; if (p2->balance == 1) p->balance = -1; else p->balance = 0; if (p2->balance == -1) p1->balance = 1; else p1->balance = 0; p = p2; } p->balance = 0; h = false; break; } } } else { p->ht.insertItem(s); h = false; } } void balance1(Node* p, bool& h) { Node* p1, * p2; short b1, b2; if (p == NULL) return; switch (p->balance) { case -1: p->balance = 0; break; case 0: p->balance = 1; h = true; break; case 1: // балансировка p1 = p->right; b1 = p1->balance; if (b1 >= 0) // R-поворот { p->right = p1->left; p1->left = p; if (b1 == 0) { p->balance = 1; p1->balance = -1; h = false; } else { p->balance = 0; p1->balance = 0; } p = p1; } else // RL-поворот { p2 = p1->left; b2 = p2->balance; p1->left = p2->right; p2->right = p1; p->right = p2->left; p2->left = p; if (b2 == 1) p->balance = -1; else p->balance = 0; if (b2 == -1) p1->balance = 1; else p1->balance = 0; p = p2; p2->balance = 0; } } } void balance2(Node* p, bool& h) { Node* p1, * p2; short b1, b2; switch (p->balance) { case 1: p->balance = 0; break; case 0: p->balance = -1; h = true; break; case -1: p1 = p->left; b1 = p1->balance; if (b1 <= 0) // L-поворот { p->left = p1->right; p1->right = p; if (b1 == 0) { p->balance = -1; p1->balance = 1; h = false; } else { p->balance = 0; p1->balance = 0; } p = p1; } else // LR-поворот { p2 = p1->right; b2 = p2->balance; p1->right = p2->left; p2->left = p1; p->left = p2->right; p2->right = p; if (b2 == -1) p->balance = 1; else p->balance = 0; if (b2 == 1) p1->balance = -1; else p1->balance = 0; p = p2; p2->balance = 0; } } }

    void delet(std::string pn, int d, int m, int y, Node*& p, bool& h) { Node* q; if (p == NULL) { h = false; } else if (pn < p->key) { delet(pn, d, m, y, p->left, h); if (h) balance1(p, h); } else if (pn > p->key) { delet(pn, d, m, y, p->right, h); if (h) balance2(p, h); } else { if (p->left == NULL && p->right == NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { delete p; p = NULL; h = true; } } else if (p->left != NULL && p->right == NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { Node* temp = p->left; delete p; p = temp; h = true; } } else if (p->left == NULL && p->right != NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { Node* temp = p->right; delete p; p = temp; h = true; } } else { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { if (p->right == NULL) { Node* temp = p->left; delete p; p = temp; h = true; } else { Node* temp = p->left; Node* parent = p; while (temp->right != NULL) { parent = temp; temp = temp->right; } if (parent != p) parent->right = temp->left; else parent->left = temp->left; p->key = temp->key; p->ht = temp->ht; delete temp; h = true;

    } } } } if (h && p != NULL) { if (p->balance == -2) { if (p->left->balance == 1) balance2(p, h); else balance1(p, h); } else if (p->balance == 2) { if (p->right->balance == -1) balance1(p, h); else balance2(p, h); } } } void walk(Node* t, short hh, std::ofstream& out) // обход дерева справа налево и вывод в файл { if (t != NULL) { walk(t->right, hh + 1, out); t->ht.writeFile(out, t->key); walk(t->left, hh + 1, out); } } void walkconsole(Node* t, short hh) // обход дерева справа налево и вывод в консоль { if (t != NULL) { walkconsole(t->right, hh + 1); t->ht.printTable(t->key); walkconsole(t->left, hh + 1); } } void print(Node* t, short hh) // печать дерева { if (t != NULL) { print(t->right, hh + 1); for (int i = 1; i <= hh; i++) cout << " "; std::cout << t->key << std::endl; print(t->left, hh + 1); } }

    int search(std::string pn, int d, int m, int y, Node*& p, bool& h, int searchsteps) { searchsteps++; if (p == NULL) { std::cout << “Not found.” << std::endl; h = false; return -1; } else if (pn < p->key) { searchsteps++; return search(pn, d, m, y, p->left, h, searchsteps); } else if (pn > p->key) { searchsteps++; return search(pn, d, m, y, p->right, h, searchsteps); } else { searchsteps = p->ht.searchItem(d, m, y, searchsteps); if (searchsteps == -1) std::cout << “Not found.” << std::endl; else std::cout << “Found in " << searchsteps << " steps.” << std::endl; h = false; return searchsteps; } } int getSizeHelper(Node* p) { if (p == NULL) { return 0; } else { return 1 + getSizeHelper(p->left) + getSizeHelper(p->right); } } public: Node* root = NULL; int getSize() { return getSizeHelper(root); } void setHashTableSize(int size) { hashTableSize = size; } Node* findbyname(std::string pn, Node*& p) { Node* q; if (p == NULL) { return nullptr; } else if (pn < p->key) { return findbyname(pn, p->left); } else if (pn > p->key) { return findbyname(pn, p->right); } else { return p; } }

    bool isEmpty() { if (root == NULL) return true; else return false; }

    void addItem(long long int vc, std::string pn, long long int t, int d, int m, int y) { bool pncor = true; for (int i = 0; i < pn.size(); i++) { if (!(pn[i] >= ‘a’ && pn[i] <= ‘z’ || pn[i] == ‘')) { pncor = false; break; } } if (pncor) { bool h = false; add(vc, pn, t, d, m, y, root, h); } else std::cout << “Incorrect key values.” << std::endl; }

    void removeItem(std::string pn, int d, int m, int y) { bool pncor = true; for (int i = 0; i < pn.size(); i++) { if (!(pn[i] >= ‘a’ && pn[i] <= ‘z’ || pn[i] == '’)) { pncor = false; break; } } if (pncor) { bool h = false; delet(pn, d, m, y, root, h); } else std::cout << “Incorrect key values.” << std::endl; }

    int searchItem(std::string pn, int d, int m, int y) { bool pncor = true; for (int i = 0; i < pn.size(); i++) { if (!(pn[i] >= ‘a’ && pn[i] <= ‘z’ || pn[i] == ‘_’)) { pncor = false; break; } } if (pncor) { bool h = false; int searchsteps = 0; searchsteps = search(pn, d, m, y, root, h, searchsteps); // Если не найден, то -1 return searchsteps; } else std::cout << “Incorrect key values.” << std::endl; }

    void printTree() { print(root, 0); std::cout << std::endl; walkconsole(root, 0); }

    void writeFile(std::string file) { std::ofstream out(file); walk(root, 0, out);

    }

    Tree(){} void readFile(const std::string readFile) { std::vector sorts = readFromFile(readFile);

    for (int i = 0; i < sorts.size(); i++) { if (i < sorts.size()) addItem(sorts[i].vendorcodes.vendorcode, sorts[i].productnames.productname, sorts[i].tins.tin, sorts[i].dates.day, sorts[i].dates.month, sorts[i].dates.year); } } };

  2. Assistant

    void delet(std::string pn, int d, int m, int y, Node*& p, bool& h) { Node* q; if (p == NULL) { h = false; } else if (pn < p->key) { delet(pn, d, m, y, p->left, h); if (h) balance1(p, h); } else if (pn > p->key) { delet(pn, d, m, y, p->right, h); if (h) balance2(p, h); } else { if (p->left == NULL && p->right == NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { delete p; p = NULL; h = true; } } else if (p->left != NULL && p->right == NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { Node* temp = p->left; delete p; p = temp; h = true; } } else if (p->left == NULL && p->right != NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { Node* temp = p->right; delete p; p = temp; h = true; } } else { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { if (p->right == NULL) { Node* temp = p->left; delete p; p = temp; h = true; } else { Node* temp = p->left; Node* parent = p; while (temp->right != NULL) { parent = temp; temp = temp->right; } if (parent != p) parent->right = temp->left; else parent->left = temp->left; p->key = temp->key; p->ht = temp->ht; delete temp; h = true;

                }
            }
        }
        if (h && p != NULL)
        {
            if (p->balance == -2)
            {
                if (p->left->balance == 1)
                    balance2(p, h);
                else
                    balance1(p, h);
            }
            else if (p->balance == 2)
            {
                if (p->right->balance == -1)
                    balance1(p, h);
                else
                    balance2(p, h);
            }
        }
    }
    

    }

  3. User

    Не помогло. Ещё раз, вот delet: void delet(std::string pn, int d, int m, int y, Node*& p, bool& h) { Node* q; if (p == NULL) { h = false; } else if (pn < p->key) { delet(pn, d, m, y, p->left, h); if (h) balance1(p, h); } else if (pn > p->key) { delet(pn, d, m, y, p->right, h); if (h) balance2(p, h); } else { if (p->left == NULL && p->right == NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { delete p; p = NULL; h = true; } } else if (p->left != NULL && p->right == NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { Node* temp = p->left; delete p; p = temp; h = true; } } else if (p->left == NULL && p->right != NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { Node* temp = p->right; delete p; p = temp; h = true; } } else { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { if (p->right == NULL) { Node* temp = p->left; delete p; p = temp; h = true; } else { Node* temp = p->left; Node* parent = p; while (temp->right != NULL) { parent = temp; temp = temp->right; } if (parent != p) parent->right = temp->left; else parent->left = temp->left; p->key = temp->key; p->ht = temp->ht; delete temp; h = true;

                    }
                }
            }
        }
        if (h && p != NULL)
        {
            if (p->balance == -2)
            {
                if (p->left->balance == 1)
                    balance2(p, h);
                else
                    balance1(p, h);
            }
            else if (p->balance == 2)
            {
                if (p->right->balance == -1)
                    balance1(p, h);
                else
                    balance2(p, h);
            }
        }
    }
    

    Проблема где-то в этой части: else { Node* temp = p->left; Node* parent = p; while (temp->right != NULL) { parent = temp; temp = temp->right; } if (parent != p) parent->right = temp->left; else parent->left = temp->left; p->key = temp->key; p->ht = temp->ht; delete temp; h = true;

                    }
    
  4. Assistant

    Измените часть кода, где происходит удаление корневого элемента с обоими поддеревьями, следующим образом:

    else
    {
        p->ht.removeItem(d, m, y);
        if (p->right == NULL) {
            Node* temp = p->left;
            delete p;
            p = temp;
            h = true;
        }
        else {
            Node* temp = p->left;
            Node* parent = p;
            while (temp->right != NULL)
            {
                parent = temp;
                temp = temp->right;
            }
            if (parent != p)
                parent->right = temp->left;
            else
                parent->left = temp->left;
            p->key = temp->key;
            p->ht = temp->ht;
            delete temp;
            h = true;
        }
    }
    

    В данном варианте кода, при удалении корневого элемента с обоими поддеревьями, сначала проверяется наличие правого поддерева. Если правого поддерева нет, то просто удаляем корневой элемент и заменяем его левым поддеревом. Иначе производим поиск наибольшего элемента в левом поддереве, заменяем корневой элемент на этот наибольший элемент, соединяем поддеревья и удаляем наибольший элемент.

  5. User

    Ты не понимаешь? Нужна балансировка

  6. Assistant

    Извините за недопонимание. Давайте попробуем изменить участок кода для удаления корневого элемента с обоими поддеревьями с учетом балансировки:

    else
    {
        p->ht.removeItem(d, m, y);
        if (p->right == NULL) {
            Node* temp = p->left;
            delete p;
            p = temp;
            h = true;
        }
        else {
            Node* temp = p->left;
            Node* parent = p;
            while (temp->right != NULL)
            {
                parent = temp;
                temp = temp->right;
            }
            if (parent != p)
                parent->right = temp->left;
            else
                parent->left = temp->left;
            p->key = temp->key;
            p->ht = temp->ht;
            delete temp;
            h = true;
            
            // Балансировка
            if (parent != p)
                balance2(parent, h);
            else
                balance1(parent, h);
        }
    }
    

    Добавленный участок кода после удаления корневого элемента с обоими поддеревьями включает балансировку для родительского узла после завершения удаления элемента. Надеюсь, это поможет в решении проблемы.