是否存在不是平衡二叉搜索树的平衡二叉树？时间复杂度是多少？

Question

是否存在不是平衡二叉搜索树的平衡二叉树？如果是这样，在这样的树中搜索一个节点的时间复杂度是多少。

我的理解是这样的：

1. 二叉树：任何节点都有两个最大叶节点。在二叉树中搜索，使用 DFS 或 BFS 是 O|V+E|
2. 二叉搜索树：BST 是一棵有序节点树。在二叉搜索树中搜索，使用 DFS 是 O|log n|
3. 平衡树（假设高度平衡）：根以下的最大层数保持在最小值。 平衡对搜索的时间复杂度有影响吗？

所以，从本质上讲，我可以创建一个高度平衡但无序的二叉树吗？这棵树的搜索时间是否为 O|V+E|还是会更好？

Answer 1

搜索无序二叉树需要遍历每个节点，所以是否平衡是O(N)

          50
       __/  \__
      /        \
    25          26
   /  \        /  \
 49    46    48    47

是否

          50
       __/  \__
      /        \
    25          26
   /  \
 49    46
      /  \
     5    6

平衡一棵无序树真的没有意义。