二叉树复杂度

Question

我想知道二叉搜索树的一些复杂性。

我找不到完整的信息。我想知道在二叉搜索树

1. ，增加了对以下操作的复杂性/插入元素
2. 删除元素
3. 找到一个元素（因为我知道这个人是O(log(n))）

Answer 1

插入，删除，并在二叉搜索树搜索是：

• O(N)在最坏的情况下;
• O(log(N))在一般情况下。

Answer 2

如果你有平衡二叉树，所有三个复杂性将是O(log(N))。如果你不平衡树，它可能是O(N)。

Answer 3

搜索有效。但是，不平衡的结构（通常是这种情况）会导致O（N）用于搜索/插入/删除操作。这就是为什么二进制堆或其他类型的平衡树优先于O（log n）。 。