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

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编译器(例如,当用... 调用时最近的GCCgcc -O2)能够将大多数尾调用优化为跳转(并在寄存器中传递值).尾调用优化意味着调用堆栈帧被被调用者重用(因此调用堆栈保持有界).看到这个问题.

FWIW,OCaml中(或计划,或哈斯克尔,或者最Common Lisp的实现),你会编写一个尾递归调用,你知道,编译器优化它作为一个跳跃.

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

阅读有关延续和继续传递风格的内容.如果你只知道C,那么学习一些函数式语言(Ocaml,Haskell或带有SICP的Scheme ......),经常使用尾调用.阅读Scheme中的call/cc.