如何提高从 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) 复杂度。

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

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

How to improve the efficiency of the function that finds the number of items in a range from AVL tree?

c

algorithm

performance

binary-search-tree

avl-tree