Publish on 11th November 2019
Category: Birds
0

CSCI 115

Chapter 7Trees

CSCI 115

§7.1Trees

§7.1 – Trees

TREELet T be a relation on a set A. T is atreeif there exists a vertex v0in A s.t. there is a unique path from v0to every other vertex in A, but no path from v0to v0.

§7.1 – Trees

RootRooted tree (Notation: (T, v0))VertexParentOffspringSiblingsDescendantLevelsHeightLeaf

§7.1 – Trees

Theorem 7.1.1Let (T, v0) be a rooted tree. Then:i) There are no cycles in Tii) v0is the only root of Tiii) Each vertex in T other than v0hasin-degree 1 and v0has in-degree 0

§7.1 – Trees

Theorem 7.1.2Let (T, v0) be a rooted tree on a set A. Then:i) T is irreflexiveii) T is asymmetriciii) If (a,b) T and (b,c) T, then (a, c) T a, b, c T

§7.1 – Trees

Let n Z+. T is ann-Treeif every vertex in T has at most n offspring.If all vertices other than the leaves have exactly n offspring, T is said to be acomplete n-Tree.A 2-tree is called abinary tree, and a 3-tree is called atertiary tree.

§7.1 – Trees

Let(T, v0) be a rooted tree on A, with vT. Let B be the set of v and all of its descendents (BA). Then T(v) is the restriction of T to B.Theorem 7.1.3If (T, v0) is a rooted tree and v T then T(v) is also a rooted tree with root v. We say T(v) is a subtree of T beginning at v.

CSCI 115

§7.2Labeled Trees

§7.2 – Labeled Trees

Labeled TreesVertices labeled accordinglyPositional treesn-tree has at most n offspring per rootn ‘positions’Binary positional trees as Data StructuresDoubly linked lists

§7.2 – Labeled Trees

Procedure to find visual representation of computer representationConstruct doubly linked list representation.Create 4 arrays, each with one more element than there are vertices in T. Call the arrays Index, Left, Data, and Right.Fill in Index and Data arrays according to the linked list representation constructed in 1.Fill in the last 2 elements in each row, doing one row at the time.

CSCI 115

§7.3Tree Searching

§7.3 – Tree Searching

Tree searching (walking, traversing)Visiting each vertex in some specified orderVisit is defined accordinglyTerminology for binary treeVLis the left offspring of a vertex, VRis the right offspringIf VLexists, T(VL) is the left subtree of vIf VRexists, T(VR) is the right subtree of v

§7.3 – Tree Searching

Algorithms for searching binary treesPreorderPolish (prefix) notationResult is unambiguous (algebraically)InorderInfix notationResult is ambiguous(and less useful)PostorderPostfix (reverse polish) notationResult is unambiguous (algebraically)

§7.3 – Tree Searching

Binary tree search algorithm 1 – Preorder SearchVisit v0If vLexists, apply algorithm to T(vL)If vRexists, apply algorithm to T(vR)Evaluation of polish (prefix) notationMove left to right until a 3 byte string is found in the form Fxy where F is a binary operation, and x and y are numbers or variablesEvaluate xFy and substitute the answer for FxyRepeat until 1 number or an algebraic expression remains

§7.3 – Tree Searching

Binary tree search algorithm 2 – Inorder SearchIf vLexists, apply algorithm to T(vL)Visit v0If vRexists, apply algorithm to T(vR)Evaluation of infix notationSince the inorder search results in an ambiguous expression, there is no algorithm to evaluate it

§7.3 – Tree Searching

Binary tree search algorithm 3 – Postorder SearchIf vLexists, apply algorithm to T(vL)If vRexists, apply algorithm to T(vR)Visit v0Evaluation of reverse polish (postfix) notationMove left to right until a 3 byte string is found in the form xyF where F is a binary operation, and x and y are numbers or variablesEvaluate xFy and substitute the answer for xyFRepeat until 1 number or an algebraic expression remains

§7.3 – Tree Searching

Searching general trees (i.e. non binary trees)Any ordered tree T with A being the set of vertices can be represented by a binary treeB(T)by the following algorithmIf v A, then:vL(the left offspring) of v in B(T) is the 1stoffspring of v in T if it existsvR(the right offspring) of v in B(T) is the next sibling of v in T if it exists

