1. What is a tree

What is a tree?

Tree

A tree is a connected simple graph with no simple cycles.

• In a tree, there is a unique simple path between any two of its vertices.
• If we add an edge to a tree, it creates a cycle.
• If we remove an edge from a tree, it becomes not connected.

graph G {
	layout=neato
	node[shape=point]
	4--1,2,3,5
	5--6,7,8
	8--9,10,11
}

Link to original

Link to original

3. Applications of trees

Applications of trees

Trees can be used for modelling and problem solving.

• Family trees in genealogy
• Representing organisations
• Computer file systems
• Constructing efficient methods for locating items in a list Binary search trees
• Game trees to analyse winning strategies in games
• Decision trees
• Decomposition trees to parse arithmetical and logic formulas and expressions

Link to original

5. Special trees

Special Trees

A rooted tree is called an $m$-ary tree if every internal vertex has no more than $m$ children.

A rooted tree is called a full $m$-ary tree if every internal vertex has exactly $m$ children.

Binary Trees

A rooted tree is called a full binary tree if every internal vertex has exactly $2$ children: a left child and a right child

graph G {
	label="full binary tree"
	node[shape="point"]
	
	1--2,3
	2--4,5
	5--6,7
}

When we have a full binary tree of height $n$:

• the left and right subtrees of the root are both full binary trees of height $\le n-1$
• at least one of the left and right subtrees of the root is a full binary tree of height $n-1$

Counting vertices and edges of trees

A full binary tree with $n$ internal vertices contains $2n-1$ vertices altogether. Every vertex, except the root, is the child of an internal vertex. Because each of the $n$ internal vertices has $2$ children, there are $2n$ vertices in the tree other than the root.

A full $m$-ary tree with $n$ internal vertices contains $m\cdot n+1$ vertices altogether. Every vertex, except the root, is the child of an internal vertex. Because each of the $n$ internal vertices has $m$ children, there are $m\cdot n$ vertices in the tree other than the root.

Link to original

7. Decomposition trees

Decomposition Trees

We can represent complicated expressions, like formulas of propositional logic and arithmetical expressions using rooted trees.

For example we can represent the formula $(\neg (p\wedge q)⟺(\neg p\vee \neg q))$ as:

graph G {
	graph [nodesep="0.6"]
	node[shape=plain]
 
	r[label="↔"]
	1[label="¬"]
	2[label="∧"]
	3[label="p"]
	4[label="q"]
	5[label="∨"]
	6[label="¬"]
	7[label="¬"]
	8[label="q"]
	9[label="p"]	
	
	r--1,5
	1--2
	2--3,4
 
	5--6,7
	6--9
	7--8
}

Notice subgraphs here represent parts of the equation:

graph G {
	graph [nodesep="1"]
	node[shape=plain]
 
	r[label="↔"]
	1[label="¬"]
	2[label="∧"]
	3[label="p"]
	4[label="q"]
	5[label="∨"]
	6[label="¬"]
	7[label="¬"]
	8[label="q"]
	9[label="p"]	
	
	r--1,5
	
	subgraph cluster0 {
		label="¬(p∧q)"
		1--2
		
		subgraph cluster2 {
			label="p∧q"
			2--3,4
		}
	}
	
	subgraph cluster1 {
		label="¬p∨¬q"
		5--6,7
		
		subgraph cluster3 {
			label="¬p"
			6--9
		}
		
		subgraph cluster4 {
			label="¬q"
			7--8
		}
	}
}

Link to original

8. Linearly ordered lists

Linearly ordered lists

Linearly ordered list

Linearly ordered list is a sequence whose elements are linearly ordered (linear order), which is not necessarily the order of listing.

For example:

• A list of natural numbers can be ordered by the $\le$ relation.
• A list of words can be ordered by the lexicographical order relation, $\prec$. As below.

Link to original

Searching for items in a linearly ordered list is important and Binary search trees are particularly useful in representing elements in such a list. There are very efficient methods for:

• searching for data in binary search trees
• revising data in binary search trees
• converting linaerly ordered lists to binary search trees and back

