时间戳

首页 > 解决方案 > AVL比较方法，正确的方法与否？

c - AVL比较方法，正确的方法与否？

问题描述

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

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

这个函数应该在 时返回正值l>r，在 时返回零，在时返回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
}

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

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

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

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

此致

标签： calgorithmperformanceavl-tree

解决方案

一个简单的、无 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

推荐阅读