§7.3 – Tree Searching

Searching general trees (i.e. non binary trees)Find binary representationApply desired search algorithm

CSCI 115

§7.4Undirected Trees

§7.4 – Undirected Trees

Undirected treeSymmetric closure of the corresponding treeTerminologyUndirected edgeAdjacent verticesSimple pathNo 2 edges correspond to the same undirected edgeSimple cycleSimple path that is also a cycleAcyclicContains no simple cyclesConnected

§7.4 – Undirected Trees

Theorem 7.4.1Let R by a symmetric relation on a set A. Then the following are equivalent (TFAE):i) R is an undirected treeii) R is connected and acyclic

§7.4 – Undirected Trees

Theorem 7.4.2Let R by a symmetric relation on a set A. R is an undirected tree iff either of the following is true:i) R is acyclic, and if any undirected edge isadded to R, the new relation is not acyclicii) R is connected, and if any undirected edge isremoved from R, the new relation is notconnected

§7.4 – Undirected Trees

Theorem 7.4.3A tree with n vertices has n – 1 edges

§7.4 – Undirected Trees

Spanning trees of connected relationsLet R be a symmetric connected relation on A. T is aspanning treefor R if T is a tree with the same vertices as R, and T can be obtained from R by deleting edges of R.Anundirected spanning treeis the symmetric closure of the corresponding spanning tree.

§7.4 – Undirected Trees

Algorithm for finding an undirected spanning tree for a symmetric connected relation R.Remove undirected edges from R until the removal of one more edge would result in disconnectionDisadvantage of this algorithmPerformance time – checking for connectedness

§7.4 – Undirected Trees

Prim’s Algorithm for finding a spanning tree for a symmetric connected relation R on a setA = {v1, v2, …, vn}Choose a vertex of v1in R and find MRs.t. the 1strow corresponds to v1.Choose a vertex v2of R s.t. (v1, v2) R. Mergev1&v2into a new vertexv1‘ representing {v1,v2} and replacev1byv1‘. Compute the matrix of the resulting relation R’. The vertexv1‘ is called a merged vertex.Repeat steps 1 & 2 on R’ and all subsequent relations until a relation with a single vertex is obtained. At each step, keep a record of the set of original vertices that is represented by each merged vertex.Construct the spanning tree as follows. At each stage, when merging vertices a & b, select an edge in R from one of the original vertices represented by a to one of the original vertices represented by b.

CSCI 115

§7.5Minimal Spanning Trees

§7.5 – Minimal Spanning Trees

Weighted graphGraph where each edge is labeled with a numerical value (its weight)Nearest neighbor of a vertexThe adjacent vertex the smallest distance awayNearest neighbor of a set of vertices VThe vertex adjacent to any member of V which is the smallest distance away (may be a member of V)Minimal spanning treeUndirected spanning tree for which the total weight of the edges is as small as possible

§7.5 – Minimal Spanning Trees

Prim’s Algorithm for finding a minimal spanning tree for a symmetric connected relation R on a setA = {v1, v2, …, vn}Choose a vertex of v1in R. Let V = {v1} and E = {}.Choose a nearest neighbor viof R that is adjacent to some vjof V and for which the edge (vi, vj) does not form a cycle with members of E. Add vito V and add (vi, vj) to E.Repeat step 2 until |E| = n – 1. Then V contains all n vertices of R, and E contains the edges of a minimal spanning tree for R.

§7.5 – Minimal Spanning Trees

Kruskal’s Algorithm for finding a minimal spanning tree for a symmetric connected relation R on a set A = {v1, v2, …, vn} whereS={e1, e2, …, ek} is the set of weighted edges of RChoose an edge e1in S of least weight. Let E = {e1}. Replace S with S – {e1}.Select an edge eiof S of least weight that will not make a cycle with members of E. Replace E with E {ei} and S with S - {ei}Repeat step 2 until |E| = n – 1. Then E contains the edges of a minimal spanning tree for R.

0

Embed

Upload

Math 115 - Heartland Community College