Структура дерева - неправильные дети

Question

Я пытаюсь построить простую структуру на C++. Он должен быть похож на дерево AVL.

Все нормально, когда я строю простое дерево с тремя узлами в функции main().

Проблема есть, когда я пытаюсь использовать функцию insert(). Первый аргумент этой функции содержит информацию, в которую помещается значение из второго аргумента.

Вот код:

#include <numeric> 
#include <vector> 
#include <cstdio> 
#include <cstdlib> 
using namespace std; 

struct Node { 
    Node* left; 
    Node* right; 
    Node* parent; 
    int value; 
    int count_leafs; 
    int height; 
}; 

Node* root; 


void insert2(int p, int value, Node* node, int left) 
{ 
    //printf("insert %d %d - (%d, %d) %d \n", p, value, node->left, node->right, left); 

    if (root == NULL) { 
     // creating a tree root 

     Node new_node; 
     new_node.left = NULL; 
     new_node.right = NULL; 
     new_node.parent = NULL; 

     root = &new_node; 

     root->value = value; 
     root->count_leafs = 1; 
     root->height = 1; 
     return; 
    } 

    if (node->left == NULL && node->right == NULL) { 
     // joining value to the leaf 

     Node new_parent; 
     new_parent.count_leafs = 2; 
     new_parent.height = 2; 
     new_parent.value = node->value + value; 
     new_parent.parent = node->parent; 
     new_parent.left = NULL; 
     new_parent.right = NULL; 

     Node new_leaf; 
     new_leaf.value = value; 
     new_leaf.count_leafs = 1; 
     new_leaf.left = NULL; 
     new_leaf.right = NULL; 
     new_leaf.height = 1; 
     new_leaf.parent = &new_parent; 

     new_parent.left = &new_leaf; 
     new_parent.right = node; 


     if (node->parent != NULL && node->parent->left != NULL && node->parent->left == node) { 
      printf("a"); 
      node->parent->left = &new_parent; 
     } 

     if (node->parent != NULL && node->parent->right != NULL && node->parent->right == node) { 
      printf("b"); 
      node->parent->right = &new_parent; 
     } 

     node->parent = &new_parent; 

     return; 
    } 

    //printf("GOTO: %d %d \n", left + node->left->count_leafs, p); 

    node->value += value; 
    node->count_leafs += 1; 

    if (left + node->left->count_leafs + 1 >= p) { 
     //printf("W left\n"); 
     insert2(p, value, node->left, left); 
    } else {  
     //printf("W right\n"); 
     insert2(p, value, node->right, left + node->left->count_leafs); 
    } 
} 


void insert(int p, int value) 
{ 
    insert2(p, value, root, 0); 
} 

int main() 
{ 
    Node new_root; 
    root = NULL; 

    new_root.value = 10; 
    new_root.height = 2; 
    new_root.count_leafs = 2; 
    new_root.parent = NULL; 
    root = &new_root; 

    Node left; 
    left.value = 6; 
    left.height = 1; 
    left.count_leafs = 1; 
    left.parent = root; 
    left.left = NULL; 
    left.right = NULL; 

    Node right; 
    right.value = 4; 
    right.height = 1; 
    right.count_leafs = 1; 
    right.parent = root; 
    right.left = NULL; 
    right.right = NULL; 

    root->left = &left; 
    root->right = &right; 

    // PLACE A 

    insert(0, 1); 

    // PLACE B 

    return 0; 
} 

Как вы видите перед местом строит дерево с 3-мя узлами. Он выглядит в МЕСТЕ А:

10 
/\ 
6 4 

Далее в линии между МЕСТЕ А и В МЕСТЕ, я хочу, чтобы добавить новый узел. После этого (в МЕСТЕ В) дерево должно выглядеть следующим образом:

11 
/\ 
    7 4 
/\ 
1 6 

Но получает что-то вроде этого:

  11 
     /\ 
    1972250912 4 
    /\ 
    2 2 

Я не могу понять, что это неправильно. Это должно быть проблемой в функции insert2(), но я не могу ее найти.

Вы видите это? Заранее благодарим за помощь!

