Hello,
HAFT is a rooted binary tree in which every non-leaf node v has following
properties:
i. v has exactly two childrens.
ii. the left child of v is root of complete binary subtree, containing half
or more of v's descendants.
Some examples of HAFT are given in attached image.
Can anybody
To construct a HAFT of with N leaves:
a) if N=2^K for some K=0, then construct a complete tree with N leaves.
b) otherwise, suppose 2^K N 2^(K+1), then
1) construct root node R.
2) construct a complete binary tree with 2^K leaves as the left child of R.
3) construct a HAFT with (N-2^K) leaves