c++ - 展开树的 C++ 实现

Question

所以我是在插入一棵新树后实现 Splay 功能。但是，当我尝试插入多个整数时，它会显示分段错误（核心转储）然后退出。

谁能检查我的问题在哪里？

void SplayTree::splay(Node* node)
{
    if (node == NULL)

        return;
   while (node!=NULL) {
            Node* parent = node->parent;
            if (parent != NULL) {
                if (parent->left == node) {
                    rightRotate(parent);
                } else {
                    leftRotate(parent);
                }
            } else {
                Node* gparent = parent->parent;
                if (parent->left == node && gparent->left == parent) {
                    rightRotate(gparent);
                    rightRotate(node->parent);
                } else if (parent->right == node &&
                        gparent->right == parent) {
                    leftRotate(gparent);
                    leftRotate(node->parent);
                } else if (parent->left == node &&
                        gparent->right == parent) {
                    rightRotate(parent);
                    leftRotate(node->parent);
                } else {
                    leftRotate(parent);
                    rightRotate(node->parent);
                }
            }
        }

}

Answer 1

在第 15 行，您基本上具有以下代码序列：

 if (parent != NULL) {
        ...

  } else {
         Node* gparent = parent->parent;

所以本质上你是在检查是否parent不是NULL，然后如果是NULL你立即尊重它（parent->parent），你基本上是在这样做：

Node* parent = NULL; *parent;

这是UB，很可能会导致段错误。

还有一系列其他的尊重parents，所以我认为你需要重新考虑你的功能是如何工作的。