Multi-Way Trees
From
(Difference between revisions)
| Line 3: | Line 3: | ||
</noinclude> | </noinclude> | ||
<br/> | <br/> | ||
| - | Multi-Way trees are trees that allow 0 or more children up to some fixed limit '''''m''''' for the entire tree; they are sometimes refered to as '''''order m trees'''''. When data are inserted or removed from a node, | + | Multi-Way trees are trees that allow 0 or more children up to some fixed limit '''''m''''' for the entire tree; they are sometimes refered to as '''''order m trees'''''. When data are inserted or removed from a node, it's number of child nodes changes. In order to maintain the pre-defined range nodes may be joined or split. Because a range of child nodes are permitted, muliway-trees do not need re-balancing as frequently as other self-balancing search trees, but may waste some space, since nodes are not entirely full. |
==Multi-Way Tree Implementations== | ==Multi-Way Tree Implementations== | ||
*[[B-Trees|B Trees]] <br/> | *[[B-Trees|B Trees]] <br/> | ||
Current revision as of 07:36, 12 May 2009
| ← Binary Trees | ↑ Tree ADTs | General Trees → |
Multi-Way trees are trees that allow 0 or more children up to some fixed limit m for the entire tree; they are sometimes refered to as order m trees. When data are inserted or removed from a node, it's number of child nodes changes. In order to maintain the pre-defined range nodes may be joined or split. Because a range of child nodes are permitted, muliway-trees do not need re-balancing as frequently as other self-balancing search trees, but may waste some space, since nodes are not entirely full.
Multi-Way Tree Implementations
CS2: Data Structures
Theory of Computation - ADT Preliminaries
Linear ADTs - Tree ADTs - Graph ADTs - Unordered Collection ADTs
