Сегментация Неисправность при попытке воспроизведения узла в дереве Splay

Question

Я работаю над реализацией дерева splay. Вставка работает отлично, но когда я пытаюсь воспроизвести вставленный узел зигзагообразным или зигзагообразным способом, я всегда получаю ошибку сегментации. Вращение влево-вправо, используемое, когда узел, который нужно разбить, не имеет бабушки и дедушки, отлично работает.

Вот код для правостороннего поворота зигзагообразного цвета. Если я это сделаю, например

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

Я получаю бесконечный цикл j и p. Первый параметр вставки - это ключ, второй - ранг (для обхода).

Таким образом, в предыдущем примере, перед тем splaying, дерево будет выглядеть так: г J р

Так как г вставляется в положении 1, тогда J в положении 1, перемещение Z в положение 2, и т. д.

Вот код зигзагообразного кода, который у меня есть для правого поворота.

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 имеет j как один из своих детей.

Answer 1

Похоже, что порядок операций для всех этих изменений ссылок неверен или вам необходимо сохранить некоторые из этих ссылок в локальных переменных перед внесением изменений. Работайте на бумаге.

n->get_parent()->set_parent(n); изменение строки n 's grandparent. После этого звонки в n->get_parent()->get_parent() собираются вернуть n. Это может вызвать появление циклов в вашем дереве.

(я предполагаю, что n->get_parent()>get_parent() типа, с -> предназначенными вместо сравнения.)