4

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

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

  1. 添加/插入元素
  2. 移除一个元素
  3. 找到一个元素（我知道这个是O(log(n))）
4

3 回答 3

10

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

  • O(N)在最坏的情况下；
  • O(log(N))在平均情况下。
于 2013-03-23T12:39:54.297 回答
7

如果你有平衡二叉树，所有三个复杂度都将是O(log(N)). 如果你没有平衡树，它可能是O(N).

于 2013-03-23T13:00:06.253 回答
0

搜索是有效的。但是不平衡的结构（通常是这种情况）可能导致搜索/插入/删除操作的 O(N)。这就是为什么使用 O(log n) 时首选二叉堆或其他类型的平衡树的原因。.

于 2013-03-23T13:18:40.510 回答