CODEWITHSUNDEEP
calgorithmperformancebinary-search-treeavl-tree
ryanchai_1995
ryanchai_1995

Reputation: 83

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

I'm writing a function that finds out the total number of items in a AVL tree by range. For example, the arguments that passed in is "ab" and "au", then I need to find out how many items they are in an AVL tree is in that range.

Currently my way of doing this is to traverse the tree every time when the client calls it. But because the number of items in my AVL tree is vary large, it takes forever if the client calls this function too many times. Is there a faster way to do that?

My range function:

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);
}

Upvotes: 4

Views: 232

Answers (1)

Yakov Galka
Yakov Galka

Reputation: 72489

Your current algorithm has a complexity of O(M + log N) where N is the size of the tree and M is the number of elements within the range. I don't think that you can do any better with unaugmented AVL tree. So the solution would involve changing your tree implementation.

A straightforward way to do that is to store in each node the size of the subtree at that node. This information can be updated in constant time during tree rotation. Later it can be used to skip entire sub-trees as follows:

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);
}

This would give an O(log N) complexity.

DISCLAIMER: the code is untested.

Upvotes: 3

Related Questions