M-Ary Tree Encyclopedia Article

M-Ary Tree

The following sections of this BookRags Literature Study Guide is offprint from Gale's For Students Series: Presenting Analysis, Context, and Criticism on Commonly Studied Works: Introduction, Author Biography, Plot Summary, Characters, Themes, Style, Historical Context, Critical Overview, Criticism and Critical Essays, Media Adaptations, Topics for Further Study, Compare & Contrast, What Do I Read Next?, For Further Study, and Sources.

(c)1998-2002; (c)2002 by Gale. Gale is an imprint of The Gale Group, Inc., a division of Thomson Learning, Inc. Gale and Design and Thomson Learning are trademarks used herein under license.

The following sections, if they exist, are offprint from Beacham's Encyclopedia of Popular Fiction: "Social Concerns", "Thematic Overview", "Techniques", "Literary Precedents", "Key Questions", "Related Titles", "Adaptations", "Related Web Sites". (c)1994-2005, by Walton Beacham.

The following sections, if they exist, are offprint from Beacham's Guide to Literature for Young Adults: "About the Author", "Overview", "Setting", "Literary Qualities", "Social Sensitivity", "Topics for Discussion", "Ideas for Reports and Papers". (c)1994-2005, by Walton Beacham.

All other sections in this Literature Study Guide are owned and copyrighted by BookRags, Inc.

M-Ary Tree

An m-ary tree is a data structure employed to improve external sorting in which for every node in the tree there are no more than m child nodes. Binary trees are a specific implementation of an m-ary tree where there are m = 2 child nodes for every node on the tree. This type of data tree is particularly important when in certain computing scenarios sorting must be done with the majority of the data remaining on auxiliary storage devices. An external sorting strategy, called the Hillsort, in combination with the m-ary tree architecture allowed the development of the Ternary Hillsort. This combinational sorting method is superior in its performance over the pure external sorting and the pure ternary tree since it executes faster and the parent-child and sibling relationships are easily calculated.

A tree is a type of organizational structuring of classes of elements, databases, or directory files that has a type of generalization or hierarchical architecture. This type of structure looks like a tree with its different branches and nodes. Also there is a unique path between any pair of nodes on the tree. The top of the file structure is called the root node and each entry on a different branch is called a child node of the parent. An m-ary tree is a particular type of tree where there are no more than m child nodes for every node in the tree. When m = 2 the tree is called a binary tree. This means that for each node on the tree that there are exactly two links to two other trees or subtrees where the two subtrees are often referred to as the left and right subtrees. This particular type of m-ary tree is the most commonly used type of tree data structure. If there are exactly m or zero child nodes for each node in the tree then the tree is called a full binary tree.

There is a simple formula for counting the number of nodes of an m-ary tree. If an m-ary tree has depth n and m > 1 then the number of nodes is given by: