Trees JIT10503.pdf

Trees Nurzulaikha binti Mahd Ab.lah  Topics ❖ Introduction to trees ❖ Subtrees ❖ Matrices representative of trees Presentation title 2 Introduction ...

Trees Nurzulaikha binti Mahd Ab.lah  Topics ❖ Introduction to trees ❖ Subtrees ❖ Matrices representative of trees Presentation title 2 Introduction  Introduction Definition 1. A tree is a connected undirected graph with no simple circuits. Theorem 1. An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices. Theorem 2. A tree with m-vertices has m-1 edges 4  Example Which of the graphs (a, b and c) are trees? a) b) c) 5  Solution a) b) tree Not a tree vertices = 6 vertices = 6 edges = 5 c) edges = 6 tree vertices = 9 edges = 8 6 Rooted Tree  Rooted Tree Definition 2.A rooted tree is a tree in which one vertex has been designed as the root and every edge is directed awayfrom the root. a b c d e f g 8  Rooted Tree - Terminologies 9..cont’d 10..cont’d 11..cont ’d 12  Example full binary tree full 3-ary tree full 5-ary tree not full 3-ary tree 13  Exercise Find: Ancestors of g Parent of e Descendents of g Children of e 14 Sibling of h Properties of Tree  Properties of Trees Theorem 2 : A tree with n nodes has n-1 edges Theorem 3 : A full m-ary tree with i internal vertices contains n = mi +  vertices. Corollary: A full m-ary tree with n vertices contains (n−)m internal vertices, and hence n − (n−)m = ((m−) n+)m leaves Corollary is a result in which the (usually short) proof relies heavily on a given theorem. 16..cont’d Theorem 4 –A full m-ary tree with 1. n vertices has i = (n-1)/m internal vertices and l = [(m-1)n+1]/m leaves. 2. i internal vertices has n = mi +1 vertices and l = (m-1)i + 1 leaves. 3. l leaves has n =(ml-1)/(m-1) vertices and i =(l-1)/(m-1) internal vertices. 17  Properties of Rooted Trees The level of avertex v in arooted tree is the length of the unique path from the root to this vertex. The level of the root is defined to be zero. The height of arooted tree is the maximum of the levels of vertices. 16  Example 17..cont’d Definition: A rooted m-ary tree of height h is balanced if all leaves are at levels h or h−1. Theorem. There are at most mh leaves in an m- arry tree of height h. 18  Exercise Which of the rooted trees shown below are balanced? Solution: T1, T3 19 Tree Traversal  Tree Traversal Universal Address Systems Label vertices: 1. root → 0, its k children → 1, 2, …, k (from left to right) 2. For each vertex v at level n with label A, its r children → A.1, A.2, …, A.r (from left to right). We can totally order the vertices using the lexicographic ordering of their labels in the universal address system. x1.x2…..xn < y1.y2…..ym if there is an i, 0  i  n, with x1= y1, x2= y2, …, xi-1= yi-1, and xi