multitree

Multitree is a term used in computer science and mathematics to describe a class of hierarchical structures that generalize the notion of a tree. In broad usage, a multitree refers to a directed acyclic graph that represents multiple hierarchies that can share substructures, rather than a single, strictly hierarchical tree. The defining feature is that nodes may participate in more than one hierarchical path, enabling subtrees to be reused by several branches. Because definitions vary by field, multitree is not a single universal formal concept.

Variants and related concepts: In probabilistic graphical models, a poly-tree or polytree is a directed acyclic graph whose underlying undirected graph is a tree; some authors use multitree as a synonym or informal variant of poly-tree. In data management and knowledge representation, multitrees describe structures where different trees are merged by identifying identical substructures, enabling shared subtrees and reducing duplication.

Properties and operations: A multitree is acyclic, but path structure can be more complex than in a simple tree. Standard tree algorithms (for example, simple top-down traversals) may need adjustments to handle multiple parents or shared subgraphs. Queries about ancestry and path counting require care to avoid double-counting shared nodes.

Applications: Multitree concepts appear in version control histories, dependency graphs, syntax and dataflow representations, and knowledge bases that support inheritance with shared components. See also related terms such as tree, forest, directed acyclic graph, poly-tree, and DAG.