所以说,二叉搜索树的深度是非常影响查找/插入性能的,所以说并不常用,广泛使用的是平衡搜索树。常见的平衡搜索树有 红黑树,B- 树,B+ 树(还有 ACM/OI 大佬们爱的 treap,splay,SBT)等。比如 Java 里的 TreeMap,TreeSet 和 HashMap 中链表的树化都是用红黑树实现的,又比如 InnoDB 的索引存储就是 B+ 树实现的。迭代写法的空间复杂度是 O(1),递归写法由于递归调用时会使用方法栈,而方法栈的深度就是二叉搜索树的深度,所以最坏空间复杂度是 O(n)。