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() //Инициализация { head = NULL; }

    void freeMemory() //Освобождение памяти 
    {
        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) //Добавление элемента в порядке возрастания
    {
        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) //Удаление элемента перед каждым вхождением заданного
    {
        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) //Поиск заданного элемента по значению
    {
        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() //Печать
    {
        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) //Разность двух списков
    {
        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 != 'Б' || x.f2 / 1000 == 0 || x.f2 / 10000 != 0) { 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 != 'Б' || x.f2 / 1000 == 0 || x.f2 / 10000 != 0) { 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 { 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; } } }

    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

    Для исправления программы и реализации балансировки АВЛ-дерева нужно внести следующие изменения:

    1. Добавить функцию updateHeight(Node* p) для обновления высоты узлов дерева:
    void updateHeight(Node* p) {
        int leftHeight = (p->left != NULL) ? getHeight(p->left) : -1;
        int rightHeight = (p->right != NULL) ? getHeight(p->right) : -1;
        p->balance = rightHeight - leftHeight;
    }
    
    1. Добавить функцию getHeight(Node* p) для получения высоты узла:
    int getHeight(Node* p) {
        if (p == NULL)
            return -1;
        return max(getHeight(p->left), getHeight(p->right)) + 1;
    }
    
    1. В функции balance1(Node* p, short h) и balance2(Node* p, short h) добавить вызов функции updateHeight(p) для обновления высоты узлов после балансировки:
    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
    

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