创建二叉树的时间复杂度

Question

我正在尝试从提供以下内容的源创建树:要添加到树中的2个节点,以及应添加这2个新闻节点的节点.为了找到这个节点在树中的位置,我使用了一个带有O(n)的inorder遍历.因此,如果在树中添加了n个节点,则整个树的创建将是O(n ^ 2).我的约束是它应该只用O(n)来创建树.

Answer 1

在二叉树中查找节点是O(log(n))因为树具有log(n)级别(每个级别保持其上面的级别的两倍).因此,要创建/插入n二进制树中的元素O(nlog(n)).

Answer 2

您可以在HashMap [1]中保留对树的每个节点的引用,以O(1)访问每个节点而不是O(log(n))典型的树.这样就可以及时构建树O(n),因为HashMap允许您直接跳转到节点而不是从树的根节点遍历.

[1]密钥将是源用于唯一标识节点的任何内容(我假设它是一个整数或字符串).该值将是对树中节点的引用.请注意,树实现必须使其所有节点都公开,因此您可能需要自己编写树或找到合适的库(例如TreeMap的JDK树保持其内部结构为私有,因此它们不会删除它).