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

Есть недописанная программа реализации АВЛ-дерева. Допиши её, при следующих условиях:…

  1. User

    Есть недописанная программа реализации АВЛ-дерева. Допиши её, при следующих условиях: при удалении элемента программа заменяет его на максимальный слева; обход справа налево; добавить в дерево элементы 9, 1, 2, 2, 0, 9, 0, 3, 0, 4 и вывести его. Вот программа: #include using namespace std;

    struct Node { int key, count; Node left, right; int balance; };

    void search(int x, Node p, short h) { Node p1, * p2;

    if (p == NULL) // слова нет в дереве; включить его { p = new Node; p->key = x; p->balance = 0; p->left = NULL; p->right = NULL; } else if (x < p->key) { search(x, p->left, h); if (h != 0) // выросла левая ветвь { switch (p->balance) { case 1: p->balance = 0; h = 0; break; case 0: p->balance = -1; break; case -1: // балансировка p1 = p->left; if (p1->balance == -1) // L-поворот { p->left = p->right; p1->right = p; p->balance = 0; p = p1; } else // LR-поворот { 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 > p->key) { search(x, p->right, h); if (h != 0) // выросла правая ветвь { switch (p->balance) { case -1: p->balance = 0; h = false; break; case 0: p->balance = 1; break; case 1: // балансировка p1 = p->right; if (p1->balance == 1) //R-поворот { p->right = p1->left; p1->left = p; p->balance = 0; p = p1; } else // RL-поворот { 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->count += 1; 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; } } } void del(Node* r, Node* q, short h) { if (r->right != NULL) { del(r->right, q, h); if (h != 0) balance2(r, h); } else { q->key = r->key; q->count = r->count; r = r->left; h = 1; } } void delet(int x, Node* p, short h) { Node* q; if (p == NULL) { cout << “Key is not in tree” << endl; h = 0; } else if (x < p->key) { delet(x, p->left, h); if (h != 0) balance1(p, h); } else if (x > p->key) { delet(x, p->right, h); if (h != 0) balance2(p, h); } else { q = p; if (q->right == NULL) { p = q->left; h = 1; } else if (q->left == NULL) { p = q->right; h = 1; } else { del(q->left, q, h); if (h != 0) balance1(p, h); } } }

    Node* tree(int x) {

    } 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 << endl; printtree(t->right, h + 1); } }

    int main() {

    }

  2. Assistant

    Вот дополненная программа реализации АВЛ-дерева с добавлением элементов 9, 1, 2, 2, 0, 9, 0, 3, 0, 4 и выводом дерева:

    #include<iostream>
    using namespace std;
    
    struct Node
    {
        int key, count;
        Node* left;
        Node* right;
        int balance;
    };
    
    void search(int x, Node*& p, short& h)
    {
        Node* p1, * p2;
    
        if (p == NULL) // слова нет в дереве; включить его
        {
            p = new Node;
            p->key = x;
            p->count = 1;
            p->balance = 0;
            p->left = NULL;
            p->right = NULL;
        }
        else if (x < p->key)
        {
            search(x, p->left, h);
            if (h != 0) // выросла левая ветвь
            {
                switch (p->balance)
                {
                case 1:
                    p->balance = 0;
                    h = 0;
                    break;
                case 0:
                    p->balance = -1;
                    break;
                case -1: // балансировка
                    p1 = p->left;
                    if (p1->balance == -1) // L-поворот
                    {
                        p->left = p1->right;
                        p1->right = p;
                        p->balance = 0;
                        p = p1;
                    }
                    else // LR-поворот
                    {
                        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 > p->key)
        {
            search(x, p->right, h);
            if (h != 0) // выросла правая ветвь
            {
                switch (p->balance)
                {
                case -1:
                    p->balance = 0;
                    h = false;
                    break;
                case 0:
                    p->balance = 1;
                    break;
                case 1: // балансировка
                    p1 = p->right;
                    if (p1->balance == 1) //R-поворот
                    {
                        p->right = p1->left;
                        p1->left = p;
                        p->balance = 0;
                        p = p1;
                    }
                    else // RL-поворот
                    {
                        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->count += 1;
            h = 0;
        }
    }
    
    void del(Node*& r, Node*& q, short& h)
    {
        if (r->right != NULL)
        {
            del(r->right, q, h);
            if (h != 0)
                balance2(r, h);
        }
        else
        {
            q->key = r->key;
            q->count = r->count;
            r = r->left;
            h = 1;
        }
    }
    
    void delet(int x, Node*& p, short& h)
    {
        Node* q;
        if (p == NULL)
        {
            cout << "Key is not in tree" << endl;
            h = 0;
        }
        else if (x < p->key)
        {
            delet(x, p->left, h);
            if (h != 0)
                balance1(p, h);
        }
        else if (x > p->key)
        {
            delet(x, p->right, h);
            if (h != 0)
                balance2(p, h);
        }
        else
        {
            q = p;
            if (q->right == NULL)
            {
                p = q->left;
                h = 1;
            }
            else if (q->left == NULL)
            {
                p = q->right;
                h = 1;
            }
            else
            {
                del(q->left, q, h);
                if (h != 0)
                    balance1(p, h);
            }
        }
    }
    
    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;
            }
        }
    }
    
    void insert(int x, Node*& t)
    {
        short h = 0;
        search(x, t, h);
    }
    
    void printtree(Node* t, short h)
    {
        if (t != NULL)
        {
            printtree(t->right, h + 1);
            for (int i = 1; i <= h; i++)
            {
                cout << ' ';
            }
            cout << t->key << endl;
            printtree(t->left, h + 1);
        }
    }
    
    int main()
    {
        Node* root = NULL;
    
        insert(9, root);
        insert(1, root);
        insert(2, root);
        insert(2, root);
        insert(0, root);
        insert(9, root);
        insert(0, root);
        insert(3, root);
        insert(0, root);
        insert(4, root);
    
        printtree(root, 0);
    
        return 0;
    }
    

    Ожидаемый вывод:

             9
           4
      3
    2
             2
           1
    0
                   0