探 自谦 必胜

这是一个错误的比较函数

int compare (const void *avl_a, const void *avl_b,
                   void *avl_param)
{
    int key_a = ((struct node *)avl_a)->key;
    int key_b = ((struct node *)avl_b)->key;
    return (key_a - key_b);
}

正确的应该为

int compare (const void *avl_a, const void *avl_b,
             void *avl_param)
{
    int key_a = ((struct node *)avl_a)->key;
    int key_b = ((struct node *)avl_b)->key;
    if (key_a > key_b)
        return 1;
    if (key_a < key_b)
        return -1;
    return 0;
}

出错的原因在于二叉树的比较函数必须满足 严格的偏序关系 , 而使用直接相减的不满足其中的传递性, 也就说存在a, b ,c 使得“a < b,b < c ,c < a”.

可以构造一个简单的例子, 假设节点key为32位的int a, b, c 三个节点的的key分别为0, 2^31-1, 2^31. 使用 GNU libavl ,依次插入a, b, c 三个节点, 然后删除a节点, 此时查找c节点则会失败. 如下图所示:

示例代码