Как я могу быстрее найти отсортированное двоичное дерево?

Question

Я пытаюсь вернуться в C ++, так как я не использую его в течение года +.

Я пытаюсь выполнить задания на этом сайте: www.testdome.com

В настоящее времяМоя задача - найти значение в отсортированном бинарном дереве.Класс Node, который я должен использовать, выглядит следующим образом:

class Node
{
public:
    Node(int value, Node* left, Node* right)
    {
        this->value = value;
        this->left = left;
        this->right = right;
    }

    int getValue() const
    {
        return value;
    }

    Node* getLeft() const
    {
        return left;
    }

    Node* getRight() const
    {
        return right;
    }

private:
    int value;
    Node* left;
    Node* right;
};

Я выполнил задание и предложил две реализации.В обоих тестах я получаю сообщение об ошибке: Превышен лимит времени

Я хотел бы знать, как это можно написать быстрее.Мои реализации:

1.Используя std::stack для работы со всеми узлами

Я сохраняю вложенные узлы в std::stack и перебираю их, пока не достигну значения.Я думаю, что это должно быть правильным решением, избегая реальной рекурсии.

bool containsStdStack(const Node& root, int value)
{
    std::stack<const Node*> queue;
    queue.push(&root);

    while(!queue.empty()) {
        const Node*const tmp = queue.top();
        queue.pop();

        if(tmp->getValue() == value) {
            return true;
        }
        // Do not push nulls to avoid extra iterations
        if(const Node* left = tmp->getLeft()) {
            queue.push(left);
        }
        if(const Node* right = tmp->getRight()) {
            queue.push(right);
        }
    }
    return false;
}

2.Наивный рекурсивный подход

Поскольку вышеописанное не прошло тест на производительность, я попробовал этот наивный подход - простые решения часто оказываются быстрее, чем ожидалось.

bool containsRecursive(const Node&root, int value) {
    return containsRecursive(&root, value);
}
bool containsRecursive(const Node*root, int value) {
    return root!=nullptr &&(
        root->getValue() == value
        || containsRecursive(root->getLeft(), value)
        || containsRecursive(root->getRight(), value)
    );
}

Но все равно это не такпройти тест производительности.

Я что-то упустил? А может, тест производительности действительно суров?Можно ли это оптимизировать дальше без хаков?

Answer 1

Я предполагаю, что дерево отсортировано.Сказав это, я просто проверяю, нужно ли искать значение в левой или правой части дерева.Сложность поиска логарифмическая.

bool containsRecursive(const Node&root, int value) {
    return containsRecursive(&root, value);
}
bool containsRecursive(const Node*root, int value) {
    // root is null  
    if (root == NULL) return false;

    // value is present at root 
    if(root->getValue()== value) return true;


    // value is greater than root's value //this saves lot of time
    if (root->getValue() < value) 
       return containsRecursive(root->getRight(), value); 

    // value is smaller than root's key 
    return containsRecursive(root->getLeft(), value); 
}

Answer 2

Ваш рекурсивный подход - хорошее начало, но он посещает (до) каждый узел, когда в этом нет необходимости, учитывая, что дерево отсортировано.

На каждом этапевам нужно только перейти вниз или к левому поддереву или к правому поддереву, в зависимости от того, является ли текущий узел меньшим или большим, чем искомый узел.

Итак:

• Является ли текущий узел совпадающим?Большой!Вы сделали.
• Это слишком высоко?Посмотрите вниз на левое поддерево (в котором все должно быть «меньше»)
• Это слишком низко?Посмотрите вниз на правильное поддерево (в котором все должно быть «больше»)
• Является ли выбранное нами поддерево пустым / несуществующим?Бу!Там нет совпадений нигде.Все готово.

Это меняет ваш алгоритм с линейного на логарифмический, как и должно быть при любом хорошем поиске по дереву.:)

Вот почему std::map использует компаратор меньше, чем для своей работы.Из этого вы также можете получить равенство (для тех значений, для которых выполняется x==y => !(x < y) && !(y < x)).