N-ary Trees

N-ary Trees
ECE 250 Algorithms and Data Structures Nary 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 © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Narytrees 2 Outline This topic quickly looks at a generalization of a binary tree, where each node has up to N children – Definition – Perfect Nary trees – Complete Nary trees – Implementation using templatesNarytrees 3 5.4.1 Nary Trees One generalization of binary trees are a class of trees termed Nary trees: – A tree where each node had N subtrees, any of which may be may be empty treesNarytrees 4 5.4.1 Ternary Trees Examples of a ternary (3ary) trees – We don’t usually indicate empty subtreesNarytrees 5 5.4.1 Quaternary Trees Example of a perfect quaternary (4ary) tree Under certain conditions, the number of operations required may be slightly fewer with quaternary trees (e.g., with heaps) – The asymptotic behaviour is similarNarytrees 6 5.4.2.1 Perfect Nary Trees Each node can have N children The number of nodes in a perfect Nary 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0Narytrees 7 5.4.2.2 Perfect Nary Trees Solving this equation for h, a perfect Nary tree with n nodes has a height given by h logn(N1)11 NNarytrees 8 5.4.2.2 Perfect Nary 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1Narytrees 9 5.4.2.3 Nary Trees Recall that the height for perfect binary tree is approximately lg(n) Therefore, if the height of an Nary 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 ) 2Narytrees 10 5.4.2.3 Nary 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 16ary tree is approximately ¼ the height of a perfect binary tree with the same number of nodesNarytrees 11 5.4.2.4 Complete Nary Trees A complete Nary tree has height  h log Nn1  N  Like complete binary trees, complete Nary 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, …, NNarytrees 12 5.4.3 Implementation of Nary Trees The “obvious” implementation of Nary trees may be something like: include algorithm template typename Type class Narytree private: Type element; int N; Narytree children; public: Narytree( Type const , int = 2 ); // ... template typename Type ; NarytreeType::Narytree( Type const e, int n ): element( e ), N( std::max( 2, n ) ), children( new NarytreeN ) for ( int i = 0; i N; ++i ) childreni = nullptr; Narytrees 13 5.4.3 Implementation of Nary 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...Narytrees 14 5.4.3 Nary Trees with Template Parameters include algorithm template typename Type, int N class Narytree private: Type element; Narytree childrenstd::max(N, 2); // an array of N children public: Narytree( Type const = Type() ) // ... ; template typename Type, int N NarytreeType, N::Narytree( Type const e ):element( e ) for ( int i = 0; i N; ++i ) childreni = nullptr; Narytrees 15 5.4.3 Nary Trees with Template Parameters Sample code using this class: Narytreeint, 4 i4tree( 1975 ); // create a 4way tree std::cout i4tree.retrieve() std::endl;Narytrees 16 5.4.3 Nary 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 requiredNarytrees 17 5.4.4 Applications One application of an 26ary trees is a trie where the root represents the start of each valid word, and the different subtrees represent next letters in valid words – Consider the words in the phrase “The fable then faded from my thoughts and memory.” – All 26 subtrees are only shown for the root node, but all nodes have 26 subtrees – 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 bookNarytrees 18 Summary An Nary 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 Nary tree containing the same number of nodes
Website URL
Comment
Presentations
Free
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom