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

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) 持有的那些值)。