mardi 23 mars 2021

Randomly occurring Seg Fault in Randomized Binary Search Tree

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