为什么这种二叉树搜索比插入要花这么长时间？

Question

I'm trying to learn/understand some basic algorithms, and today I decided to write a binary tree in Go. This is what the structure looks like:

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

Here's my function to check if the tree contains an 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
  }
}

I wrote a test function to test how long different operations on the tree take. It takes my Insert() function 34ms to insert 100,000 random integers, and it takes my Contains() function 33ms to check if the tree contains 100,000 random integers. If I bump the number of random integers up to 1,000,000, it takes my Insert() function 34ms to run, but my Contains() function suddenly takes 321ms to run.

Why does Contains() run time increase so drastically, while Insert() stays practically the same?

Answer 1

The Insert function should periodically rebalance the tree, as an imbalanced tree may lead to very uneven traversal times. As a result, Insert should generally be slower that Contains.

If your Insert function does not rebalance the tree, then the time required for any given function become O(n) worst case instead of O(log n) and fairly unpredictable.

In addition, when talking about O(...) time complexity, we're generally talking about worst case behavior. If you time single calls, then any given call may take (much) less time than the worst case -- for example, Contains looking for the node that happens to be the root will return immediately regardless of the size.