尝试在播放树中展开节点时出现分段错误

-4

我正在实施splay树。插入工作完美，但是当我尝试以锯齿形或锯齿形的方式展现插入的节点时，我总会遇到分段错误。当节点被展开时没有祖父母时使用的左右旋转完美地起作用。尝试在播放树中展开节点时出现分段错误

下面是右右锯齿形旋转的代码。如果我这样做，例如

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

我得到一个无限循环的j和p。插入的第一个参数是关键，第二个参数是排序（为了遍历）。

所以，在前面的例子中，张开之前，树将如下所示： ž Ĵ p

，由于Z被插入在位置1，则j在位置1处，移动Z到位置2，等等

这里是我右旋转的zig-zig代码。

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作为其孩子之一。

来源

2017-02-19 Severage

它看起来像所有这些链接更改的操作顺序不正确，或者您需要在进行更改之前将一些链接存储在本地变量中。通过纸张工作。

n->get_parent()->set_parent(n);行更改n的祖父母。之后，致电n->get_parent()->get_parent()将返回n。这可能会导致树中出现循环。

（我假定n->get_parent()>get_parent()是一种类型的，具有->意图代替的比较。）

来源

2017-02-19 03:03:58 1201ProgramAlarm

感谢。我甚至没有注意到这个错字，而你的其他解释也很合理。 – Severage

尝试在播放树中展开节点时出现分段错误

回答

相关问题