随机二叉搜索树中随机发生的段错误

Question

我正在编写一个函数，将 Node* T 和 int k 作为参数，其中 T 是指向二叉搜索树根节点的指针，k 是要插入的元素。该函数应以 1/T->size 概率确定是否应将 k 作为新头插入。如果概率失败，则使用相应的子树递归调用自身。函数写在下面：

    Node *insert_random(Node *T, int k){
    //Random seed
    if(T==nullptr){
        //If 1 element, always make it head
        T=insert(T,k);//This function has been implemented previously, and works fine
    }
    else{
        //Based on size of T, determine odds of making this the head
        float percent=(1.0/T->size);
        int num=(rand()%1000);//Random 1-1000
        //This line basically randomly chooses if the insertion should be the head
        if(num<(int)(1000*percent)){
            Node n(T->key);
            Node* oldHead=&n;
            oldHead->size=T->size;
            oldHead->left=T->left;
            oldHead->right=T->right;
            T->key=k;
            T->size++;
            T->right=nullptr;
            T->left=nullptr;
            if(oldHead->key>k){
                T->right=oldHead;
            }
            else{
                T->left=oldHead;
            }
            return T;
        }
        else{
            //If not chosen to be the head, insert recursively
            T->size++;
            if(k>T->key){
                T->right=insert_random(T->right,k);
            }
            else{
                T->left=insert_random(T->left, k);
            }
        }
    }
    return T;
  // If k is the Nth node inserted into T, then:
  // with probability 1/N, insert k at the root of T
  // otherwise, insert_random k recursively left or right of the root of T
  //Implement Node *insert_random(Node *T, int k)
}
int main(void)
{
    srand(time(0));
    Node* T = nullptr;
    for (int i=0; i<30; i++){
        int r=rand()%100;
        T=insert_random(T, r);
    }
return 0;
}

我遇到的问题是当运行函数时，段错误发生在行：

float percent=(1.0/T->size);

为什么会这样？我在开头有一个 if 语句来确保 T 不是 nullptr，并且由于它不是 nullptr，它应该被构造成 T->size 有一个值？这个算法的缺陷是从哪里来的？

Answer 1

        Node n(T->key); // n is a local object that exists until we return
        Node* oldHead=&n; // oldhead is a pointer to n
        oldHead->size=T->size;
        oldHead->left=T->left;
        oldHead->right=T->right;
        T->key=k;
        T->size++;
        T->right=nullptr;
        T->left=nullptr;
        if(oldHead->key>k){
            T->right=oldHead; // T->right now points to n
        }
        else{
            T->left=oldHead;
        }
        return T; // When we return, t->right doesn't point to anything

这显然是错误的。 T->right此时包含&n。在你 return T; 之后，t->right 仍然指向 n 所在的位置。但是n在这个函数returns之后就不再存在了。因此，当您稍后取消引用 T->right 时，您正在跟踪一个不指向存在的对象的指针。

随机二叉搜索树中随机发生的段错误

Randomly occurring Seg Fault in Randomized Binary Search Tree

c++

binary-search-tree