具有一个子树的二叉搜索树

Question

我只是想知道，

有可能没有左子树的二叉搜索树吗？

或者 root 必须 children？

Answer 1

是的，可以。它还可以包含 1 个项目（仅根）甚至 0 个项目（空树或空树）。

在简单 BST 的情况下，尝试插入 1、2、3、4、5、6、7 等等 - 你会得到如下树：

1
 \
  2
   \
    3
     \ 
      4
       \
        5
         \
          6
           \
            7
             ...  

在这种情况下，搜索操作将需要O(n) - 这就是为什么它是二叉搜索树的最坏情况。这样的树叫做unbalanced tree.
为了避免这种情况，我们有自平衡二叉搜索树。