如何提高从AVL树中查找范围内项目数的函数的效率？

Question

我正在编写一个函数，该函数可以按范围找出AVL树中的项目总数。例如，传入的参数是“ ab”和“ au”，那么我需要找出它们在该范围内的AVL树中有多少个项目。

目前，我这样做的方法是每次客户端调用它时遍历该树。但是，由于我的AVL树中的项目数量相差很大，因此如果客户端调用此函数的次数过多，则需要花费很多时间。有没有更快的方法呢？

我的范围功能：

void range(AvlTree T, char* k1, char* k2) {
    if ( T == NULL )
        return;

    if ( strcmp(k1, T->Element) < 0 )
        range(T->Left, k1, k2);

    if ( strcmp(k1, T->Element) <= 0 && strcmp(k2, T->Element) >= 0 )
        total++;

    if ( strcmp(k2, T->Element) > 0 )
        range(T->Right, k1, k2);
}

Answer 1

您当前的算法的复杂度为O（M + log N），其中N是树的大小，M是范围内的元素数。我认为使用未增强的AVL树无法做得更好。因此，解决方案将涉及更改树的实现。

一种简单的方法是在每个节点中存储该节点处子树的大小。该信息可以在树旋转期间以恒定的时间更新。稍后，它可以用来跳过整个子树，如下所示：

int range(AvlTree T, const char* k1, const char* k2) {
    assert(!k1 || !k2 || strcmp(k1, k2) <= 0);
    if(T == NULL)
        return 0;
    if(!k1 && !k2)
        return T->size;
    if(k2 && strcmp(k2, T->Element) < 0)
        return range(T->left, k1, k2);
    if(k1 && strcmp(T->Element, k1) < 0)
        return range(T->right, k1, k2);
    return range(T->left, k1, 0) + 1 + range(T->right, 0, k2);
}

这将导致O（log N）复杂性。

免责声明：该代码未经测试。