C++递归实现AVL树插入时维护父指针的问题

我在C++中实现递归式AVL树插入操作时，需要维护父指针（因为手动实现节点旋转必须用到）。目前只能维护根节点和非空节点的父指针，空节点的父指针只能指向自身；如果取消注释代码里的父指针赋值语句，就会触发段错误。

我的代码如下：

AVL::node *AVL::insert(int k, string d, node *&n)
{
    //recursive base  case, I imagine n->parent = n should not be here

    if (n == NULL) {
        n = new node;
        n->left = NULL;
        n->right = NULL;
        n->key = k;
        n->data = d;
        n->height = 1;
        n->parent = n;
        return n;
    }

    if (n->key > k) {
        if (n->left != NULL) {
            n->left->parent = n;
            insert(k, d, n->left);
        } else {
            //n->left->parent = n;
            // this creates SEGFAULT
            insert(k, d, n->left);
        }
    } else if (n->key < k) {
        if (n->right != NULL) {
            n->right->parent = n;
            insert(k, d, n->right);
    } else {
        //n->right->parent = n;
        // this creates SEGFAULT
        insert(k, d, n->right);
    }
  } else {
      return n;
  }

    // insert height management here

    updateHeight(n);
    return n;
}

问题根源 #

触发段错误的核心原因是：当n->left或n->right为NULL时，你试图访问n->left->parent或n->right->parent，这属于对空指针的非法解引用，直接导致内存访问错误。

修正方案 #

不需要在递归前给空的子节点赋值父指针，正确的做法是在递归创建新节点后，通过父节点上下文设置正确的父指针，或者直接在基例中传递父节点参数完成初始化。

方案一：利用递归返回值设置父指针

AVL::node *AVL::insert(int k, string d, node *&n)
{
    if (n == NULL) {
        n = new node;
        n->left = NULL;
        n->right = NULL;
        n->key = k;
        n->data = d;
        n->height = 1;
        n->parent = nullptr; // 初始化父指针为空，后续由上层节点设置
        return n;
    }

    if (n->key > k) {
        AVL::node* child = insert(k, d, n->left);
        // 仅在子节点未设置父指针时赋值，避免重复操作
        if (child->parent == nullptr) {
            child->parent = n;
        }
    } else if (n->key < k) {
        AVL::node* child = insert(k, d, n->right);
        if (child->parent == nullptr) {
            child->parent = n;
        }
    } else {
        // 键已存在，直接返回
        return n;
    }

    updateHeight(n);
    return n;
}

方案二：重载函数传递父节点参数（更简洁）

对外隐藏父节点参数，内部递归时传递当前节点作为子节点的父节点：

// 对外公开的接口
AVL::node *AVL::insert(int k, string d) {
    return insert(k, d, root, nullptr);
}

// 内部递归实现，新增父节点参数
AVL::node *AVL::insert(int k, string d, node *&n, node* parent)
{
    if (n == NULL) {
        n = new node;
        n->left = NULL;
        n->right = NULL;
        n->key = k;
        n->data = d;
        n->height = 1;
        n->parent = parent; // 创建节点时直接设置正确的父指针
        return n;
    }

    if (n->key > k) {
        insert(k, d, n->left, n); // 传递当前节点为左子节点的父节点
    } else if (n->key < k) {
        insert(k, d, n->right, n); // 传递当前节点为右子节点的父节点
    } else {
        return n;
    }

    updateHeight(n);
    return n;
}

额外注意点 #

• 根节点的父指针应设置为nullptr，而非指向自身，这样旋转操作时更容易判断根节点，避免逻辑混乱。
• 原代码中n->parent = n的写法会导致根节点父指针自指，后续旋转时极易引发错误，必须修正。

内容的提问来源于stack exchange，提问作者Sebastien_Van