# Trees

**Tree:**a relation in which there is a uniqiue path from the root to the other vertexes**Root $v_0$**: the root node- Rooted tree: $(T, v_0)$:

- Geometic properties
- $v_0$ is the only root of $T$
- Tree's have cycles
- $v_0$ has in-degree 0, $v != v_0$ has in-degree 1

- Relational properties
- Irreflexive
- Assymmetric
- Not transitive (inverse of transitive)

- Terminology
- Level: steps from root node, starts at zero
- Height: number of largest level
- Siblings: nodes with the same parent
- Leaves: nodes that have no children
- Ancestors: all connections upwards
- Descendants: all connetions downards

**n-tree/n-ary tree**: each vertex has at most n children**Complete n-tree**: each vertex has exactly n children (except for the leaves)**Binary tree**: name for 2-trees

**Positional tree**: positive integers as child positions $1, ..., n$ (ordered)**Labeled trees**: each node has a label attached to it**Subtree**- $B_v$ set of all decendatns of $v$
- Subtree: $T(v) = T \cap (B_v \times B_v$ restriction of $T$ to $B_v$
- Is also a tree

## Examples/applications of trees #

**Syntax tree**: used in compilers and calculators- Draw by reading from outside to the inside

**Huffman code**: follow edges in order of bits until you get to a label, repeat from the root node until all bits are decoded- Binary search tree
- Tries/prefix trees
- Character encoding

## Tree search #

**Linked-list representation**: method to create a binary tree from a general tree to apply search on it

- Left edges: relations from parent to first child.
- Right edges: the siblings (in order of the tree).

### Depth-first search (DFS) #

On a binary tree, in which: Node (N), Left (L), Right (R):

- Preorder search (NLR)
- Inorder search (LNR)
- Postorder search (LRN)

## Undirected trees #

**Undirected tree**: the symmetric closure of a tree**Undirected edge**: $\{a, b\}$ = $(a, b), (b, a)$**Graphs**instead of**digraphs**(lines represent undirected edges)**Adjacent**: a and b are adjacent if there is an undirected edge between them

## Spanning Trees #

Let $R$ be a **symmetric connected** relation:

**Spanning tree**: exactly the vertices of $R$, can be obtained by deleting edges from $R$**Weighted graphs**: graph in which every edge has a**weight****Undirected spanning tree**: the symmetric closure of a spanning tree**Minimal spanning tree**: an undirected spanning tree for which the weight is minimal- Algorithms:
**Prim's algorithm**: adds one vertex at a time and checks for minimality**Kruskal's algorithm**: sort edges by weight and add one edge at a time and check for**acyclicity**