[Discrete Mathematics] Trees

NOTE: 현업에서 이진 트리 개념이 사용되는 사례 (링크)

1. Spanning Tree

A tree T is a spanning tree of a graph G if T is a subgraph of G that contains all of the vertices of G.

• Every connected graph has a spanning tree.
• Any two spanning trees for a graph have the same numbers of the edges.

• A graph G has a spanning tree if and only if G is connected.

The graph G has one circuit v2-v1-v4-v2, and removal of any edge of the circuit gives a tree. Thus, as shown below, there are three spanning trees for G.

Spanning tree search method

• BFS : process all the vertices on a given level before moving to the next-higher level
• DFS : proceeds to successive levels in a tree at the earliest possible opportunity (Backtracking)

(1) BFS

bfs(V, E) {
// V = vertices ordered v1,..., vn; E = edges
// V′ = vertices of spanning tree T; E′ = edges of spanning tree T
// v1 is the root of the spanning tree
// S is an ordered list
	S = (v1)
	V′ = {v1}
	E′ = ∅
	while (true) {
		for each x ∈ S, in order,
			for each y ∈ V − V′, in order,
				if ((x, y) is an edge)
					add edge (x, y) to E′ and y to V′
		if (no edges were added)
			return T
		S = children of S ordered consistently with the original vertex ordering
	}
}

Process all the vertices on a given level before moving to the next-higher level.

Order: abcdefgh

1. select a (root)
2. add to T all edges (a,x) and vertices on which they are incident that do not produce a cycle when added to T.
3. repeat this procedure on level 1. (b, c, g)
4. repeat this procedure on level 2. (d, e)
5. repeat this procedure on level 3. (f)
6. repeat this procedure on level 4. (h)

(2) DFS

dfs(V, E) {
// V′ = vertices of spanning tree T; E′ = edges of spanning tree T
// v1 is the root of the spanning tree
	V′ = {v1}
	E′ = ∅
	w = v1
	while (true) {
		while (there is an edge (w, v) that when added to T does not create a cycle in T) {
			choose the edge (w, vk) with minimum k that when added to T does not create a cycle in T
			add (w, vk) to E′
			add vk to V′
			w = vk
		}
		if (w == v1)
			return T
		w = parent of w in T // backtrack
	}
}

Proceeds to successive levels in a tree at the earliest possible opportunity

Order: abcdefgh

1. Select a (root)
2. Add the edge (a, x), with minimal x, to our tree. (a, b)
3. Repeat this process. (b, d), (d, c), (c, e), (e, f), (f, h)
4. We cannot go further. We backtrack to the parent f of h and try to add an edge of the form (f, x) 
5. We cannot go further. We backtrack to the parent e of f and try to add an edge of the form (e, x).
   → Add (e, g)

Example

• 위 그래프를 BFS로 탐색하면, 순서는 1-2-3-4-5-6-7-8 순이 된다.

• 위 그래프를 DFS로 탐색하면, 순서는 1-2-5-3-8-6-4-7 순이 된다.

3과 8중에서는 더 작은 값인 3을 먼저 탐색

• 1 → 2 → 5 → 3
• 3에서 backtracking 발생 (5 → 8 → 6 → 4 → 7로 진행)
• 7과 인접하면서 탐색되지 않은 vertex가 없으므로 backtracking 발생 (4 → 6 → 8 → 5 → 2 → 1) 

---

2. Minimun Spanning Tree

Let G be a weighted graph. A minimal spanning tree of G is a spanning tree of G with minimum weight.

For a weighted graph G, there are two spanning trees, T and T'. T' with weight 20 is not a minimal spanning tree since spanning tree T has weight 12. We will see later that T is a minimal spanning tree for G.

MST search algorithms

• Prim's Algorithm : A example of Greedy algorithm
  • Greedy algorithm : 이전의 선택은 고려하지 않고 각각의 iteration에서 최적화시킴 → doing the best locally
• Kruskal’s algorithm

(1) Prim's algorithm

This algorithm finds a minimal spanning tree in a connected, weighted graph.

