我怎么可能更快地搜索排序的二叉树？

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

您的递归方法是一个良好的开端,但它会在不必要时访问(最多)每个节点,因为树已经排序.

在每个阶段,你只需要往下走要么左子树或右子树,根据当前节点是否较小,小于或大于你要找的节点.

所以:

• 当前节点是否匹配？大!你完成了.
• 它太高了吗？向下看左边的子树(其中一切都应该"少")
• 太低了吗？去看看正确的子树(其中一切都应该是"更多")
• 我们选择的子树是空的还是不存在的？嘘!在任何地方都没有比赛.你完成了.

这会将您的算法从线性变为对数,因为每次良好的树搜索都应如此.:)

这就是std::map使用低于比较器来完成其工作的原因.您也可以从中导出相等(对于那些x==y => !(x < y) && !(y < x)保持的值).