Heap

Trees

Definition

 We call a connected undirected graph without cycles a tree.

Properties of trees

Theorem 1

 Let G=(V,U) be an undirected graph. The following statements are equivalent:
- G is a tree
- Any two vertices in G are joined by a unique simple chain
- G is minimally connected (if we suppress an edge, the resulting graph is disconnected)
- G is connected and has |V|-1 edges
- G is acyclic and has |V|-1 edges
- G is maximally acyclic (if we add an edge, the resulting graph contains cycles)

Introductory Notions

  1. Trees
  2. Binary trees
  3. Heaps

Min-Heap generator

Heap

  1. Creation
  2. Insert node
  3. Combination
  4. Extract node

Priority queue

Applications

Dictionary

Theorem 2

 The integers 0 <= d1 <= d2 <= ... <= dn (n>=2) are the degrees of the vertices of a tree if and only if d1+d2+...+dn = 2*n-2.

Rooted trees

Definition

 A rooted tree is a finite set of nodes that is either empty or:
- there is a special node called the root of the tree
- the set of other nodes is partitioned into n>=0 classes A1, A2, ..., An, each class being a rooted tree. The root of the tree is joined by edges of tree roots A1, A2, ..., An.