英文:
Why does this binary tree search take so much longer than an insertion?
问题
我正在尝试学习/理解一些基本算法，今天我决定用Go语言编写一个二叉树。结构如下：
type Node struct {
Value int
Left *Node
Right *Node
}
这是我用来检查树中是否包含某个整数的函数：
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()函数插入100,000个随机整数需要34毫秒，而使用我的Contains()函数检查树中是否包含100,000个随机整数需要33毫秒。如果我将随机整数的数量增加到1,000,000，那么我的Insert()函数运行时间仍然是34毫秒，但是Contains()函数的运行时间突然增加到了321毫秒。
为什么Contains()函数的运行时间增加如此剧烈，而Insert()函数的运行时间几乎没有变化？
英文:
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?
答案1
得分: 1
Insert函数应该定期重新平衡树，因为不平衡的树可能导致遍历时间非常不均匀。因此，Insert函数通常比Contains函数慢。
如果你的Insert函数不重新平衡树，那么任何给定函数的时间复杂度将变为最坏情况下的O(n)，而且相当不可预测。
此外，当我们谈论O(...)时间复杂度时，通常是指最坏情况下的行为。如果你计时单个调用，那么任何给定的调用可能比最坏情况下的时间（要快得多）少，例如，Contains函数查找恰好是根节点的节点时，无论树的大小如何，都会立即返回。
英文:
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论