\documentstyle{article}
\begin{document}

\newtheorem{definition}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}

\begin{center}
{\bf\huge Trees}\hfill
\parbox{2in}{\flushright
  {\em Burton Rosenberg}\\
  {\em Dept. of Math and Comp. Sci.}\\
  {\em University of Miami}
}
\end{center}

Let $N$ be a finite set of elements called {\em nodes},
let $\bot$ be an element not in $N$. The element $\bot$
is called {\em bottom} by logicians, the {\em empty
element} by mathematicians, and {\em null} by computer
scientists.

\begin{definition}[Tree]
A tree is the collection,
\[ ( N, \lambda,\rho:N\rightarrow N\cup\{\bot\} )\]
which satisfies the Unique Path Property.
\end{definition}

{\noindent\sc Standard Terminology: }
Given $n,m\in N$, if $\lambda(n)=m$, then $m$ is said
to be the {\em left child} of $n$; if $\rho(n)=m$, then
$m$ is said to be the {\em right child} of $n$.
We shall see that it is not possible that for $n,n',m\in N$
that $\lambda(n) = \rho(n') = m$. That is, a node is
either a left or a right child, not both. Also, there is
exactly one node which is not a child of any $n\in N$.
This node is called the {\em root}.
A node $n\in N$ such that $\lambda(n)=\rho(n)=\bot$ is
called a {\em leaf} of the tree. A leaf is a node without
children.

\begin{definition}[Path]
A path is a relation $\rightarrow^*$ between nodes defined as
follows:
\begin{itemize}
\item $n\rightarrow^0 m \iff n=m.$ This is called the empty path.
   It has length 0.
\item $n\rightarrow^1 m \iff \lambda(n)=m \lor \rho(n)=m.$ This
   path has length 1. It is also written without superscript:
   $n\rightarrow m$.
\item $n\rightarrow^i m \iff n\rightarrow n' \rightarrow^{i-1} m$
   for $i>1.$ This inductively defines paths of length $i$.
\item $\rightarrow^* = \cup_{i\ge 0} \rightarrow^i$. That is,
   $\rightarrow^*$ is the transitive closure of $\rightarrow.$
\end{itemize}
\end{definition}

\begin{definition}[Unique Path Property]
The structure $(N, \lambda, \rho)$ has the unique
path property if,
\[ \exists r\in N : \forall n\in N\; \exists ! r \rightarrow^* n\]
This $r$ is called a root of the tree.
\end{definition}

\begin{lemma}[Unique Root]
There is only one root in a tree.
\end{lemma}

{\noindent\sc Proof: } Else, for two distinct $r, r'\in N$
we have booth $r\rightarrow^* r'$ and $r'\rightarrow^* r$.
Hence, the path from $r$ to $r$ is not unique:
there is the empty path and the path 
$r\rightarrow^* r' \rightarrow^* r$.

\begin{lemma}[Unique Parents]
For any $n\in N$ with $n\ne r$ there is exactly
one $m$ such that $m \rightarrow n$. This $m$ is said to
be the parent of $n$. The root has no parent.
\end{lemma}

{\noindent\sc Proof: }
Distinct parents $m,m'\in N$ exist such that 
$m\rightarrow n$ and $m'\rightarrow n$ would imply distinct
paths $r \rightarrow^* m \rightarrow n$ and 
$r \rightarrow^* m' \rightarrow n$. Hence any node has
at most one parent. By the unique path property, if
$n$ is not the root, the path from $r$ to $n$ is not empty,
hence there is a parent for $n$. However, if $m \rightarrow r$
for any $m\ne r$, then the loop $r\rightarrow^* m\rightarrow r$
would show multiple paths from $r$ to $r$.

~\\
{\noindent\sc Standard Terminology: }
Often a tree is defined as a {\em connected acyclic graph}.
A graph is a node set and a set of edges each of which connect
a pair of nodes.
In our development, $n\rightarrow m$ means that the pair $(n,m)$
is an edge. A path in a graph is a sequence of edges of the
form $(n_0,n_1),(n_1,n_2),\ldots,(n_{k-1},n_k)$. Our paths
are directed versions of these paths. We are required to walk
our paths consitently from parent to child. A cycle in a
graph is a path which begins and ends at the same node, that is,
$n_0=n_k$, in the notation of the example path directly above.
An acyclic graph is a graph without cycles.
A graph is connected if there is at least one path between
any two nodes in the graph.

This is equivalent to our defintion. Given a cycle in a graph
which comes from our tree, assign the proper ``arrows'' by
walking around the cycle. The Unique Parents lemma assures
that either a clockwise or counterclockwise promenade will
lead us fully around the cycle. Now select a node on the cycle
and demonstrate mutiple paths from the root to this node, by
appending to the shortest path from the root to the node additional
journeys around the cycle.

\begin{definition}[Descendant, Ancestor]
Given $n,m\in N$, $n\rightarrow^* m$ then $m$ is said to
be a descendant of $n$, and $n$ an ancestor of $m$.
\end{definition}

\begin{lemma}[Partial Order]
The relationship of descendant is a partial order.
\end{lemma}

{\noindent\sc Proof: } 
The three properties of partial orders must be verified:
\begin{enumerate}

\item For any $n\in N$, $n\rightarrow^* n$ by definition.

\item For any $n,m\in N$, $n\rightarrow^* m$ and
$m \rightarrow^* n$ implies if $n=m$. If not, there are at
least two paths from the root $r$
to $n$, $r\rightarrow^* n$ and
$r \rightarrow^*n \rightarrow^* m \rightarrow^* n$.

\item
If $n\rightarrow^* m$, and $m\rightarrow^* l$, then
$n\rightarrow^* l$. This path from $n$ to $l$ exists: 
$n\rightarrow^* m\rightarrow^* l$.

\end{enumerate}

We define the {\em left descendants} $L$ of a node $n\in N$ to
be the set of descendants of the left child of $n$.
\[ m\in L(n) \mbox{ if exists } n'\in N,\; \lambda(n)=n', \mbox{ and }
n' \rightarrow^* m.\]
The set $R$ of {\em right descendants} is defined similarly.

Let $S$ be a set with a {\em Total Ordering} $\le$. The set
$S$ labels of the nodes if there is a function $l:N\rightarrow S$.

\begin{definition}
A tree has the search tree property if for all $n\in N$,
for all $n_L\in L(n)$ and $n_R\in R(n)$, $l(n_L) < l(n)$
and $l(n) \le l(n_R).$
\end{definition}

{\noindent\bf Use of the Search Tree Property}

We will find the node $n\in N$ in the tree with label $s\in S$,
that is $l(n)=s$. We will assume that such a node exists. That
is, we are not looking for something which is not at all in the
tree. Let $r$ be the root of the tree. We will use the
working variable $n$ in the search:
\begin{verbatim}
   n = r ;
   while ( l(n) != s )
   {
       if ( l(n) < s ) 
          n = rightChild(n) ;
       else /* l(n) > s, of course! */
          n = leftChild(n) ;
   }
\end{verbatim}


\end{document}