Логическая ошибка при вставке узла в BST

Question

Я написал код вставки узла для BST.Но, похоже, он не работает правильно.Это дает «Ошибка сегментации».Вот моя логика для вставки.

    void insert(Node* root, int data){
     if(root==NULL){
      root= new Node;
      root->data = data;
      }
    else if(data < root->data){
      insert(root->left,data);
      }
    else if(data> root->data){
      insert(root->right,data);
      }
    }

Как это исправить?Спасибо

Редактировать: так что я попробовал кое-что, и этот делает свое дело

    Node* insert(Node* &root, int data){
    if(root==nullptr){
    root = create(data);
    return root;
    }
    else if(data < root->data){
    insert(root->left,data);
    }
    else if(data> root->data){
    insert(root->right,data);
    } 
    }

В чем разница между Node * root и Node * & root?

Answer 1

Ну, если узел не существует (это NULL), вы просто устанавливаете указатель root на new Node, но вам не хватает, чтобы "повесить" его родительский элемент. И, как уже упоминалось, вы можете использовать unique_ptr -s начиная с C++11, чтобы избежать утечек памяти (тогда вы забудете удалить объект). Похоже:

struct Node {
    int data = -1;  // not initialized
    std::unique_ptr<Node> l;
    std::unique_ptr<Node> r;
}

void insert(Node *root, int data) {
    if (root->data == -1) {
        root->data = data;
        return;
    }
    if (data < root->data) {
        if (!root->l) {
            // hanging new left node up
            root->l = std::make_unique<Node>();  // std::make_unique comes since C++14
        }
        insert(root->l.get(),  // getting raw ptr
               data);
    }
    else {
        if (!root->r) {
             // hanging new right node up
             root->r = std::make_unique<Node>();
        }
        insert(root->r.get(), data);
    }
}

Также вас может заинтересовать структура данных, называемая treap , потому что ваша реализация может работать очень долго, если вы вставите, например, увеличивающуюся последовательность:

Node root;

for (int i = 1; i <= 100'000; i++) {
    insert(&root, i);
}

Итак, ваше двоичное дерево в этом случае выглядит так:

1
 \                  
  2                 <=
   \                <= very long path
    3               <=
     \
     ...
       \
     100'000

Treap помогает избежать длинных путей в вашем BST.