J'écris une fonction qui trouve le nombre total d'éléments dans une arborescence AVL par plage. Par exemple, les arguments transmis sont "ab" et "au", alors je dois savoir combien d'éléments ils se trouvent dans une arborescence AVL dans cette plage.

Actuellement, ma façon de procéder consiste à parcourir l'arbre à chaque fois que le client l'appelle. Mais comme le nombre d'éléments dans mon arbre AVL est très variable, cela prend une éternité si le client appelle cette fonction trop de fois. Existe-t-il un moyen plus rapide de le faire ?

Ma fonction de portée :

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);
}
4
ryanchai_1995 13 févr. 2020 à 23:59

1 réponse

Meilleure réponse

Votre algorithme actuel a une complexité de O(M + log N) où N est la taille de l'arbre et M est le nombre d'éléments dans la plage. Je ne pense pas que vous puissiez faire mieux avec un arbre AVL non augmenté. La solution consisterait donc à modifier l'implémentation de votre arbre.

Un moyen simple de le faire est de stocker dans chaque nœud la taille du sous-arbre à ce nœud. Ces informations peuvent être mises à jour en temps constant lors de la rotation des arbres. Plus tard, il peut être utilisé pour ignorer des sous-arbres entiers comme suit :

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

Cela donnerait une complexité O(log N).

AVIS DE NON-RESPONSABILITÉ : le code n'a pas été testé.

3
Yakov Galka 14 févr. 2020 à 00:10