• Input: A connected, weighted graph with vertices 1,..., n and start vertex s. If (i, j) is an edge, w(i, j) is equal to the weight of (i, j); if (i, j) is not an edge, w(i, j) is equal to ∞ (a value greater than any actual weight).
• Output: The set of edges E in a MST

prim(w, n, s) {
	// v(i) = 1 if vertex i has been added to mst
	// v(i) = 0 if vertex i has not been added to mst
	for i = 1 to n
	v(i) = 0
	// add start vertex to mst
	v(s) = 1
	// begin with an empty edge set
	E = ∅
	// put n − 1 edges in the minimal spanning tree
	for i = 1 to n − 1 {
		// add edge of minimum weight with one vertex in mst and one vertex
		// not in mst
		min = ∞
		for j = 1 to n
			if (v(j) == 1) // if j is a vertex in mst
				for k = 1 to n
					if (v(k) == 0 ∧ w(j, k) < min) {
						add vertex = k
						e = (j, k)
						min = w(j, k)
	 				}
		// put vertex and edge in mst
		v(add vertex) = 1
		E = E ∪ {e}
	}
	return E
}

• min=w(i, j) : 하나의 vertex v(j)는 mst에 속하고 다른 vertex v(k)는 mst에 속하지 않는 edge w(j,k)중에서 최소치 edge 선택

• 각각의 반복에서 최적화하는 것이 항상 optimal solution은 아니다. → Greedy Algorithm의 한계

• Greedy Algorithm으로 MST : (a, c) (c, z), (z, b) → 11
• Prim’s Algorithm으로 MST : (a, c) (a, b), (b, z) →  7

Prim’s Algorithm is CORRECT; that is, at the termination of Prim's algorithm, T is a minimal spanning tree.

(2) Kruskal’s Algorithm

1. Find the edge in the graph with smallest weight (if there is more than one, pick one at random). 
   Mark it with any given color, say red.
   

   

2. Find the next edge in the graph with smallest weight that doesn't close a cycle. 
   Color that edge and the next incident vertex.
   

   

3. Repeat Step 2 until you reach out to every vertex of the graph. The chosen edges form the desired minimum spanning tree.
   

   

   1+2+2+2+3+4=14

Prim, Kruskal 알고리즘 둘 중 아무것이나 선택해서 풀어도 답은 동일하다.

---

3. Binary Tree

A binary tree is a rooted tree in which each vertex has either no children, one child, or two children. If a vertex has one child, that child is designated as either a left child or a right child (but not both). If a vertex has two children, one child is designated a left child and the other child is designated a right child.

• Full binary tree : a tree in which each vertex has either two children or zero children
• If T is a full binary tree with i internal vertices, then T has i + 1 terminal vertices and 2i + 1 total vertices.
• If a binary tree of height h has t terminal vertices, then log₂ t ≤ h.
  
  • Is there a binary tree that has height 5 and 38 terminal vertices?
    → No! any binary tree T with height 5 has at most 2⁵ = 32 terminal vertices, so such a tree cannot have 38 terminal vertices.

A binary search tree is a binary tree T in which data are associated with the vertices. The data are arranged so that, for each vertex v in T, each data item in the left subtree of v is less than the data item in v, and each data item in the right subtree of v is greater than the data item in v.

make bin search tree(w, n) {
	let T be the tree with one vertex, root
    store w1 in root
	for i = 2 to n {
		v = root
		search = true // find spot for wi
		while (search) {
			s = word in v
			if (wi < s)
				if (v has no left child) {
					add a left child l to v
					store wi in l
					search = false // end search
				}
				else
					v = left child of v
			else // wi > s
				if (v has no right child) {
					add a right child r to v
					store wi in r
					search = false // end search
				}
				else
					v = right child of v
		} // end while
	} // end for
	return T
}

---

4. Tree Traversal

(1) Preorder Traversal

preorder(PT) {
	if (PT == null)
		return
        
	process PT
	preorder(left child of PT)
	preorder(right child of PT)
}

(2) Inorder Traversal

inorder(PT) {
	if (PT == null)
		return

	inorder(left child of PT)
	process PT
	inorder(right child of PT)
}

(3) Postorder Traversal

postorder(PT) {
	if (PT == null)
		return

	postorder(left child of PT)
	postorder(right child of PT)
	process PT
}