Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· openaiHugging Face Suzhen/CodeChat

Есть программа реализации АВЛ-дерева. Всё работает корректно, кроме удаления корневого…

  1. User

    Есть программа реализации АВЛ-дерева. Всё работает корректно, кроме удаления корневого элемента. Почему? Вот программа: #include #include #include #include using namespace std;

    class ListNode //элемент списка { public: int data; ListNode* prev, * next; public: ListNode(int data) { this->data = data; this->prev = this->next = NULL; } }; class LinkedList //список { public: ListNode* head;

    public: LinkedList() //1.Инициализация { head = NULL; }

    void freeMemory() //2.Освобождение памяти { if (head == NULL) return;

    ListNode* current = head;

    ListNode* nextNode;

    do { nextNode = current->next; delete current; current = nextNode; } while (current != head); head = NULL; }

    void addSorted(int data) //3.Добавление элемента в порядке возрастания { ListNode* newNode = new ListNode(data);

    if (head == NULL) //если список пустой { head = newNode; newNode->next = newNode->prev = newNode; } else if (data < head->data) //если новый элемент меньше головы списка {

    newNode->next = head; newNode->prev = head->prev; head->prev->next = newNode; head->prev = newNode; head = newNode; } else if (data > head->prev->data) //если новый элемент больше хвоста списка { newNode->next = head; newNode->prev = head->prev; head->prev->next = newNode; head->prev = newNode; head->prev = newNode; } else //если новый элемент располагается где-то в середине списка { ListNode* current = head->next;

    while (current != head && current->data < data) //поиск элемента, значение которого больше нового { current = current->next; }

    newNode->next = current; newNode->prev = current->prev; current->prev->next = newNode; current->prev = newNode; } }

    void removeBefore(int data) //4.Удаление элемента перед каждым вхождением заданного { if (head == NULL) { return; }

    if (head->data == data) { ListNode* nodeToRemove = head->prev; nodeToRemove->prev->next = head; head->prev = nodeToRemove->prev; delete nodeToRemove; }

    ListNode* current = head->next;

    while (current != head) { if (current->data == data) { ListNode* nodeToRemove = current->prev; nodeToRemove->prev->next = current; current->prev = nodeToRemove->prev; delete nodeToRemove; }

    current = current->next; } }

    bool search(int data) //5.Поиск заданного элемента по значению { if (head == NULL) return false;

    ListNode* current = head;

    do { if (current->data == data) return true;

    current = current->next; } while (current != head);

    return false; }

    void print() //6.Печать { if (head == NULL) return;

    ListNode* current = head;

    do { cout << current->data << ’ '; current = current->next; } while (current != head);

    cout << endl; }

    LinkedList difference(LinkedList list1, LinkedList list2) //7.Дополнительная операция – разность двух списков { if (head != NULL) { LinkedList result;

    ListNode* current = list1.head;

    do { if (list2.search(current->data) == false) result.addSorted(current->data); current = current->next; } while (current != list1.head); return result; } } };

    struct Key { char f1; int f2; };

    struct Node { Key key; LinkedList list; Node* left; Node* right; int balance; };

    void add(Key x, Node*& p, int linenumber, short h) // поиск и добавление элемента { if (x.f1 != ‘Б’) { return; } else if (p == NULL) // слова нет в дереве; включить его { p = new Node; p->key = x; p->list.addSorted(linenumber); p->balance = 0; p->left = NULL; p->right = NULL; } else if (x.f2 < p->key.f2) { add(x, p->left, linenumber, h); if (h != 0) // выросла левая ветвь { switch (p->balance) { case 1: p->balance = 0; h = 0; 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 = 0; break; } } } else if (x.f2 > p->key.f2) { add(x, p->right, linenumber, h); if (h != 0) // выросла правая ветвь { switch (p->balance) { case -1: p->balance = 0; h = 0; 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 = 0; break; } } } else { p->list.addSorted(linenumber); h = 0; } }

    void balance1(Node* p, short h) { Node* p1, * p2; short b1, b2; switch (p->balance) { case -1: p->balance = 0; break; case 0: p->balance = 1; h = 0; 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 = 0; } 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, short h) { Node* p1, * p2; short b1, b2; switch (p->balance) { case 1: p->balance = 0; break; case 0: p->balance = 0; h = 0; 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 = 0; } 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; } } } Node* del(Node* r, Node* q, short h) { if (r->right != NULL) { r->right = del(r->right, q, h); if (h != 0) balance2(r, h); return r; } else { q->key = r->key; Node* left = r->left; delete r; h = 1; return left; } } void delet(Key x, Node*& p, short h) // удаление элемента, выше вспомогательные подпрограммы { Node* q; if (p == NULL || x.f1 != ‘Б’) { cout << “Key is not in tree” << endl; h = 0; } else if (x.f2 < p->key.f2) { delet(x, p->left, h); if (h != 0) balance1(p, h); } else if (x.f2 > p->key.f2) { delet(x, p->right, h); if (h != 0) balance2(p, h); } else { q = p; if (q->right == NULL) { p = q->left; delete q; h = 1; } else if (q->left == NULL) { p = q->right; delete q; h = 1; } else { del(q->left, q, h); if (h != 0) balance1(p, h); } } }

    void search(Key x, Node*& p, short h) // поиск элемента { Node* q; if (p == NULL || x.f1 != ‘Б’) { cout << “В дереве нет такого элемента” << endl; h = 0; } else if (x.f2 < p->key.f2) { search(x, p->left, h); } else if (x.f2 > p->key.f2) { search(x, p->right, h); } else { cout << "Элемент содержится в строке(ах) входного файла "; p->list.print(); } }

    ofstream out(“outdata.txt”); void walktree(Node* t, short h) // обход дерева справа налево и вывод в файл {

    if (t != NULL) { walktree(t->right, h + 1); out << t->key.f1 << t->key.f2 << endl; walktree(t->left, h + 1); } }

    void printtree(Node* t, short h) // печать дерева { if (t != NULL) { printtree(t->left, h + 1); for (int i = 1; i <= h; i++) cout << " "; cout << t->key.f1 << t->key.f2 << endl; printtree(t->right, h + 1); } }

    void deletetree(Node* t, short h) // удаление дерева {

    if (t != NULL) { deletetree(t->right, h + 1); delete t; deletetree(t->left, h + 1); } }

    ifstream in(“data.txt”); void initialize(Node*& p) { Key key;

    string line;

    int linenumber = 0; if (in.is_open()) { while (getline(in, line)) { ++linenumber; key.f1 = line[0]; key.f2 = 0; for (int i = 1; i < 5; i++) { key.f2 += (line[i] - ‘0’) * pow(10, 4 - i); } add(key, p, linenumber, 0); } } }

    int main() { setlocale(LC_ALL, “rus”);

    Node* root = NULL;

    initialize(root);

    walktree(root, 0);

    delet({ ‘Б’, 9122 }, root, 0); printtree(root, 0);

    in.close(); out.close(); return 0; }

  2. Assistant

    Проблема возникает в функции delet. Она не корректно обрабатывает случай удаления корневого элемента, когда есть левое и правое поддеревья. Вместо использования функции del, которая корректно удаляет узел, вы делаете простое удаление и замену корня на левое поддерево. Однако это нарушает структуру АВЛ-дерева и может приводить к некорректным результатам.

    Вместо этого, в функции delet, замените следующий код:

    q = p;
    if (q->right == NULL)
    {
    p = q->left;
    delete q;
    h = 1;
    }
    else if (q->left == NULL)
    {
    p = q->right;
    delete q;
    h = 1;
    }
    else
    {
    del(q->left, q, h);
    if (h != 0)
    balance1(p, h);
    }
    

    на следующий код:

    if (p->left == NULL && p->right == NULL) // в случае если у узла нет детей
    {
    delete p;
    p = NULL;
    h = 1;
    }
    else if (p->left != NULL && p->right == NULL) // в случае если у узла есть только левый ребенок
    {
    Node* temp = p->left;
    delete p;
    p = temp;
    h = 1;
    }
    else if (p->left == NULL && p->right != NULL) // в случае если у узла есть только правый ребенок
    {
    Node* temp = p->right;
    delete p;
    p = temp;
    h = 1;
    }
    else // в случае если у узла есть оба ребенка
    {
    p->list.freeMemory(); // освобождаем память заранее, чтобы избежать потери данных
    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->list = temp->list;
    delete temp;
    h = 1;
    }
    

    Этот код заменит корень на самый правый элемент в левом поддереве в случае, если узел имеет и левое и правое поддерево.

  3. User

    Объясним всё после while (temp->right != NULL)

  4. Assistant

    Внутри цикла while мы перебираем правые дети узла temp до тех пор, пока не достигнем самого правого элемента в левом поддереве. Делается это с помощью следующего кода:

    Node* temp = p->left; // начинаем с левого ребенка корня
    Node* parent = p; // запоминаем родителя текущего узла
    
    while (temp->right != NULL)
    {
        parent = temp; // запоминаем текущий узел как родителя
        temp = temp->right; // переходим к правому ребенку
    }
    

    Далее, при удалении этого самого правого элемента, мы обрабатываем несколько случаев:

    1. Если самый правый элемент является прямым ребенком корня (т.е. у него нет правых детей), то мы просто меняем ссылку на его левого ребенка:
    if (parent != p)
        parent->right = temp->left;
    else
        parent->left = temp->left;
    
    1. Если самый правый элемент находится глубже в дереве (у него есть правые дети), то мы также меняем ссылку на его левого ребенка, и затем копируем ключ и список этого элемента в удаляемый узел:
    p->key = temp->key;
    p->list = temp->list;
    

    После этого мы освобождаем память у

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.