时间戳

首页 > 解决方案 > C++ 分段错误——自平衡树插入

c++ - C++ 分段错误——自平衡树插入

问题描述

我正在尝试解决 Hackerrank ( https://www.hackerrank.com/challenges/self-balancing-tree/problem ) 上的自平衡树问题，并且在最后 3 个测试用例中不断遇到分段错误。我看到以前曾发布过同样的问题，并尝试将相同的方法（检查 nullptr）应用于我的案例，但到目前为止没有成功。以下代码是用 C++ 编写的，如果你们能帮助我，我将不胜感激。谢谢！

/* Node is defined as :
typedef struct node
{
    int val;
    struct node* left;
    struct node* right;
    int ht;
} node; */

node * newNode(int val)
{
    node * newNode = new node;
    
    newNode->val = val;
    newNode->left = nullptr;
    newNode->right = nullptr;
    newNode->ht = 0;
    
    return newNode;
}

int getHeight(node* root)
{
    if(root == nullptr) {
        return -1;
    } else {
        return root->ht;
    }
}

node* rightRotate(node* root)
{
    node* temp = root->left;
    root->left = temp->right;
    temp->right = root;

    root->ht = 1 + max(getHeight(root->left), getHeight(root->right));
    temp->ht = 1 + max(getHeight(temp->left), getHeight(temp->right));

    return temp;
}

node* leftRotate(node* root)
{
    node* temp = root->right;
    root->right = temp->left;
    temp->left = root;

    root->ht = 1 + max(getHeight(root->left), getHeight(root->right));
    temp->ht = 1 + max(getHeight(temp->left), getHeight(temp->right));

    return temp;
}

node * insert(node * root,int val)
{
    if(root == nullptr) {
        root = newNode(val); 
        return root;
    }
    if(val > root->val) {
        root->right = insert(root->right, val);
    }
    else if(val < root->val) {
        root->left = insert(root->left, val);
    }
    else{ return 0; }
    
    root->ht = 1 + max(getHeight(root->left),getHeight(root->right));
  
    int balance = getHeight(root->left) - getHeight(root->right);
    
    if(root->left != nullptr && balance > 1) {//Left subtree disbalanced
        if(val < root->left->val) { 
            //Left-Left case: perform a right rotation on the disb. node
            return rightRotate(root);
        }
        else {
            //Left-Right case: perfom a left rotation on the disb. node left subtree
            //and a right rotation on the disb. node
            root->left = leftRotate(root->left);
            return rightRotate(root);

        }
    }
    if(root->right != nullptr && balance < -1) {//Right subtree disbalanced
        if(val > root->right->val) { 
            //Right-Right case: perform a left rotation on the disb. node
            return leftRotate(root);
        }
        else {
            //Right-Left case: perfom a right rotation on the disb. node right subtree
            //and a left rotation on the disb. node
            root->right = rightRotate(root->left);
            return leftRotate(root);
        }
    }
    return root;
}

编辑：

出于调试目的，我使用了在线 gdb，并在上面的代码中添加了以下遍历方法和 main 函数：

void inOrder(node* root) {
    if(root == NULL) {
        return;
    } else {
        inOrder(root->left);
        cout << root->val << " ";
        inOrder(root->right);
    }
}

int main()
{
    node* root=NULL;

    root=insert(root,2);
    root=insert(root,4);
    root=insert(root,3);
    
    inOrder(root);
    return 0;
}

在尝试按此顺序插入值 2、4 和 3 之后，我们将得到一棵不平衡的树，因为右子树的高度为 1，而左子树的高度为 -1（叶节点为 nullptr）并且平衡因子将小于-1。进一步分析表明，我们有一个 RIGHT-LEFT 情况，因为导致不平衡的节点是不平衡节点（根 2）的右孩子的左孩子。然后，我们必须对不平衡节点的右子节点执行右旋转，然后对不平衡节点本身进行左旋转，树最终应该如下所示：

   3
  / \
 2   4

标签： c++segmentation-faultavl-tree

解决方案

感谢所有试图帮助我解决这个问题的人，事实证明我的愚蠢程度是无限的。我相信我已经弄清楚我做错了什么。这个问题的问题在于检查右子树是否不平衡的部分，如果是，则执行必要的旋转。在下面的代码段上，它应该是

root->right = rightRotate(root->right);

代替

root->right = rightRotate(root->left);

推荐阅读