Какова сложность алгоритма поиска всех элементов AVL дерева, принадлежащих интервалу?

Question

[Василий Дёмин]

Есть обычное AVL дерево, которое описывается следующей структурой:

typedef struct AvlNode {
    struct AvlNode *parent;
    struct AvlNode *left;
    struct AvlNode *right;
    int8_t         bfactor;
    double         key;
} AvlNode;

typedef struct {
    AvlNode *root;
    size_t  size;
} AvlTree;

Нужно найти все элементы, которые принадлежат интервалу. Есть следующая функция для этого:

void avl_node_print_range(AvlNode *node, double min, double max) {
    if(!is_nil(node->left) && node->key > min)
        avl_node_print_range(node->left, min, max);

    if(node->key >= min && node->key <= max)
        printf("%lf ", node->key);

    if(!is_nil(node->right) && node->key < max)
        avl_node_print_range(node->right, min, max);
}

void avl_print_range(AvlTree *tree, double min, double max) {
    if(is_nil(tree->root))
        return;

    avl_node_print_range(tree->root, min, max);
    fputs("\n", stdout);
}

Мне казалось, что из-за двух рекурсивных вызовов, каждый по n/2 элементов, сложность должна быть O (n). Однако в интернете на нескольких ресурсах сложность данного алгоритма была обозначена, как O(log n + M), где n - размер AVL дерева, а M - количество элементов дерева, попадающих в интервал. Доказательств ни на одном ресурсе не нашёл, а сам для оценки сложности затрудняюсь составить рекуррентное соотношение, потому что будет ли вызвана функция и сколько раз она будет вызвана зависит не от n, а от min и max. Собственно вопрос - какова на самом деле сложность данного алгоритма?

Answer 1

[Wataru]

Оценка O(log n + m) - правильная. Ее нельзя (или очень сложно) вывести рекуррентным соотношением, потому что она сильно завязана на условия в функции. Там 2 рекурсивных вызова, но они происходят не всегда.

Оценку можно вывести посчитав различные вызовы функции. Сначала, когда node->key не в интервале - будет ровно один рекурсивный вызов. Ну, потому что не в интервале, это или <min, или >max. Т.е. одно из двух условий (node->key > min, node->key < max) точно нарушается.

Поэтому сколько-то уровней дерева будет ровно один вызов. Потом будут вызовы в вершины внутри интервала, и могут быть вызовы за границы интервала. Первые все посчитаются в слагаемом M в оценке. Сколько будет вторых? Не более 2*количество уровней - максимум один вызов в числа меньшие min и один в числа, большие max.

Вот мы оказались в какой-то вершине в отрезке (A). И пошли от нее влево в вершину вне отрзка (B). А так же вправо в вершину (C). Так вот, все ключи в поддереве С не меньше A, а значит, ни одна из них не будет "торчать" из отрезка влево. Поэтому, "плохие" вершины вне отрезка слева, которые мы посещаем, там не встретятся никогда. Значит, на следующем уровне может быть максимум одна "плохая" вершина слева - правый ребенок B. И так далее, пока мы не спустимся до вершины опять в отрезке. Аналогичное рассуждение показывает, что может быть только по одной плохой вершины справа на каждом уровне.