分段错误二叉搜索树

Question

我知道标题相似的问题很少，但是我仔细检查了它们，仍然无法解决我的错误。

这是 BST 实现：

struct node {
    int val;
    node* left;
    node* right;
};

node* createNewNode(int x)
{
    node* nn = new node;
    nn->val = x;
    nn->left  = nullptr;
    nn->right = nullptr;

    return nn;
}

void bstInsert(node* &root, int x)
{
    if(root == nullptr) {
        root = createNewNode(x);
        return;
    }

    if(x < root->val)
    {
        if(root->left == nullptr) {
            root->left = createNewNode(x);
            return;
        } else {
            bstInsert(root->left, x);
        }
    }

    if( x > root->val )
    {
        if(root->right == nullptr) {
            root->right = createNewNode(x);
            return;
        } else {
            bstInsert(root->right, x);
        }
    }
}

这是我的主要内容：


int main() {
    node *root = nullptr;
    for (int i = 0; i < 100000; i++) {
        bstInsert(root, i);
    }
}

如果我尝试插入 10000 个元素，那么一切正常。然而，当我尝试插入 100000 个元素时，我在调试器中得到：

Signal = SIGSEGV (Segmentation fault)

当循环中的I值达到32469时，我错过了什么？

Answer 1

首先，您的二叉搜索树是右偏二叉树，因为新元素将添加为现有树的最右边的子元素。

也就是说，对于每次插入，递归将深入到传递给 bstInsert() 的 i 的值，并且对于 i 的某个大值，最终它运行从 space 中递归，然后崩溃。在这么大的树中使用递归进行插入并不是一个好主意。最好进行迭代实施。

附加：
添加 new 运算符失败的检查。

PS:
在我的系统上，您的代码不会因 100000 元素插入而崩溃 :).

Answer 2

有趣的是，您的代码在 fedora g++ 编译器上对我来说工作得很好。可能是我的编译器将 8 字节分配给整数，而您的编译器可能将 4 字节分配给整数，所以请试试这个并告诉我。

#include <iostream>

struct node {
    long val;
    node* left;
    node* right;
};

node* createNewNode(long x)
{
    node* nn = new node;
    nn->val = x;
    nn->left  = nullptr;
    nn->right = nullptr;

    return nn;
}

void bstInsert(node* &root, long x)
{
    if(root == nullptr) {
        root = createNewNode( x);
        return;
    }

    if(x < root->val)
    {
        if(root->left == nullptr) {
            root->left = createNewNode(x);
            return;
        } else {
            bstInsert(root->left, x);
        }
    }

    if( x > root->val )
    {
        if(root->right == nullptr) {
            root->right = createNewNode(x);
            return;
        } else {
            bstInsert(root->right, x);
        }
    }
}
int main() {
    node *root = nullptr;
    for (long i = 0; i < 100000; i++) {
        bstInsert(root, i);
        std::cout << i << std::endl; // printing output to see the results using short gives overlow.
    }
}

如果这不起作用，因为您的计算机内存没有所需的那么多，可能是您只有不到 785 KB 的 CPU CACHE，因为在运行时程序在缓存中并且可能使用 100000 ~ 785 KB 内存，在这种特定情况下位于缓存中，因为它处于运行时并且尚未对其应用任何管理。

分段错误二叉搜索树

Segmentation fault Binary search Tree

c++

c++11

c++14

c++17