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 <megha1...@iiitd.ac.in> > > 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 algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
