Computer Science Asked by Arthur B on February 10, 2021
Consider a list of full binary trees of heights $(h_0, h_1, ldots, h_{n-1})$ where a tree with a single leaf is deemed to have height 0.
The list has the property that the height of the tree when going through the list is, at first strictly increasing, and then strictly decreasing, i.e $$exists k, 0 leq k < n, ~forall i, (1 leq i leq k implies h_{i-1} < h_{i}) wedge (k leq i < n implies h_{i} > h_{i+1})$$
Examples of list of heights that have this property
()
(4)
(0, 1, 5)
(0, 1, 3, 2, 1)
(3, 0)
Examples of lists that do not have this property
(3, 3)
(3, 4, 2, 3)
The total number of leaves in this list $sum_{i=0}^n 2^{h_i}$ so, in the worse case, the length of the list is bounded by $2 log_2 l$ if $l$ is the number of leaves.
We define the "take" operation on a list in pseudocode as follow
take quantity forest :
result = []
while quantity > 0 and forest not empty:
if 2^(forest.head.height) < quantity:
forest = forest.tail
insert = front
while result not empty and result.front.height = insert.height
insert = merge(insert, result.head)
result = result.tail
result = cons(insert, result)
quantity = quantity - 2^(front.height)
else:
forest = cons(forest.head.left, cons(forest.head.right, forest.tail))
return result
It’s not too hard to convince oneself that this take operation preserves the property of being increasing then decreasing of the list (although the invariant can be temporarily violated in the loop).
It’s a bit less obvious than the list returned by the procedure also has this property, but it still seems true.
Much less obvious is the worst-case complexity of the operation as a function of $l$, the number of leaves. The inner while looks like it could introduce some quadratic $mathcal{O}(log^2 l)$ complexity, but it is not obvious that this is actually the case.
So what is the worse case complexity of this procedure?
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP