我想知道，BST递归插入和BST迭代插入的最大性能是什么？
通过“迭代插入”，您是说类似于指针后面的while循环，在该循环中，递归插入将使用递归调用？
big-O complexity是相同的：在最坏的情况下†，您必须执行log n“下降一级”操作才能到达树中的正确位置。在递归情况下，每个下降操作的instructions的数量确实稍高（创建一个新的堆栈框架并在之后销毁它），但这是被吞咽的一个竞争因素。 （例如O（15n）和O（12n）等效于O（n））
如果编译器像Scheme一样执行尾递归优化，则这两个变量是相同的。众所周知，C编译器有时会执行TCO，但是在进行较小的代码更改时，很容易不会采用这种启发式方法。
†：假设二叉搜索树是平衡的，对于链表的病理情况是O（n）。