title: Example: lexicographical order on words
First, we order the letters of the English alphabet as usual:
 
$$
	a \prec b \prec c \prec d \prec e \prec ... \prec x \prec y \prec z
$$
 
Then, we can use this ordering of the letters to order longer words:
- Given two words $w_1$ and $w_2$, we compare them letter by letter, from left to right, passing equal letters.
- If at any point a letter in $w_1$ is $\prec$-smaller than the corresponding letter in $w_2$, then we put $w_1 \prec w_2$.
- If every letter in $w_1$ is equal to the corresponding letter in $w_2$ but $w_2$ is longer than $w_1$, then we also put $w_1 \prec w_2$.
- In any other case, we put $w_2 \prec w_1$.
 
$$
	\text{discreet} \prec \text{discreetness} \prec \text{discrete} \prec \text{discretion} \prec \text{geography}
$$
$$
	 \prec \text{geology} \prec \text{mathematics} \prec \text{physics} \prec \text{psychology}
	 $$

Link to original

9. Binary search trees

Binary search trees

Given two things: a list of $\boxed{L}$ items and a linear order $\boxed{\prec }$ on them. A binary search tree for $L$ and $\prec$ is a binary tree in which every vertex is labelled with an item from $L$ such that we have:

1. the label of each vertex:
   • is $\prec$-greater than the labels of all vertices in the left subtree
   • is $\prec$-less than the labels of all vertices in its right subtree
2. every path in the tree be compatible with the order of listing:

   graph G {
    layout=neato
   	node[shape=point]
    
    a[xlabel="5" pos="2,4!"]
    b[xlabel="3" pos="1,3!"]
    c[xlabel="128" pos="3,3!"]
    d[xlabel="2" pos="0.5,2!"]
    e[xlabel="4" pos="1.5,2!"]
    f[xlabel="15" pos="2.5,2!"]
    g[xlabel="20" pos="3,1!"]
    
    a--b,c
    b--d,e
    c--f
    f--g
   }

   For the list $(5,128,3,2,15,4,20)$ and linear order $\le$.

Binary Tree from Linearly ordered list

We are given a list $L$ of items, and a linear order $\prec$ on them. We go through each member of the list, from left to right:

• First item: becomes our root
• Comparing: We take the next item in the list, and first compare it with the labels of the ‘old’ vertices already in the list, starting from the root then:
  • moving to the left: if the new item is $\prec$-less than the label of the respective ‘old’ vertex, if this ‘old’ vertex has a left child, or:
  • moving to the right: if the new item is $\prec$-greater than the label of the respective ‘old’ vertex, if this ‘old’ vertex has a right child.
• Adding:
  • When the new item is $\prec$-less than the label of an ‘old’ vertex and the vertex has no left child, insert a new left child to the ‘old’ vertex and label it with the new item.
  • When the new item is $\prec$-larger than the label of an ‘old’ vertex and the vertex has no child, then we insert a new right child to the ‘old’ vertex and label it with the new item.

Example BST

Build a binary search tree for the following list of words using the lexicographical order $\boxed{\prec }$.

$$\boxed{\text{mathematics, physics, geography, zoology, meteorology, geology, psychology}}$$

1. Take mathematics and label the root with it:

   graph G {
   	m[shape=point xlabel=mathematics]
   }

2. We take physics and compare it with mathematics, $\text{mathematics}\prec \text{physics}$, mathematics has no right child so we label a new right child with physics:

   graph G {
   	layout=neato
    node[shape=point]
   	m[xlabel=mathematics pos="0,0!"]
    p[xlabel=physics pos="1,-1!"]
    
    m--p
   }

3. We take geography, $\text{geography}\prec \text{mathematics}$, mathematics has no left child so we create a new left child with geography:

   graph G {
   	layout=neato
    node[shape=point]
   	m[xlabel=mathematics pos="0,0!"]
    p[xlabel=physics pos="1,-1!"]
    g[xlabel=geography pos="-1,-1!"]
    
    m--p,g
   }

