Combine two trees

How to merge two splay trees with amortized cost of log (n)?

+3
source share
1 answer

I assume that the splay trees you want to combine hold nobjects each. (i.e., all objects 2n). Then I think that it is impossible to combine them with amortized cost log(n)if you do not impose some additional assumptions. If you do not have information about the objects contained in the trees, you will have to search at least on each element of one of the two trees, so the cost O(n).

However, if you can make certain assumptions about objects, you can do it in O(log(n)). You can extract specific subtrees so that you can insert the entire subtree into another splay tree. However, I do not know the exact algorithm like acchieve O(log(n)). For example, if we know that the largest object is Tree1smaller than the smallest object in Tree2, then we can simply translate the left-most node out Tree2, and then we hang the root Tree1in a new root Tree2.

0
source

Source: https://habr.com/ru/post/1767918/


All Articles