Как вывести значения в 2-3 дерева в O (log (n) + k) по диапазону? - PullRequest
Новая
       34

Как вывести значения в 2-3 дерева в O (log (n) + k) по диапазону?

0 голосов
/ 18 января 2019

Я пытаюсь написать алгоритм, который будет печатать значения листьев в 2-3 дерева по заданному диапазону ключей.

У меня есть объект узла и объект дерева, который содержит узлы. Дерево представлено левым дочерним правым представлением родного брата.

Алгоритм должен быть в O (log (n) + k) Я написал алгоритм в виде O (n), но не могу придумать, как уменьшить сложность.

например, для дерева, которое включает ключи 1,3,7,6,9,10,13 и значения 2,4,6,12,20,100,217 соответственно для заданного диапазона [7,10] I следует напечатать [6,12,20,100].

Это алгоритм, который я написал до сих пор 

void LCRS_BalancedTree::printHelper(Node *x, const Key *minKey, const Key *maxKey) const {
if (x->getLeftChild() == NULL) {
    if (!(*x->getKey() < *minKey) && !(*maxKey < *x->getKey())) {
        x->getValue()->print();
        return;
    }
} else {
    if (*x->getKey() < *minKey) {
        return;
    }
    printHelper(x->getLeftChild(), minKey, maxKey);
    printHelper(x->getMiddleChild(), minKey, maxKey);

    if (x->getRightChild() != NULL) {
        if (*x->getKey() < *minKey) {
            return;
        }
        printHelper(x->getRightChild(), minKey, maxKey);
    }
}

}

void LCRS_BalancedTree :: Print_Values ​​(const Key * key1, const Key * key2) const {

Node *x = Nroot;

printHelper(x, key1, key2);

}

...