创建二叉树的时间复杂度 [英] Time Complexity of Creating a Binary Tree

问题描述

我正在尝试从提供以下信息的源创建一棵树:要添加到树中的 2 个节点，以及应添加这 2 个新闻节点的节点.为了找到这个节点在树中的位置，我使用了一个需要 O(n) 的中序遍历.因此，如果要在树中添加 n 个节点，则整个树的创建是否为 O(n^2).我的限制是它应该只需要 O(n) 来创建树.

解决方案

您可以在 HashMap [1] 中保留对树的每个节点的引用，以获得对每个节点的 O(1) 访问node 而不是 O(log(n)) 这是典型的树.这将使在 O(n) 时间内构建树成为可能，因为 HashMap 允许您直接跳转到一个节点，而不是从树的根节点遍历那里.

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

I am trying to create a tree from a source that provides: the 2 nodes to be added to the tree, and the node which these 2 news nodes should be added. To find where this node is in the tree, I used a inorder traversal which takes O(n). So if there was n number of nodes to be added in the tree, will the creation of the whole tree be O(n^2). My constraint is that it should only take O(n) to create the tree.

解决方案

You could keep references to each node of the tree in a HashMap [1], to get O(1) access to each node instead of the O(log(n)) which is typical of trees. That would make it possible to build the tree in O(n) time, because that HashMap lets you jump directly to a node instead of traversing there from the tree's root node.

[1] The key would be whatever the source uses for uniquely identifying the nodes (I'm assuming it to be an integer or string). The value would be a reference to the node in the tree. Note that the tree implementation must make all its nodes public, so you will probably need to write the tree yourself or find a suitable library (JDK's trees such as TreeMap keep their internal structure private, so they won't cut it).

这篇关于创建二叉树的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！