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

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