二叉搜索树（BST）的大O复杂度

Question

我一直在审查我所学到的所有知识，并发现该网站，并且说在二叉树中搜索的最坏情况是O（n）复杂性。到目前为止，我知道，在二叉搜索树中，是一棵排序树，我们可以使用二叉搜索来搜索它，它可能具有O（log n）-log base 2。

谁能解释？

Answer 1

在绝对最坏的情况下，带有N元素的二叉树就像一个链表。
因此，将存在N级别，并且搜索将N遍历。

                                    ~ Root ~
                                      ____
                                     | 42 |
                                     |____|
                                    /      \
                               ____/        \
                              | 13 |         X
                              |____|
                             /      \
                        ____/        \
                       | 11 |         X
                       |____|
                      /      \
                     /        \
                  ...          X

这就是为什么O(N)在最坏的情况下。
这就是为什么我们需要平衡树以实现O(log N)搜索的原因。