Question? Leave a message!




N-ary Trees

N-ary Trees
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
ECE 250 Algorithms and Data Structures N-ary Trees Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.N-arytrees 2 Outline This topic quickly looks at a generalization of a binary tree, where each node has up to N children – Definition – Perfect N-ary trees – Complete N-ary trees – Implementation using templatesN-arytrees 3 5.4.1 N-ary Trees One generalization of binary trees are a class of trees termed N-ary trees: – A tree where each node had N sub-trees, any of which may be may be empty treesN-arytrees 4 5.4.1 Ternary Trees Examples of a ternary (3-ary) trees – We don’t usually indicate empty sub-treesN-arytrees 5 5.4.1 Quaternary Trees Example of a perfect quaternary (4-ary) tree Under certain conditions, the number of operations required may be slightly fewer with quaternary trees (e.g., with heaps) – The asymptotic behaviour is similarN-arytrees 6 5.4.2.1 Perfect N-ary Trees Each node can have N children The number of nodes in a perfect N-ary tree of height h is 2 3 h 1 + N + N + N⋅⋅⋅ + N This is a geometric sum, and therefore, the number of h1 h N1 k nN nodes is  N1 k0N-arytrees 7 5.4.2.2 Perfect N-ary Trees Solving this equation for h, a perfect N-ary tree with n nodes has a height given by h logn(N1)11 NN-arytrees 8 5.4.2.2 Perfect N-ary Trees We note, however, that log (nN) – 1 = log (n), hence, we may N N postulate that log (n) should be an equally good approximation N N1 log nN111 n N11 ln N   N lim lim nn 1 log n  N nN ln  nN1  N1  lim lim1 nn nNn1 N1N-arytrees 9 5.4.2.3 N-ary Trees Recall that the height for perfect binary tree is approximately lg(n) Therefore, if the height of an N-ary tree is log (n), the ratio of the N heights is: log (n) log (n) 2 2  log (n) log (n) log (N ) N 2 2  log (N ) 2N-arytrees 10 5.4.2.3 N-ary Trees Therefore: – The height of a perfect quaternary tree is approximately ½ the height of a perfect binary tree with approximately the same number of nodes – The height of a perfect 16-ary tree is approximately ¼ the height of a perfect binary tree with the same number of nodesN-arytrees 11 5.4.2.4 Complete N-ary Trees A complete N-ary tree has height  h log Nn1  N  Like complete binary trees, complete N-ary trees can also be stored efficiently using an array: – Assume the root is at index 0 k1  – The parent of a node with index k is at location  N  – The children of a node with index k are at locations kN + j for j = 1, …, NN-arytrees 12 5.4.3 Implementation of N-ary Trees The “obvious” implementation of N-ary trees may be something like: include algorithm template typename Type class Nary_tree private: Type element; int N; Nary_tree children; public: Nary_tree( Type const &, int = 2 ); // ... template typename Type ; Nary_treeType::Nary_tree( Type const &e, int n ): element( e ), N( std::max( 2, n ) ), children( new Nary_treeN ) for ( int i = 0; i N; ++i ) childreni = nullptr; N-arytrees 13 5.4.3 Implementation of N-ary Trees Problems with this implementation: – Requires dynamic memory allocation – A destructor is required to delete the memory – No optimizations possible – Dynamic memory allocation may not always be available (embedded systems) Solution? – Specify N at compile time...N-arytrees 14 5.4.3 N-ary Trees with Template Parameters include algorithm template typename Type, int N class Nary_tree private: Type element; Nary_tree childrenstd::max(N, 2); // an array of N children public: Nary_tree( Type const & = Type() ) // ... ; template typename Type, int N Nary_treeType, N::Nary_tree( Type const &e ):element( e ) for ( int i = 0; i N; ++i ) childreni = nullptr; N-arytrees 15 5.4.3 N-ary Trees with Template Parameters Sample code using this class: Nary_treeint, 4 i4tree( 1975 ); // create a 4-way tree std::cout i4tree.retrieve() std::endl;N-arytrees 16 5.4.3 N-ary Trees nd Because the size of the array (the 2 template parameter) is specified at compile time: – The compiler can make certain optimizations – All memory is allocated at once • Possibly even on the stack at compile time – No destructor requiredN-arytrees 17 5.4.4 Applications One application of an 26-ary trees is a trie where the root represents the start of each valid word, and the different sub-trees represent next letters in valid words – Consider the words in the phrase “The fable then faded from my thoughts and memory.” – All 26 sub-trees are only shown for the root node, but all nodes have 26 sub-trees – Some nodes are marked as terminal indicating the end of a valid word – These terminal points could be used to store a list of all places in a document where the word occurs • Consider the ultimate index to a bookN-arytrees 18 Summary An N-ary tree is similar to a binary tree, however, each node can have up to N children A binary tree has a height approximately log (N) times the height of 2 an N-ary tree containing the same number of nodes