Definition:Rooted Tree

From ProofWiki
Jump to navigation Jump to search

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:

RootedTree.png

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 \left\{{r_T}\right\} \to T$ be the mapping defined by:

$\pi \left({t}\right) := \text{the node adjacent to $t$ on the path to $r_T$}$


Then $\pi \left({t}\right)$ 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$.

This path is indeed unique, by Path in Tree is Unique.


Proper Ancestor

A proper ancestor node of $t$ is an ancestor node of $t$ that is not $t$ itself.


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:

$\left\{{s \in T: \pi \left({s}\right) = t}\right\}$

where $\pi \left({s}\right)$ denotes the parent mapping of $s$.

That is, the children of $t$ are all the nodes of $T$ of which $t$ is the parent.


Grandchild Node

A child of a child node of a node $t$ can be referred to as a grandchild node of $t$.

In terms of the parent mapping $\pi$ of $T$, a grandchild node of $t$ is a node $s$ such that:

$\pi \left({\pi \left({s}\right)}\right) = t$


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.


Proper Descendant

A proper descendant node of $t$ is a descendant of $t$ which is not $t$ itself.


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 \left\{{r_T}\right\}$ is in $\Gamma$
$(3): \quad$ Each node in $\Gamma$ either:
$(a): \quad$ is a leaf node of $T$
or:
$(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


Sources

For their purposes, they refer to this concept just as a tree: they have no use for the unrooted version.