Discrete Mathematics Tree

Tree all part

1. Introduction to Tree Fundamental data storage structures used in programming. Combines advantages of an ordered array and a linked list. Searching as fast as in ordered array. Insertion and deletion as fast as in linked list.

2. Tree (example) node edge Draw a parse tree

3. Tree characteristics Consists of nodes connected by edges . Nodes often represent entities (complex objects) such as people, car parts etc. Edges between the nodes represent the way the nodes are related. Its easy for a program to get from one node to another if there is a line connecting them. The only way to get from node to node is to follow a path along the edges.

4. Tree Terminology Path: Traversal from node to node along the edges results in a sequence called path. Root: Node at the top of the tree. Parent: Any node, except root has exactly one edge running upward to another node. The node above it is called parent. Child: Any node may have one or more lines running downward to other nodes. Nodes below are children. Leaf: A node that has no children. Subtree: Any node can be considered to be the root of a subtree, which consists of its children and its children’s children and so on.

5. Tree Terminology Visiting: A node is visited when program control arrives at the node, usually for processing. Traversing: To traverse a tree means to visit all the nodes in some specified order. Levels: The level of a particular node refers to how many generations the node is from the root. Root is assumed to be level 0. Keys: Key value is used to search for the item or perform other operations on it.

6. Leaf A vertex is called a leaf if it has no children. 6

7. 7 Owner Jake Manager Brad Chef Carol Waitress Waiter Cook Helper Joyce Chris Max Len Leaf nodes have no children LEAF NODES

8. 8 Owner Jake Manager Brad Chef Carol Waitress Waiter Cook Helper Joyce Chris Max Len A Subtree LEFT SUBTREE OF ROOT ROOT

9. 9 Owner Jake Manager Brad Chef Carol Waitress Waiter Cook Helper Joyce Chris Max Len Another Subtree RIGHT SUBTREE OF ROOT ROOT

10. m -ary trees A rooted tree is called an m-ary tree if every internal vertex has no more than m children. The tree is called a full m-ary tree if every internal vertex has exactly m children. An m -ary tree with m =2 is called a binary tree .

11. Ordered Rooted Tree An ordered rooted tree is a rooted tree where the children of each internal vertex are ordered. Ordered trees are drawn so that the children of each internal vertex are shown in order from left to right.

12. Properties of Trees A tree with n vertices has n-1 edges.

13. Properties of Trees A full m -ary tree with i internal vertices contains n = mi +1 vertices.

14. Properties of Trees A full m -ary tree with ( i ) n vertices has i = ( n -1)/ m internal vertices and l = [( m -1) n +1]/ m leaves. ( ii ) i internal vertices has n = mi + 1 vertices and l = ( m -1)i + 1 leaves. ( iii ) l leaves has n = ( ml - 1)/( m -1) vertices and i = ( l -1)/( m -1) internal vertices.

15. Proof We know n = mi+1 (previous theorem) and n = l+i, n – no. vertices i – no. internal vertices l – no. leaves For example, i = (n-1)/m

16. Properties of Trees The level of a vertex v in a rooted tree is the length of the unique path from the root to this vertex. level 2 level 3

17. Properties of Trees The height of a rooted tree is the maximum of the levels of vertices.

18. Properties of Trees A rooted m -ary tree of height h is called balanced if all leaves are at levels h or h -1.

19. Properties of Trees There are at most m h leaves in an m -ary tree of height h .

20. Properties of Trees If an m -ary tree of height h has l leaves, then

21. Proof From previous theorem:

22. Minimum Spanning Tree Input: A connected, undirected graph G = ( V , E ) with weight function w : E  R . For simplicity, we assume that all edge weights are distinct. Output: A spanning tree T, a tree that connects all vertices, of minimum weight:

23. Example of MST 6 12 5 14 3 8 10 15 9 7

24. Kruskal ’ s Algorithm It is a greedy algorithm. In Kruskal ’ s algorithm, the set A is a forest. The safe edge is added to A is always a least-weight edge in the graph that connects two distinct Components.

25. Kruskal ’ s Algorithm The operation FIND-SET(u) returns a representative element from the set that contains u. Thus we can determine whether two vertices u and v belong to the same tree by testing whether FIND-SET(u) = FIND-SET(v) The combining of trees is accomplished by the UNION procedure

26. Kruskal ’ s Algorithm 1 . A   2. for each vertex v Î V[G] do MAKE-SET(v) short the edges of E into non-decreasing order by weight. for each edge (u, v) Î E, taken in non-decreasing order by weight. do if FIND-SET(u) != FIND-SET(v) then, A  A U {(u, v)} UNION(u, v) return A