AVL比较法，正确与否？

Question

我正在使用一个小型 AVL 树库，如您所知，您需要为 AVL 树节点定义一个比较方法。库将 AVL 键传递给此方法以对树的元素进行排序。下面是比较方法的语法：

int compare(const void* l, const void* r)
{
}

此函数在 l>r 时应 return 为正值，在 l==r 时应为零，在 l<r 时应为负值，此方法的效率对 AVL的效率。

现在假设 AVL 个树键是 uint32_t。一个简单的方法是使用以下比较函数：

int compare(const void* l, const void* r)
{
    if (*(uint32_t*)l > *(uint32_t*)r)
        return 1;
    if (*(uint32_t*)l < *(uint32_t*)r)
        return -1;
    return 0;
}

但是这种方法的摊销运行时间对于平衡良好的数据来说是一场灾难，因为 跳跃预测在 if 语句 上失败的可能性很高。我通常这样写这个比较：

int compare(const void* l, const void* r)
{
    return *(uint32_t*)l - *(uint32_t*)r;
    // if you want to overcome underflow in subtraction, you can write it like this:
    // return (int64_t)*(uint32_t*)l - (int64_t)*(uint32_t*)r;
    // But this will not solve problem with casting to int for returning result
}

这是一个巨大的效率提升。但是考虑到 return 类型的 int，我想知道从 uint32_t 转换为 int 时是否溢出或减法时下溢（或一般情况下任何其他更大的关键数据大小）可能导致不正确的树结构。如果您的键值最多占用 31 位，则使用此比较方法可以完美地工作。但如果密钥占用 32 位，事情就会变得棘手。例如，查看以下结果：

`l` points to value | `r` points to value | result
--------------------------------------------------
2                   |1                    | 1
2                   |0xFFFFFFFF           | 3

这意味着此比较函数在树的同一侧搜索两个值，而在第一种情况下 l>r 和第二种情况下 l<r 将两个键都视为无符号值。

我想知道当节点确实存在时，使用这种比较方法是否可能不会导致在 AVL 树中找到一个节点。你怎么看？如果这种方法可能找不到节点，那么什么高效的比较方法适合这种情况？

此致

Answer 1

简单、无UB的比较方法如下：

int compare (void* a, void* b)
{
    unsigned int aa = *(unsigned int*)a;
    unsigned int bb = *(unsigned int*)b;
    return (aa > bb) - (aa < bb);
}

在 x86 上，gcc 将它编译成这个相当高效的代码（使用 -O2）：

  mov ecx, DWORD PTR [rdi]
  mov edx, DWORD PTR [rsi]
  xor eax, eax
  cmp ecx, edx
  seta al
  sbb eax, 0
  ret

AVL比较法，正确与否？

AVL comparison method, correct approach or not?

c

algorithm

performance

avl-tree