Definition:Rooted Tree
Definition
A rooted tree is a tree with a countable number of nodes, in which a particular node is distinguished from the others and called the root node:
Root Node
Let $T$ be a rooted tree.
The root node of $T$ is the node of $T$ which is distinguished from the others by being the ancestor node of every node of $T$.
Parent
Let $T$ be a rooted tree whose root is $r_T$.
Let $t$ be a node of $T$.
From Path in Tree is Unique, there is only one path from $t$ to $r_T$.
Let $\pi: T \setminus \set {r_T} \to T$ be the mapping defined by:
- $\map \pi t := \text {the node adjacent to $t$ on the path to $r_T$}$
Then $\map \pi t$ is known as the parent node of $t$.
The mapping $\pi$ is called the parent mapping.
Ancestor
Let $T$ be a rooted tree with root $r_T$.
Let $t$ be a node of $T$.
An ancestor node of $t$ is a node in the path from $t$ to $r_T$.
Child Node
Let $T$ be a rooted tree with root $r_T$.
Let $t$ be a node of $T$.
The child nodes of $t$ are the elements of the set:
- $\set {s \in T: \map \pi s = t}$
where $\map \pi s$ denotes the parent mapping of $s$.
That is, the children of $t$ are all the nodes of $T$ of which $t$ is the parent.
Descendant
Let $T$ be a rooted tree with root $r_T$.
Let $t$ be a node of $T$.
A descendant node $s$ of a $t$ is a node such that $t$ is in the path from $s$ to $r_T$.
That is, the descendant nodes of $t$ are all the nodes of $T$ of which $t$ is an ancestor node.
Sibling
Let $T$ be a rooted tree with root $r_T$.
Two children of the same node of $T$ are called siblings.
That is, siblings are nodes which both have the same parent.
Leaf Node
Let $v$ be a node of a tree $T$.
Then $v$ is a leaf node of a $T$ if and only if $v$ is of degree $1$.
If $T$ is a rooted tree, this is equivalent to saying that $v$ has no child nodes.
Branch
Let $T$ be a rooted tree with root node $r_T$.
A subset $\Gamma$ of $T$ is a branch if and only if all the following conditions hold:
- $(1): \quad$ The root node $r_T$ belongs to $\Gamma$
- $(2): \quad$ The parent of each node in $\Gamma \setminus \set {r_T}$ is in $\Gamma$
- $(3): \quad$ Each node in $\Gamma$ either:
- $\text {(a)}: \quad$ is a leaf node of $T$
- or:
- $\text {(b)}: \quad$ has exactly one child node in $\Gamma$.
Also known as
In some contexts, in which only a rooted tree would make sense, the term tree is often used.
Also see
- Results about rooted trees can be found here.
Sources
- 1996: H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability ... (previous) ... (next): $\S 1.7$: Tableaus
- For their purposes, they refer to this concept just as a tree: they have no use for the unrooted version.