Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
M-ary tree
Résumé
In graph theory, an m-ary tree (for nonnegative integers m) (also known as n-ary, k-ary or k-way tree) is an arborescence (or, for some authors, an ordered tree) in which each node has no more than m children. A binary tree is the special case where m = 2, and a ternary tree is another case with m = 3 that limits its children to three.
A full m-ary tree is an m-ary tree where within each level every node has 0 or m children.
A complete m-ary tree (or, less commonly, a perfect m-ary tree) is a full m-ary tree in which all leaf nodes are at the same depth.
For an m-ary tree with height h, the upper bound for the maximum number of leaves is .
The height h of an m-ary tree does not include the root node, with a tree containing only a root node having a height of 0.
The height of a tree is equal to the maximum depth D of any node in the tree.
The total number of nodes in a perfect m-ary tree is , while the height h is
By the definition of Big-Ω, the maximum depth
The height of a complete m-ary tree with n nodes is .
The total number of possible m-ary tree with n nodes is (which is a Catalan number).
tree traversal
Traversing a m-ary tree is very similar to traversing a binary tree. The pre-order traversal goes to parent, left subtree and the right subtree, and for traversing post-order it goes by left subtree, right subtree, and parent node. For traversing in-order, since there are more than two children per node for m > 2, one must define the notion of left and right subtrees. One common method to establish left/right subtrees is to divide the list of children nodes into two groups. By defining an order on the m children of a node, the first nodes would constitute the left subtree and nodes would constitute the right subtree.
Using an array for representing a m-ary tree is inefficient, because most of the nodes in practical applications contain less than m children. As a result, this fact leads to a sparse array with large unused space in the memory.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.