4. We take zoology, $\text{mathematics}\prec \text{zoology}$, so we move to the right child of the root and take the label, which in this case is physics.
5. We now compare zoology with physics, $\text{physics}\prec \text{zoology}$, physics has no right child, hence we label a new right child:

   graph G {
   	layout=neato
    node[shape=point]
   	m[xlabel=mathematics pos="0,0!"]
    p[xlabel=physics pos="1,-1!"]
    g[xlabel=geography pos="-1,-1!"]
    z[xlabel=zoology pos="1.5,-2!"]
    
    m--p,g
    p--z
   }

6. We take meteorology, $\text{mathematics}\prec \text{meteorology}$, so we move to the right child of the root and take the label, which in this case is physics.
7. We now compare zoology with physics, $\text{meteorology}\prec \text{physics}$, physics has no left child, hence we label a new left child:

   graph G {
   	layout=neato
    node[shape=point]
   	m[xlabel=mathematics pos="0,0!"]
    p[xlabel=physics pos="1,-1!"]
    g[xlabel=geography pos="-1,-1!"]
    z[xlabel=zoology pos="1.5,-2!"]
    2[xlabel=meteorology pos="0.5,-2!"]
    
    m--p,g
    p--z,2
   }

8. We take geology, $\text{geology}\prec \text{mathematics}$, so we move to the left child of the root and take the label, which in this case is geography.
9. We now compare geology with geography, $\text{geography}\prec \text{geology}$, physics has no right child, hence we label a new right child:

   graph G {
   	layout=neato
    node[shape=point]
   	m[xlabel=mathematics pos="0,0!"]
    p[xlabel=physics pos="2,-1!"]
    g[xlabel=geography pos="-2,-1!"]
    z[xlabel=zoology pos="2.5,-2!"]
    2[xlabel=meteorology pos="1.5,-2!"]
    3[xlabel=geology pos="-1.5,-2!"]
    
    m--p,g
    p--z,2
    g--3
   }

10. Finally, we take psychology, compare it with mathematics, move to the right, compare it with physics, move to the right then compare it with zoology, $\text{psychology}\prec \text{zoology}$, hence create a new left child:

    graph G {
    	layout=neato
     node[shape=point]
    	m[xlabel=mathematics pos="0,0!"]
     p[xlabel=physics pos="2,-1!"]
     g[xlabel=geography pos="-2,-1!"]
     z[xlabel=zoology pos="2.5,-2!"]
     2[xlabel=meteorology pos="1.5,-2!"]
     3[xlabel=geology pos="-1.5,-2!"]
     4[xlabel=psychology pos="2,-3!"]
     
     m--p,g
     p--z,2
     g--3
     z--4
    }

Say we had to add a new word, chemistry, to our BST. How many comparisons do we need to locate or find it?

In this case, it’s just $2$. We compare it with mathematics, move left, compare it with geography. As $\text{chemistry}\prec \text{geography}$ and geography has no left child, we know that chemistry is not in the tree. We can create a new left child and label it as such.

graph G {
	layout=neato
	node[shape=point]
	m[xlabel=mathematics pos="0,0!"]
	p[xlabel=physics pos="2,-1!"]
	g[xlabel=geography pos="-2,-1!"]
	z[xlabel=zoology pos="2.5,-2!"]
	2[xlabel=meteorology pos="1.5,-2!"]
	3[xlabel=geology pos="-1.5,-2!"]
	5[label=chemistry pos="-2.5,-2!" shape="plain"]
	4[xlabel=psychology pos="2,-3!"]
 
	m--p,g
	p--z,2
	g--3
	z--4
	g--5
 
	subgraph cluster0 {
		5
	}
}

Link to original

10. Tree traversal algorithms

Tree traversal

Rooted trees are often used to store information. We use different systematic approaches to visit each vertex of a rooted tree to access data, called traversal algorithms.

Common traversal algorithms:

• Preorder traversal: visit the root, continue traversing subtrees in preorder, from left to right
• Inorder traversal: begin traversing leftmost subtree inorder, then visit root, then continue traversing subtrees in inorder, from left to right
• Postorder traversal: begin traversing leftmost subtree in postorder, then continue traversing subtrees in postorder, from left to right, finally visit root

Link to original