二叉搜索树最有效的搜索方法是什么?

Question

我见过很多搜索算法在二叉排序树中搜索，但它们都使用相同的方式:递归。我知道递归与循环相比是昂贵的，因为每次我们调用搜索函数时，都会为该方法创建一个新的堆栈帧，如果二叉搜索树太大，最终会使用大量内存。

为什么我们不能像这样搜索二叉树呢?

while (root!=NULL)
{
    if (root->data==data)
        return 0;
    else if (data > root->data)
        root=root->right;
    else
        root=root->left;
}

我认为这种方式比递归方式更快更有效，如果我错了请纠正我!

Answer 1

可能您的方式-这是在C中编写代码的常见方式-可能更快，但您应该进行基准测试，因为一些C编译器(例如最近的GCC在使用gcc -O2调用时…)能够优化大多数尾部调用作为跳转(并在寄存器中传递值)。尾部调用优化意味着调用堆栈帧被调用方重用(因此调用堆栈保持有界)。请看这个问题

在OCaml(或Scheme，或Haskell，或大多数常见的Lisp实现)中，你会编写一个尾部递归调用，并且你知道编译器将其优化为跳转。

递归并不总是比循环慢(特别是尾部调用)。这是编译器优化的问题。

阅读延续和延续传递风格。如果你只懂C，那就学习一些函数式语言(Ocaml、Haskell或带有SICP的Scheme…)，在这些语言中经常使用尾调用。阅读Scheme中的call/cc

Answer 2

是的，这是正常的做法。

Answer 3

理论上，你的解和递归解具有相同的Big Oh复杂度。理论上它们都是O(log n).如果你想在秒内测量性能，你需要实际一些，编写两种方法的代码(迭代的，递归的)，运行它们并测量运行时间。