Splayツリーのノードを広げようとしたときのセグメンテーションフォルト

Question

私はスプレイツリーの実装に取り​​組んでいます。この挿入は完全に機能しますが、挿入されたノードをジグジグまたはジグザグの方法でスプレーしようとすると、私はいつもセグメンテーション違反を受け取ります。左と右の回転は、分割するノードに祖父母がないときに使用され、完全に機能します。

右下のジグジグ回転のコードは次のとおりです。たとえば、

insert("z", 1); 
insert("j", 1); 
insert("p", 1); 
zigZigRotate(root.get_left().get_left()); 

jとpの無限ループが発生します。 insertの最初のパラメータはキーであり、2番目はランクです（順序トラバーサルの場合）。

したがって、前述の例では、広がりの前に、木は次のようになります。次に Z J P

zは位置1に挿入されているので、位置1でのJ、2を位置決めするZを移動させ、

右回転のジグザグコードです。

if (n == n->get_parent()->get_left()) 
    { 
     if (n->get_right() != nullptr) 
     { 
      n->get_right()->set_parent(n->get_parent()); 
     } 
     if (n->get_parent()->get_right() != nullptr) 
     { 
      n->get_parent()->get_right()->set_parent(n->get_parent()>get_parent()); 
     } 
     n->get_parent()->get_parent()->set_parent(n->get_parent()); 
     n->get_parent()->set_parent(n); 
     n->get_parent()->get_parent()->set_left(n->get_parent()->get_right()); 
     n->get_parent()->set_right(n->get_parent()->get_parent()); 
     n->get_parent()->set_left(n->get_right()); 
     n->set_right(n->get_parent()); 
     n->set_parent(n->get_parent()->get_parent()->get_parent()); 
} 

私はそれを追跡しました。それは私に正しく回転しているようです。無限ループが起こる場所はありません。しかし、それ以来、私は、jとpはどうにかしてはならないやり方で何とか結びついていると思います。このようなjは左の子としてpを持ちますが、pは何らかの理由でその子の1つとしてjを持ちます。

Answer 1

リンクの変更に関する操作の順序が間違っているか、変更を加える前にローカル変数にリンクの一部を保存する必要があるようです。それを紙の上で働かせてください。

n->get_parent()->set_parent(n);行変更nの祖父母。その後、n->get_parent()->get_parent()へのコールはnを返します。これはあなたのツリーにループを引き起こしている可能性があります。

（私はn->get_parent()>get_parent()ではなく、比較の意図->で、タイプであると仮定しています。）