为什么这个二叉树搜索比插入花费的时间长得多？

Question

我正在尝试 learn/understand 一些基本算法，今天我决定用 Go 编写一棵二叉树。结构如下所示：

type Node struct {
  Value int
  Left  *Node
  Right *Node
}

这是我检查树是否包含 int 的函数：

func (tree *Node) Contains(val int) bool {
  if val == tree.Value {
    return true
  } else if val > tree.Value {
    if tree.Right != nil {
      return tree.Right.Contains(val)
    } else {
      return false
    }
  } else if val < tree.Value {
    if tree.Left != nil {
      return tree.Left.Contains(val)
    } else {
      return false
    }
  } else { // huh
    return false
  }
}

我写了一个测试函数来测试对树的不同操作需要多长时间。我的 Insert() 函数 34ms 插入 100,000 个随机整数，我的 Contains() 函数 33ms 检查是否这棵树包含 100,000 个随机整数。如果我将随机整数的数量增加到 1,000,000，我的 Insert() 函数需要 34ms 到运行，但是我的 Contains() 函数突然需要 321ms 到运行.

为什么 Contains() 运行时间增加如此之快，而 Insert() 几乎保持不变？

Answer 1

Insert 函数应该定期重新平衡树，因为不平衡的树可能会导致遍历时间非常不平衡。因此，Insert 应该通常比 Contains.

慢

如果您的 Insert 函数没有重新平衡树，那么任何给定函数所需的时间将变为 O(n) 最坏情况而不是 O(log n) 并且相当不可预测。

此外，在谈论 O(...) 时间复杂度时，我们通常谈论的是最坏情况 行为。如果您对单个调用进行计时，那么任何给定的调用都可能比最坏的情况花费（少得多）时间——例如，Contains 寻找恰好是根的节点将立即 return 而不管尺寸。

为什么这个二叉树搜索比插入花费的时间长得多？

Why does this binary tree search take so much longer than an insertion?

algorithm

binary-tree

go

time-complexity