0

This is a part of job interview question which got harder in its second part.

Given two 2-3 trees T1 and T2 such that for each tree h in known (h for height) and m, M for each tree are known too (m for minimum and M for maximum), Plus that each node in T1 < every node in T2. I was asked to find an algorithm to join both of them into one tree in O(|h1-h2|+1)

This one was quite easy, and I have to point that this algorithm may result in a tree with h bigger than the previous two.

Now, I was given k 2-3 trees (T1,T2,T3...Tk) with the same exact conditions plus knowing that h_1<=h_2<=...<=h_k and that no three trees share the same height to join them in O(h_k-h_1+k).

At first I thought about using the previou algorithm to join the first two together then to join the third to the result and so on but I felt that something is going wrong here since I didn't utilise the fact that "no three trees share the same height".

What I am missing here?

1 Answers1

1

Your solution is correct, but it would not be if you had more than 2 trees of the same height. For example, if you have k trees of identical height, then the first two would be indeed merged in O(h_1 - h_1) = O(1) time, but the resulting height can become h_1 + 1. While it only might become, or it might not so let me show that it is possible that everything goes wrong.

The maximum amount of keys we can have inside a tree of height n is 3^(n+1)-1. That's because each vertex has at most 3 subtrees, therefore i-th level has 3^i vertices, adding n levels would result in (3^(n + 1) - 1)/2 vertices. Because each vertex has 2 keys in such a scenario the total number of keys is 3^(n + 1) - 1.

Therefore, if we merge 4 such maximum trees, we would for sure get a tree with height increased by 2, 16 merged trees to get height increased by 3, and so on. Thus, while the first 3 merges are done in constant time, the next 12 ones are done twice slower, and the next 48 are done 3 times slower, and so on. You would do Ω(i) operations Ω(3^(i+1) - 3^i) times for each i starting from 1 and up to log(k).

The resulting sum

Because Ω(3^log(k)) = Ω(k) this sum is definitely Ω(k log k), therefore inappropriate for given asymptotic bounds.

When no 3 trees share the same height, this problem does not occur, because whenever you merge two trees the resulting height is max(h_i, h_(i+1)) + 1 = h_(i+1) + 1, and h_(i+3) >= h_(i+1) + 1, therefore the height of merged part never goes one above the next tree, and that's where +k part gets from in asymptotic bound.

Roman Svistunov
  • 1,069
  • 6
  • 11
  • 1
    "but the resulting height can become h_1 + 1" can you elaborate on what's the problem if this happened? –  Dec 17 '20 at 12:43
  • @MrCalc my initial calculation was off, discovered it while describing the problem more precisely, fixed in the edit. The problem persists despite being less intense. – Roman Svistunov Dec 17 '20 at 13:05
  • ״ the resulting height is max(h_i, h_(i+1)) + 1 = h_(i+1) + 1״ Did you mean the max resulting height here instead of resulting height? (Since if we combine two trees with height of 2 and 3 we can get 3 I think) Plus why the height can grow only by one? It can grow by 2 or more –  Dec 17 '20 at 13:19
  • Yes, I meant the maximum height, here while in theory there exists a tree that would be of height increased by two or more, the most-often used implementation of the merging operation can only increase height by one splitting the root vertex. – Roman Svistunov Dec 17 '20 at 13:23
  • But something seems wrong to me, we merge T1 with T2 in O(h2-h1+1) right? then the result have a max height of h2+1 then we merge it with T3 and the but that won't be in O(h3-h2+1) as I want it... It would be in O(h3-(h2+1)+1) Plus, shouldn't we consider the min height of the result instead of the max height? since the min gives more time complexity... –  Dec 17 '20 at 13:35
  • O(h3 - (h2 + 1) + 1) = O(h3 - h2 + 1), so if height not grows high it would be alright. We are considering max height, because, if the current height is less then what we are merging with we would get h2-h1 + h3-h2 + ... + hn - h(n-1), and it would result in hn - h1 operations which is alright, but if height grows too high the difference would be another way around because actually, we are merging in O(|h1 - h2|), not O(h1 - h2). If the height grows too slow - it is not a problem. But height growing too fast is. – Roman Svistunov Dec 17 '20 at 13:42
  • sorry but still I don't get it, if the difference between height is bigger then time complexity is bigger which mean min height is the problem here not max height (To make the gap between current tree and the next one bigger) –  Dec 17 '20 at 14:02
  • If the current tree is higher, then the next one, then the higher it is, the worse the algorithm works, therefore in such case, we should analyze the maximum height it can get to. I am using words like "at least four times" to make sure I do not overestimate the maximum height that can actually be achieved. Also, some of my Big-O were messed with Big-Omega, fixed them now – Roman Svistunov Dec 17 '20 at 14:07
  • 1
    Got it, last thing Q1) "Therefore, if we merge 5 such maximum trees, we would for sure get a tree with height increased by 2" why 5 of them why you choose 5 exactly and then 17? it's enough to merge 2 full to get one more level Q2) |The maximum amount of keys we can have inside a tree of height n is 3 * 4^n" I don't agree with this, where 4^n came from too? –  Dec 17 '20 at 14:09
  • 1
    Thank you for pointing to the number of keys, I calculated it the wrong way the first time, but other claims stay correct. If you merge 4 trees each of size 4^(n+1)-1 you would get 4^(n+2)-4 elements if the fifth tree has more than 3 vertices, so I would assume h_k >= 2, adding it would result in more than 4^(n+2)-1, and it won't fit within the tree of height n+1. Then, having 5 such bigger trees would result in another height increase and so on. – Roman Svistunov Dec 17 '20 at 14:22
  • 1
    ". That's because each vertex has at most 4 subtrees" in 2-3 there is a max of 3 and not 4 –  Dec 17 '20 at 14:23
  • Actually yes, I messed up a little with B trees with other parameters, but almost everything would stay true, in most cases simply replacing 4 with 3 and 3 with 2 would work, I would edit this fix in my answer, but it would take some time. The idea is just that the size is exponential from the height, and if we merge some trees height will grow at least logarithmically. – Roman Svistunov Dec 17 '20 at 14:27
  • Actually, it took less time then I have expected, now it should be correct (so I am sure in nothing right now) – Roman Svistunov Dec 17 '20 at 14:33