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 recursively as the right child of R.
To add a leaf node to the HAFT: (incremental construction) a) if current tree is empty tree. Create a tree of single node. b) if current tree is a complete binary tree, then: 1. create a root node R; 2. make old complete binary tree the left child of R; 3. create a leaf node as right child of R. c) otherwise, add a leaf to the right child of HAFT recursively. 2013/3/15 Megha Agrawal <[email protected]> > > 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 provide algo/code for construction of HAFT? > > -- > Regards, > Megha Agrawal > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- __________________________________________________ -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
