Java 创建二叉树的时间复杂度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9659394/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Time Complexity of Creating a Binary Tree
提问by Dan
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.
我正在尝试从提供的源创建一棵树：要添加到树中的 2 个节点，以及应添加这 2 个新闻节点的节点。为了找到这个节点在树中的位置，我使用了一个需要 O(n) 的中序遍历。因此，如果要在树中添加 n 个节点，则整个树的创建是否为 O(n^2)。我的限制是它应该只需要 O(n) 来创建树。
采纳答案by Esko Luontola
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.
您可以在 HashMap [1] 中保留对树的每个节点的引用，以O(1)访问每个节点而不是O(log(n))树的典型节点。这将使及时构建树成为可能O(n)，因为 HashMap 允许您直接跳转到一个节点，而不是从树的根节点遍历那里。
[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).
[1] 关键是源用于唯一标识节点的任何内容（我假设它是整数或字符串）。该值将是对树中节点的引用。请注意，树实现必须公开其所有节点，因此您可能需要自己编写树或找到合适的库（JDK 的树，例如 TreeMap，将其内部结构保持为私有，因此它们不会对其进行切割）。
回答by twain249
Looking up a node in a binary tree is O(log(n))because the tree has log(n)levels (each level holds twice as much as the level above it). Therefore to create/insert nelements into a binary tree it's O(nlog(n)).
在二叉树中查找节点是O(log(n))因为树有log(n)层次（每个层次是它上面层次的两倍）。因此，要创建/插入n元素到二叉树中，它是O(nlog(n)).
回答by Guest
for Binary search tree time complexity will be O(nlogn) when the elements are not sorted and sorted it takes O(n^2). It is because to to insert one element in a sorted list in a BST O(n) time is taken so for n elements O(n^2) and for a balanced or almost balanced binary search tree max time for insertion is logn so for n elements it is nlogn
对于二叉搜索树的时间复杂度为 O(nlogn)，当元素未排序时，排序需要 O(n^2)。这是因为在 BST O(n) 时间内在排序列表中插入一个元素需要花费 O(n^2) 个元素，并且对于平衡或几乎平衡的二叉搜索树，插入的最大时间为 logn，因此对于n 个元素是 nlogn
