Hierarchy

• A system in which entities are ranked one above each other.
• A Classification of entities following a scheme of importance
• One entity includes its children entities in a containment hierarchy

Definitions

A Hierarchy is a Tree with:

• successor → child
• predecessor → parent
• root node
• leaves → node of degree 1
• inner nodes
• a tree level (length of path to root node)
• Out-Degree is number of children
• Siblings → same parent
• height of node (length of longest path to leave)
• depth of node (tree level, or length of path to root node)
• height of tree → height of root node or depth of deepest leaf node
• ordered tree → children have fixed left-to-right order
• subtrees are trees
• degree of tree is max degree of all nodes
• a tree is always Planar Graph
• binary tree → out degree at most 2
• Spanning Tree
• rooted tree
• directed acyclic graph (DAG)
• Forest
• MST-Algorithmus von Prim, MST-Algorithmus von Kruskal
• Depth-first search, Breadth-first search → pre-order, post-order, in-order