AVL树插入操作调试：重复键引发空指针崩溃问题

问题描述 #

实现支持重复键的AVL树时，avl_tree_insert在特定场景下会因空指针解引用崩溃。随机插入通常能运行数千次，但会突然触发异常终止程序。

崩溃触发条件 #

当以下条件同时满足时会崩溃：

• 待插入的键已存在于树中
• 当前处理的节点（根节点）的left和right子节点初始均为空
• 该节点因插入操作处于不平衡状态（平衡因子>1，需要右旋）
• 待插入的键大于等于该节点左子节点的键（代码逻辑错误触发左旋操作）

此时执行左旋操作时，因左子节点的right子节点为空，导致空指针解引用。

原因分析 #

核心问题出在重复键插入后的平衡逻辑：

1. 重复键被插入到当前节点的左子树（代码中key <= root->key分支）
2. 当插入后当前节点平衡因子>1时，原代码判断key >= root->left->key就尝试对左子节点执行左旋
3. 但重复键是插入到左子节点的左子树，左子节点的right子节点为空，左旋操作直接访问空指针导致崩溃
4. 原逻辑是针对非重复键设计的，重复键的插入位置不符合该判断条件的假设

修复方案 #

1. 修正平衡判断条件 #

将左重场景下的左旋触发条件从key >= root->left->key改为key > root->left->key，仅当插入键大于左子节点键（即插入到左子节点的右子树）时才执行左旋，重复键（等于左子节点键）属于左左型，直接右旋即可。

2. 增加旋转函数的空指针防护 #

在旋转函数中先检查目标子节点是否存在，避免空指针解引用。

修复后的关键代码 #

修改平衡逻辑部分 #

// CASE: Key <= root key (recurse left).
else
{
    if (key == root->key)
    {
        debug_flag = true;
        printf("Keys match: %lld, left key: %lld, right key: %lld\n",
               key,
               (root->left ? root->left->key : -1),
               (root->right ? root->right->key : -1));
    }
    root->left = _avl_tree_insert(tree, root->left, src, key);

    // Rebalance? Y/N
    if (avl_tree_balance_factor(root) > 1)
    {
        // 修正条件：仅当key大于左子节点键时才左旋
        if (key > root->left->key)
        {
            if (debug_flag) printf("Rotate left required.\n");
            root->left = avl_tree_rotate_left(root->left);
        }
        root = avl_tree_rotate_right(root);
    }
}

修改旋转函数增加防护 #

node_t*
avl_tree_rotate_left
(   node_t* root
)
{
    // Rotate left.
    if (!root || !root->right)
    {
        printf("Rotate left skipped: invalid node or right child missing on append #%llu, key: %lld.\n",
               op_count, root ? root->key : -1);
        return root; // 返回原节点避免崩溃
    }
    node_t* right = root->right;
    root->right = right->left;
    right->left = root;

    // Update depth.
    root->depth = avl_tree_recompute_depth(root);
    right->depth = avl_tree_recompute_depth(right);

    return right;
}

node_t*
avl_tree_rotate_right
(   node_t* root
)
{
    // Rotate right.
    if (!root || !root->left)
    {
        printf("Rotate right skipped: invalid node or left child missing on append #%llu, key: %lld.\n",
               op_count, root ? root->key : -1);
        return root; // 返回原节点避免崩溃
    }
    node_t* left = root->left;
    root->left = left->right;
    left->right = root;

    // Update depth.
    root->depth = avl_tree_recompute_depth(root);
    left->depth = avl_tree_recompute_depth(left);

    return left;
}

验证结果 #

修复后运行测试代码，不会再出现空指针崩溃，重复键插入能正常处理，AVL树的平衡状态得以维持。

示例输出（修复后） #

Keys match: 2214, left key: -1, right key: -1
Keys match: 5145, left key: -1, right key: -1
...
Num elements in tree: 1000000

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