Wurzelbäumen

Wurzelbäumen (German for "rooted trees") are trees in graph theory and computer science that have a distinguished vertex called the root. Each edge implicitly orients away from the root, establishing parent–child relationships that define ancestors, descendants, leaves (vertices with no children), depth (distance from the root) and height (maximum depth). Rooted trees may be ordered (children have a left-to-right sequence) or unordered, and may be labeled or unlabeled; common special cases include binary trees and k-ary trees.

In combinatorics and enumeration, rooted trees are a central object. Cayley’s formula counts labeled trees on n vertices as n^{n-2}; choosing a root multiplies this by n, giving n^{n-1} rooted labeled trees. Enumeration of unlabeled rooted trees involves more intricate generating-function techniques and asymptotic results (Otter’s theorem). Representations such as Prüfer sequences and parent arrays facilitate counting and encoding.

In computer science, rooted trees model hierarchical data and enable efficient algorithms: syntax trees and abstract syntax trees in compilers, DOM trees in web documents, file system hierarchies, and search trees (binary search trees, AVL, red–black). Standard operations include traversals (preorder, inorder, postorder, level-order), insertion, deletion and rebalancing. In biology and linguistics, rooted trees appear as phylogenetic and derivation trees to represent ancestry and structure.

The study of rooted trees intersects graph theory, combinatorics, algorithm design and applications across disciplines, providing both theoretical insights and practical data structures for hierarchical information.