非平衡二叉搜索树中不成功搜索的最佳情况复杂度（大θ表示法）咨询

Best-Case Time Complexity for Unsuccessful Search in an Unbalanced BST #

The best-case time complexity here is Θ(1). Here's why:

• An unsuccessful search in a BST terminates when you reach a null pointer (signaling the target value isn't present in the tree).
• The shortest possible path happens when you check the root node, then immediately hit a null child in the direction the target value would take you. For example:
  • If the root is 15 and has no left child, searching for 10 will compare 10 to 15, attempt to traverse left (which is null), and conclude the value doesn't exist in just one comparison step.
• This scenario is possible no matter how unbalanced the tree is—even if most of the tree is a long chain, as long as the root has at least one missing child (which every non-perfect BST does), this best case applies.
• Since the number of operations is constant (it doesn't grow as the tree size n increases), we express this using big-theta notation as Θ(1).

内容的提问来源于stack exchange，提问作者keezar