M-ary tree: Difference between revisions
Content deleted Content added
m →Types of k-ary trees: fixed repeated citation I made in previous edit XD |
m fixing a ref error I made |
||
| Line 4: | Line 4: | ||
*A '''full k-ary tree''' is a k-ary tree where within each level every node has either ''0'' or ''k'' children. |
*A '''full k-ary tree''' is a k-ary tree where within each level every node has either ''0'' or ''k'' children. |
||
*A '''perfect k-ary tree''' is a full <ref name="orderedtrees">{{cite web|url=http://www.cs.lmu.edu/~ray/notes/orderedtrees/|title=Ordered Trees|accessdate=10 October 2011}}</ref> k-ary tree in which all [[leaf node]]s are at the same depth.<ref>{{cite web|url=http://xlinux.nist.gov/dads/HTML/perfectKaryTree.html|title=perfect k-ary tree|last=Black|first=Paul E.|date=20 April 2011|publisher=U.S. National Institute of Standards and Technology|accessdate=10 October 2011}}</ref> |
*A '''perfect k-ary tree''' is a full <ref name="orderedtrees">{{cite web|url=http://www.cs.lmu.edu/~ray/notes/orderedtrees/|title=Ordered Trees|accessdate=10 October 2011}}</ref> k-ary tree in which all [[leaf node]]s are at the same depth.<ref>{{cite web|url=http://xlinux.nist.gov/dads/HTML/perfectKaryTree.html|title=perfect k-ary tree|last=Black|first=Paul E.|date=20 April 2011|publisher=U.S. National Institute of Standards and Technology|accessdate=10 October 2011}}</ref> |
||
*A '''complete k-ary tree''' is a k-ary tree which is maximally space efficient. It must be completely filled on every level (meaning that each level has k children) except for the last level (which can have at most k children). However, if the last level is not complete, then all nodes of the tree must be "as far left as possible". <ref name="orderedtrees"> |
*A '''complete k-ary tree''' is a k-ary tree which is maximally space efficient. It must be completely filled on every level (meaning that each level has k children) except for the last level (which can have at most k children). However, if the last level is not complete, then all nodes of the tree must be "as far left as possible". <ref name="orderedtrees"></ref> |
||
==Properties of k-ary trees== |
==Properties of k-ary trees== |
||
Revision as of 22:49, 23 March 2012
In graph theory, a k-ary tree is a rooted tree in which each node has no more than k children. It is also sometimes known as a k-way tree, an N-ary tree, or an M-ary tree. A binary tree is the special case where k=2.
Types of k-ary trees
- A full k-ary tree is a k-ary tree where within each level every node has either 0 or k children.
- A perfect k-ary tree is a full [1] k-ary tree in which all leaf nodes are at the same depth.[2]
- A complete k-ary tree is a k-ary tree which is maximally space efficient. It must be completely filled on every level (meaning that each level has k children) except for the last level (which can have at most k children). However, if the last level is not complete, then all nodes of the tree must be "as far left as possible". [1]
Properties of k-ary trees
- For a k-ary tree with height h, the upper bound for the maximum number of leaves is .
- The total number of nodes is , while the height h is
References
- ^ a b "Ordered Trees". Retrieved 10 October 2011.
- ^ Black, Paul E. (20 April 2011). "perfect k-ary tree". U.S. National Institute of Standards and Technology. Retrieved 10 October 2011.
- Storer, James A. (2001). An Introduction to Data Structures and Algorithms. Birkhäuser Boston. ISBN 3764342536.
External links
 | This computer science article is a stub. You can help Wikipedia by expanding it. |