I am writing a function to take a Node* T and int k as parameters, where T is a pointer to the Root node of a Binary Search Tree, and k is the element to insert. The function should, with 1/T->size probability determine if k should be inserted as the new head. If the probability fails, it recursively calls itself using the corresponding subtree. The function is written below:
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;
}
The problem I'm having is when running the function, a Seg Fault occurs at line:
float percent=(1.0/T->size);
Why is this happening? I have an if statement at the beginning to ensure T is not a nullptr, and since its not a nullptr, it should have been constructed such that T->size has a value? Where in this algorithm is this flaw coming from?
Aucun commentaire:
Enregistrer un commentaire