二叉树的复杂度

Question

我想了解二叉搜索树的一些复杂性。

我找不到完整的信息。我想知道在二叉搜索树上执行以下操作的复杂度：

1. 添加/插入元素
2. 删除元素
3. 查找元素（据我所知，这个是O(log(n))）

- nabroyan

---

这取决于你的算法，与数据结构关系不大。 - m4573r

一般是指二叉树吗？还是二叉搜索树？或者是某种特定的自平衡二叉搜索树？ - user395760

维基百科上关于二叉树的一切。 - masoud

是的，我是指二分搜索树，我刚刚编辑了我的问题。 - nabroyan

简单解释：https://dev59.com/q3E95IYBdhLWcg3wb9hb#13093274 - 2cupsOfTech

Answer 1

二叉搜索树中的插入、删除和查找：

• 最坏情况下为O(N)；
• 平均情况下为O(log(N))。

- md5

Answer 2

如果您有平衡的二叉树，所有三个复杂度都将为O(log(N))。如果您不平衡树，则可能为O(N)。

- Apurv

Answer 3

搜索是有效的。但不平衡的结构（这通常是情况）可能导致搜索/插入/删除操作的O(N)时间复杂度。这就是为什么二叉堆或其他种类的平衡树更受欢迎，其时间复杂度为O(log n)。

- SChepurin