merge k AVL trees complexity
-
Hello everybody i am trying to disprove the claim: the time complexity of merging K AVL trees is O(the sum of their nodes number) i tried to calculate the complexity of meging K AVL trees but there could be more than one algorithm. How do i disprove the claim. Thanks
-
Hello everybody i am trying to disprove the claim: the time complexity of merging K AVL trees is O(the sum of their nodes number) i tried to calculate the complexity of meging K AVL trees but there could be more than one algorithm. How do i disprove the claim. Thanks
If you handle every node in every tree, the complexity will be O(the sum of their nodes number). So one way to disprove this is to come up with a merging algorithm that avoids handling every node. One way to avoid handling every node is to reuse the existing structure of the AVL trees. This can be done in trivial cases where the ranges of key values for the trees don't overlap. If they DO overlap (which is most likely), then you have a much more difficult problem, because you have to "weave" one tree into another, while maintaining the tree's balanced property. You may be able to find subtrees whose key values don't overlap, and merge these. Using bigger building blocks like this avoids handling every node, and reduces the time complexity of your algorithm. After merging, you will probably have to do a little rearranging to restore the balanced property. But it seems very hard, and in most cases, probably impossible.
-
Hello everybody i am trying to disprove the claim: the time complexity of merging K AVL trees is O(the sum of their nodes number) i tried to calculate the complexity of meging K AVL trees but there could be more than one algorithm. How do i disprove the claim. Thanks
To merge K trees in O(N), where N is the sum of node counts, you must never search on insertion: all your insertions must complete in O(1). In other words, on each step you must insert the new root node, and maybe do a rotation or two. However, the new root could come from any of the K trees that you are merging, so the time to search for that node would be O(K) (perhaps you could do O(Log2 K), but regardless of how you do it, K will be a factor to it). That's why I think the best you can do is O(N*Log2 K).
-
If you handle every node in every tree, the complexity will be O(the sum of their nodes number). So one way to disprove this is to come up with a merging algorithm that avoids handling every node. One way to avoid handling every node is to reuse the existing structure of the AVL trees. This can be done in trivial cases where the ranges of key values for the trees don't overlap. If they DO overlap (which is most likely), then you have a much more difficult problem, because you have to "weave" one tree into another, while maintaining the tree's balanced property. You may be able to find subtrees whose key values don't overlap, and merge these. Using bigger building blocks like this avoids handling every node, and reduces the time complexity of your algorithm. After merging, you will probably have to do a little rearranging to restore the balanced property. But it seems very hard, and in most cases, probably impossible.
If you diligently handle every node, I think the time will be O(N*Log2 N), where N is the sum of all nodes numbers.
-
To merge K trees in O(N), where N is the sum of node counts, you must never search on insertion: all your insertions must complete in O(1). In other words, on each step you must insert the new root node, and maybe do a rotation or two. However, the new root could come from any of the K trees that you are merging, so the time to search for that node would be O(K) (perhaps you could do O(Log2 K), but regardless of how you do it, K will be a factor to it). That's why I think the best you can do is O(N*Log2 K).
i liked that idea, lets say we've got k tree where each one got one node. we know that there is no algorithm that can sort with better than teta(klogk) so, in order to sort the nodes in array and scan an empty tree to insert them, it will takes at least teta(klogk)