M-ary tree: Difference between revisions
Content deleted Content added
→Types of k-ary trees: added a part about complete k-ary trees and added a citation to the definition of where I got it from |
→Types of k-ary trees: fixed spacing issueswith the section on complete k-ary trees |
||
| 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 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 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 |
*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>{{cite web|url=http://www.cs.lmu.edu/~ray/notes/orderedtrees/|title=Ordered Trees|accessdate=10 October 2011}}</ref> |
||
(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>{{cite web|url=http://www.cs.lmu.edu/~ray/notes/orderedtrees/|title=Ordered Trees|accessdate=10 October 2011}}</ref> |
|||
==Properties of k-ary trees== |
==Properties of k-ary trees== |
||
Revision as of 22:39, 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 k-ary tree in which all leaf nodes are at the same depth.[1]
- 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". [2]
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
- ^ Black, Paul E. (20 April 2011). "perfect k-ary tree". U.S. National Institute of Standards and Technology. Retrieved 10 October 2011.
- ^ "Ordered Trees". 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. |