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.
3 Answers
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 n elements into a binary tree it's O(nlog(n)).
1 Comment
ftw
Look ups are only
O(log(n)) if the tree is balanced, O(n) if its unbalanced. Create/insert n elements if it's sorted would be O(n^2)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).
4 Comments
twain249
while this would solve the question, it begs another question: Why not just store the data in a HashMap at the point and forgo the tree entirely.
Esko Luontola
twain249: True. If this is homework, I doubt there is any real reason to use a tree, other than that the assignment says so. :) One realistic (but rare) reason I could come up with is that the system needs to quickly restore its state from a file after restart (thus the O(n) startup time) and during normal operation the system has strict worst-case latency requirements (thus hash map's amortized O(1) is not acceptable, but a tree's predictable O(log(n)) is needed).
Ciro Santilli OurBigBook.com
The words O(1) amortized time given a perfect hash function or
O(1) average should appear more predominantly in this answer :-)
BARJ
One advantage I can think using a B-tree instead of a hash-table, if you are storing strings, is that with a hash-table you can not do prefix searches, with B-tree you can.
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(n log n). There does seem to be something missing from your description. Also I assume that's homework so you should add the right tags.