Answer 1

Причиной такого поведения является то, что вы используете переменные области видимости вне области видимости. Вы не должны использовать указатель, который указывает на переменную области видимости из этой области. Сфера действия переменных существует только при условии, что они были объявлены. Если вы решите получить доступ к переменной области видимости вне области действия, вы получите доступ к некоторой части стека, в которой некоторые другие данные будут перезаписаны этой переменной, что приведет к неопределенному поведению.

Я имею в виду, что вы не должны делать так:

if (root == NULL) 
{ 
    Node new_node; 
    root = &new_node; 
    return; 
} 

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

if (root == NULL) 
{ 
    root = new Node; 
    return; 
} 

Но вы должны удалить этот узел позже. Или вы можете использовать интеллектуальные указатели, см. this.

Прочтите this и this для получения дополнительной информации.

Код ниже делает то, что вы ожидали. Однако он не удаляет созданные узлы, которые могут привести к утечке памяти, поэтому этот код необходимо улучшить, но это отдельная проблема.

#include <numeric> 
#include <vector> 
#include <cstdio> 
#include <cstdlib> 
using namespace std; 

struct Node { 
    Node* left; 
    Node* right; 
    Node* parent; 
    int value; 
    int count_leafs; 
    int height; 
}; 

Node* root; 


void insert2(int p, int value, Node* node, int left) 
{ 
    //printf("insert %d %d - (%d, %d) %d \n", p, value, node->left, node->right, left); 

    if (root == NULL) { 
     // creating a tree root 

     Node* new_node = new Node; 
     new_node->left = NULL; 
     new_node->right = NULL; 
     new_node->parent = NULL; 

     root = new_node; 

     root->value = value; 
     root->count_leafs = 1; 
     root->height = 1; 
     return; 
    } 

    if (node->left == NULL && node->right == NULL) { 
     // joining value to the leaf 

     Node* new_parent = new Node; 
     new_parent->count_leafs = 2; 
     new_parent->height = 2; 
     new_parent->value = node->value + value; 
     new_parent->parent = node->parent; 
     new_parent->left = NULL; 
     new_parent->right = NULL; 

     Node* new_leaf = new Node; 
     new_leaf->value = value; 
     new_leaf->count_leafs = 1; 
     new_leaf->left = NULL; 
     new_leaf->right = NULL; 
     new_leaf->height = 1; 
     new_leaf->parent = new_parent; 

     new_parent->left = new_leaf; 
     new_parent->right = node; 


     if (node->parent != NULL && node->parent->left != NULL && node->parent->left == node) { 
      printf("a"); 
      node->parent->left = new_parent; 
     } 

     if (node->parent != NULL && node->parent->right != NULL && node->parent->right == node) { 
      printf("b"); 
      node->parent->right = new_parent; 
     } 

     node->parent = new_parent; 

     return; 
    } 

    //printf("GOTO: %d %d \n", left + node->left->count_leafs, p); 

    node->value += value; 
    node->count_leafs += 1; 

    if (left + node->left->count_leafs + 1 >= p) { 
     //printf("W left\n"); 
     insert2(p, value, node->left, left); 
    } 
    else { 
     //printf("W right\n"); 
     insert2(p, value, node->right, left + node->left->count_leafs); 
    } 
} 


void insert(int p, int value) 
{ 
    insert2(p, value, root, 0); 
} 

int main() 
{ 
    Node new_root; 
    root = NULL; 

    new_root.value = 10; 
    new_root.height = 2; 
    new_root.count_leafs = 2; 
    new_root.parent = NULL; 
    root = &new_root; 

    Node left; 
    left.value = 6; 
    left.height = 1; 
    left.count_leafs = 1; 
    left.parent = root; 
    left.left = NULL; 
    left.right = NULL; 

    Node right; 
    right.value = 4; 
    right.height = 1; 
    right.count_leafs = 1; 
    right.parent = root; 
    right.left = NULL; 
    right.right = NULL; 

    root->left = &left; 
    root->right = &right; 

    // PLACE A 

    insert(0, 1); 

    // PLACE B 

    return 0; 
}