c++ - C++ の左派ヒープをパーコレートすると、セグ フォールトが発生する

Question

removeSelection左派ヒープから特定のノードを削除する関数を実装しました。このコードは、ヒープに挿入されたキーを追跡するハッシュテーブルを介してノードを見つけます。その後、ノードはヒープのルートにパーコレートされ、deleteMinそれを削除するために呼び出されます。swapWithParent呼び出す関数でコードが失敗しているようでpercolateUp、セグ フォールトが生成されます。

これは、ヒープの main から呼び出される関数です。

    bool removeSelection( const Comparable & x )
{
    LeftistNode * temp = locateNode( x ); //find the node with the item
    if(temp == NULL)
        return false;
    //percolate that node to the top
    percolateUp(temp);
    //delete the root
    int derp = 0; //deleteMin requires an int be passed
    deleteMin(derp);
    return true;

}

percolateUp機能:

    void percolateUp( LeftistNode * t )
{
    if(t != NULL)
    {
        while(t != root)
        {
            t = swapWithParent(t->parent, t);
        }
    }
}

swapWithParent機能:

    //swap h2 with its parent h1
//return pointer to h2's new location
LeftistNode * swapWithParent(LeftistNode * h1, LeftistNode * h2)
{
    //if h2 is its parent's left child
    if(h2 == h1->left)
    {
        LeftistNode *temp = new LeftistNode(h2->element, -1, h1->parent, h1->left, h1->right, h1->npl); //clone h1 and store as a temp

        temp->lines = h2->lines;

        //update all pointers
        h1->parent = h2;
        if(h1->right != NULL)
            h1->right->parent = h2;
        h1->left = h2->left;
        h1->right = h2->right;
        h2 = temp;
        return h2;
    }
    else
    {
        LeftistNode *temp = new LeftistNode(h2->element, -1, h1->parent, h1->left, h1->right, h1->npl); //clone h1 and store as a temp
        temp->lines = h2->lines;
        //update all pointers
        h1->parent = h2;
        if(h1->left != NULL)
            h1->left->parent = h2;
        h1->left = h2->left;
        h1->right = h2->right;
        h2 = temp;
        return h2;

    }
}

NULL ポインターを逆参照している可能性のある場所はありますか? 確認しましたが、エラーが見つからないようです。

Answer 1

t->parent呼び出しでがNULLの場合t = swapWithParent(t->parent, t);、でNULLポインタを参照しswapWithParent()ます。NULLが許可されている場合parentは、swapWithParent（）にチェックを追加し、NULLであってはならない場合は、少なくともを追加して、assert()誤ってNULLに設定されていないことを確認します。