{"action":"opened","issue":{"url":"https://api.github.com/repos/AnBlsvv/blsvv/issues/1","repository_url":"https://api.github.com/repos/AnBlsvv/blsvv","labels_url":"https://api.github.com/repos/AnBlsvv/blsvv/issues/1/labels{/name}","comments_url":"https://api.github.com/repos/AnBlsvv/blsvv/issues/1/comments","events_url":"https://api.github.com/repos/AnBlsvv/blsvv/issues/1/events","html_url":"https://github.com/AnBlsvv/blsvv/issues/1","id":388260539,"node_id":"MDU6SXNzdWUzODgyNjA1Mzk=","number":1,"title":"AVL tree C ++. Find the error in removing the node","user":{"login":"AnBlsvv","id":45663784,"node_id":"MDQ6VXNlcjQ1NjYzNzg0","avatar_url":"https://avatars0.githubusercontent.com/u/45663784?v=4","gravatar_id":"","url":"https://api.github.com/users/AnBlsvv","html_url":"https://github.com/AnBlsvv","followers_url":"https://api.github.com/users/AnBlsvv/followers","following_url":"https://api.github.com/users/AnBlsvv/following{/other_user}","gists_url":"https://api.github.com/users/AnBlsvv/gists{/gist_id}","starred_url":"https://api.github.com/users/AnBlsvv/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/AnBlsvv/subscriptions","organizations_url":"https://api.github.com/users/AnBlsvv/orgs","repos_url":"https://api.github.com/users/AnBlsvv/repos","events_url":"https://api.github.com/users/AnBlsvv/events{/privacy}","received_events_url":"https://api.github.com/users/AnBlsvv/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-12-06T15:19:37Z","updated_at":"2018-12-06T15:19:37Z","closed_at":null,"author_association":"OWNER","body":"Please help, there is another person’s code, I’m trying to figure it out, I redid it a bit for myself and don’t understand why after removing a node it displays an incorrectly balanced tree\r\n\r\n```\r\n#include<stdio.h>\r\n#include<stdlib.h>\r\n#include<iostream>\r\nusing namespace std;\r\n \r\nstruct avl_st {\r\n    avl_st *left;   // левая ветка\r\n    avl_st *right;  // правая ветка\r\n    int value;      // значение узла\r\n    int balance;    // фактор баланса\r\n    avl_st(int v) :left(0), right(0), balance(0), value(v) {}\r\n};\r\navl_st *root;   // корень дерева\r\nclass AVL_tree {\r\nprivate:\r\n    bool Insert(avl_st **node, int value);  // вставка\r\n    bool Remove(avl_st **node, int value);      //!< удаление (рекурсивная часть)\r\n    bool GetMin(avl_st **root, avl_st **res);   //!< взять минимальный узел (рекурсивная часть)\r\n    avl_st *RotateLR(avl_st*);              // вращение \r\n    avl_st *RotateRL(avl_st*);              // вращение\r\n    int Balance(avl_st**, int);             // балансировка узла\r\n    bool BalanceRemove(avl_st**, bool);             // балансировка узла\r\n \r\npublic:\r\n    AVL_tree()\r\n    {\r\n        root = 0;\r\n    }\r\n    void Insert(int value);     // вставка значения\r\n    void Remove(int value);     //!< удаление значения\r\n    bool Find(int value);       //!< поиск значения\r\n    void display(avl_st *, int);// показать дерево\r\n};\r\n \r\n \r\ninline void AVL_tree::Insert(int value)\r\n{\r\n    Insert(&root, value);\r\n}\r\n \r\ninline void AVL_tree::Remove(int value)\r\n{\r\n    Remove(&root, value);\r\n}\r\n \r\nbool AVL_tree::Find(int value)\r\n{\r\n    avl_st *node = root;\r\n    while (node) {\r\n        if (node->value == value) return true;\r\n        if (node->value>value) node = node->left; else node = node->right;\r\n    }\r\n    return false;\r\n}\r\n \r\nint AVL_tree::Balance(avl_st **root, int res = 0)\r\n{\r\n    avl_st *node = *root;\r\n    if (node->balance>1) {\r\n        if (node->right->balance<0) node->right = RotateLR(node->right);\r\n        *root = RotateRL(node);\r\n        return true;\r\n    }\r\n    if (node->balance<-1) {\r\n        if (node->left->balance>0) node->left = RotateRL(node->left);\r\n        *root = RotateLR(node);\r\n        return true;\r\n    }\r\n    return false;\r\n}\r\n \r\nbool AVL_tree::BalanceRemove(avl_st **root, bool res)\r\n{\r\n    avl_st *node = *root;\r\n    if (node->balance>1) {\r\n        res = !!node->right->balance;\r\n        if (node->right->balance<0) node->right = RotateLR(node->right);\r\n        *root = RotateRL(node);\r\n    }\r\n    if (node->balance<-1) {\r\n        res = !!node->left->balance;\r\n        if (node->left->balance>0) node->left = RotateRL(node->left);\r\n        *root = RotateLR(node);\r\n    }\r\n    return res;\r\n}\r\n \r\nbool AVL_tree::Insert(avl_st **root, int value)\r\n{\r\n    bool res = false;\r\n    avl_st *node = *root;\r\n    if (!node) {\r\n        *root = new avl_st(value);\r\n        return true;\r\n    }\r\n    if (value == node->value) return false;\r\n    if (value<node->value) res = Insert(&node->left, value) && !!--node->balance; //уменьшаем баланс узла\r\n    else                  res = Insert(&node->right, value) && !!++node->balance; //цвеличиваем баланс узла\r\n    if (Balance(root)) res = false; //Если произошел поворот узла - прекращаем\r\n    return res;\r\n}\r\n \r\navl_st *AVL_tree::RotateLR(avl_st *node) //вершина которую нужно повернуть\r\n{\r\n    static const int array[6][4] = {\r\n        //до   после\r\n        -1,-1,+1,+1,// для  \r\n        -1,+0,+1,+0,// вложенного \r\n        -1,+1,+2,+0,// поворота\r\n        -2,-1,+0,+0,// для\r\n        -2,-2,+0,+1,// внешнего\r\n        -2,+0,+1,-1 // поворота\r\n    };\r\n    avl_st *left = node->left;\r\n    avl_st *left_right = left->right;\r\n    left->right = node;\r\n    node->left = left_right;\r\n    for (int n = 0; n<6; n++) \r\n        if (array[n][0] == node->balance && array[n][1] == left->balance) {\r\n        left->balance = array[n][2];\r\n        node->balance = array[n][3];\r\n        break;\r\n    }\r\n    return left; //новая вершина\r\n}\r\n \r\navl_st *AVL_tree::RotateRL(avl_st *node)\r\n{\r\n    static const int array[6][4] = {\r\n        //до   после\r\n        +1,+1,-1,-1,// для  \r\n        +1,-0,-1,-0,// вложенного \r\n        +1,-1,-2,-0,// поворота\r\n        +2,+1,-0,-0,// для\r\n        +2,+2,-0,-1,// внешнего\r\n        +2,-0,-1,+1 // поворота\r\n    };\r\n    avl_st *right = node->right;\r\n    avl_st *right_left = right->left;\r\n    right->left = node;\r\n    node->right = right_left;\r\n    for (int n = 0; n<6; n++) \r\n        if (array[n][0] == node->balance && array[n][1] == right->balance) {\r\n        right->balance = array[n][2];\r\n        node->balance = array[n][3];\r\n        break;\r\n    }\r\n    return right;\r\n}\r\n \r\nbool AVL_tree::GetMin(avl_st **root, avl_st **res)\r\n{\r\n    avl_st *node = *root;\r\n    if (node->left) {\r\n        if (GetMin(&node->left, res) && !++node->balance) return true;\r\n        return Balance(root, false);\r\n    }\r\n    *res = node;\r\n    *root = node->right;\r\n    return true;\r\n}\r\n \r\n \r\nbool AVL_tree::Remove(avl_st **root, int value)\r\n{\r\n    bool ok = false;\r\n    avl_st *node = *root;\r\n    if (!node) return ok;\r\n    if (node->value<value) {\r\n        if (Remove(&node->right, value) && !--node->balance) ok = true;\r\n    }\r\n    else if (node->value>value) {\r\n        if (Remove(&node->left, value) && !++node->balance) ok = true;\r\n    }\r\n    else {                          // нашли вершину кот. надо удалить\r\n        if (!node->right) {             // если есть возможность вырезать сразу, вырезаем\r\n            *root = node->left; \r\n            delete node; \r\n            return true;\r\n        }\r\n        ok = GetMin(&node->right, root);    // находим вершину, которую вставляем на место удалённой\r\n        (*root)->balance = node->balance;       // ставим на место удалённой вершины, нашу замену\r\n        (*root)->left = node->left;\r\n        (*root)->right = node->right;\r\n        delete node;\r\n        if (ok) ok = !--(*root)->balance;\r\n    }\r\n    return BalanceRemove(root, ok);\r\n}\r\n \r\nvoid AVL_tree::display(avl_st *node, int level)\r\n{\r\n    int i;\r\n    if (node != NULL)\r\n    {\r\n        display(node->right, level + 1);\r\n        printf(\"\\n\");\r\n        if (node == root)\r\n            cout << \"Root -> \";\r\n        for (i = 0; i < level && node != root; i++)\r\n            cout << \"        \";\r\n        cout << node->value;\r\n        display(node->left, level + 1);\r\n    }\r\n}\r\n \r\nint main()\r\n{\r\n    AVL_tree tree;\r\n    int n, k;\r\n    cout << \"Vvedite kol-vo \\n\";\r\n    cin >> n;\r\n    for (int i = 0; i<n; i++) {\r\n        cout << \"Vvedite znacheniya \\n\";\r\n        cin >> k;\r\n        tree.Insert(k);\r\n    }\r\n    tree.display(root, 1);\r\n    cout << endl << endl;\r\n    tree.Remove(4);\r\n    tree.display(root, 1);\r\n    cout << endl << endl;\r\n    tree.Find(2);\r\n    return 0;\r\n}\r\n```"}}
{"actor":{"display_login":"AnBlsvv"}}