Tree with Multiple Children - Linear Time Access Complexity
My problem is not with the structure to hold the Tree but the way I am
doing it; because I think this implementation will cost much in long run.
I have a tree structure in which a tree Node will contain the List of
references of its children. But here the problem is that while finding the
child of a Node, we need to go through the List of children which will
take Linear time(Linear time complexity). And I also need to store these
all as immediate child(as children word is used for the immediate
children).
Now, is there any way I can put all the children other than List structure
so that the retrieval and deletion of the children from the List will be
efficient and logarithmic(if we can)?
If I am going to traverse the Tree then to go to the right children from
the root node, I will have to check a condition for each child node. That
check would be Linear search and check. I just want a technique which will
help in improving this algorithm of searching for the right child in the
children list during traversal.
No comments:
Post a Comment