NON-LINEAR DATA STRUCTURE-TREES.pptx

TREEs in Data structures notes

1. NON-LINEAR DATA STRUCTURE BY A. RAJITHA DL in Computer Science TTWRDC- SpARK , NAGARAM-

2. OBJECTIVES What is Non Linear Data Structure? What is importance of Non Linear Data Structures Different Non Linear Data Structures Operations of each Non Linear Data Structures Applications of each Non Linear Data Structures Questioner

3. What is Non Linear Data Structure A Non-Linear Data structures is a data structure in which data item is connected to several other data items. Non-Linear data structure may exhibit either a hierarchical relationship or parent-child relationship. In non-linear data structures, every data element may have more than one predecessor as well as successor. Elements do not form any particular linear sequence.

4. Importance Non-linear data structures are capable of expressing more complex relationships than linear data structures . The memory is utilized efficiently in the  non - linear data structure  where  linear data structure  tends to waste the memory. One big drawback of linked list is, random access is  not  allowed.

5. Types of Non Linear Data Structures Trees A tree is a non-empty set one element of which is designated the root of the tree while the remaining elements are partitioned into non-empty sets each of which is a sub-tree of the root. Graph A graph G is a discrete structure consisting of nodes (vertices) and the lines joining the nodes (edges).

6. TREES Trees are non linear data structure that can be represented in a hierarchical manner. A tree contains a finite non-empty set of elements. Any two nodes in the tree are connected with a relationship of parent-child. Every individual elements in a tree can have any number of sub trees. It represents the nodes connected by edges

7. Terminology of TREE Root : The basic node of all nodes in the tree. All operations on the tree are performed with passing root node to the functions. Child : a successor node connected to a node is called child. A node in binary tree may have at most two children. Parent : a node is said to be parent node to all its child nodes. Leaf : a node that has no child nodes. Siblings : Two nodes are siblings if they are children to the same parent node.

8. Terminology of TREE Ancestor : a node which is parent of parent node ( B is ancestor node to D,E and F ). Descendent : a node which is child of child node ( D, E and F are descendent nodes of node B ) Level : The distance of a node from the root node, The root is at level – 0,( B and C at Level 1 and D, E, F have Level 2 ( highest level of tree is called height of tree ) Degree : The number of nodes connected to a particular parent node. Path : Path is a number of successive edges from source node to destination node.

9. Terminology of TREE Edge : Edge is connection between one node to another node Path : Path is a number of successive edges from source node to destination node. Edge : Edge is connection between one node to another node. Height of a node : It represents number of edges on the longest path between that node and a leaf. Height of a Tree : It represents the height of root node. Depth of a Tree: Depth of a tree represents the number edges from the tree’s root node to the node.

10. TYPES of TREE Free tree Rooted tree Ordered tree Regular tree Binary tree Complete Binary tree Binary Search tree

11. FREE TREE A free tree is a connected, acyclic graph . It is undirected graph It has no node designated as a root As it is connected, any node can be reached from any other node by a unique path Figure: Free Tree

12. Rooted Tree Unlike free tree, rooted tree is a directed graph in which one node is designated as root, whose incoming degree is zero And for all other nodes incoming degree is one. Figure: Rooted Tree

13. Ordered Tree In many applications the relative order of the nodes at any particular level assumes some significance It is easy to impose an order on the nodes at a level by referring to a particular node as the first node, to another node as the second, and so on Such ordering can be done left to right Ordered Tree

14. Regular Tree A tree in which each branch node vertex has the same out degree is called as Regular Tree. If in a directed tree, the out degree of every node is less than or equal to m, then the tree is called as an m- ary tree. If the out degree of every node is exactly equal to m (branch nodes) or zero (leaf nodes) then the tree is called as regular m- ary tree.

15. Binary Tree In a binary tree, each node can have at most two children. A binary tree is either empty or consists of a node called the root together with two binary trees called the left subtree and the right subtree . Node with 2 children are called internal nodes and nodes with 0 children are called external nodes

16. Binary Tree (Contd..) Assigning level numbers and Numbering of nodes for a binary tree: The nodes of a binary tree can be numbered in a natural way level by level left to right. The nodes of a complete binary tree can be numbered so that the root is assigned the number 1. A left child is assigned twice the number assigned its parent. A right child is assigned one more than twice the number assigned its parent.

17. Binary Tree (Contd..)

18. Properties of Binary Tree If h = height of a binary tree, then a. Maximum number of leaves = 2 h b. Maximum number of nodes = 2 h + 1 - 1 If a binary tree contains m nodes at level l, it contains at most 2m nodes at level l + 1 . Since a binary tree can contain at most one node at level (the root), it can contain at most 2 l node at level l The total number of edges in a full binary tree with n node is n - 1 .

19. Strictly Binary Tree If every non-leaf node in a binary tree has nonempty left and right sub trees, the tree is termed a strictly binary tree. A strictly binary tree with n leaves always contains 2n – 1 nodes.

20. Fully Binary Tree A full binary tree of height h has all its leaves at level h. All non leaf nodes of a full binary tree have two children, and the leaf nodes have no children. A full binary tree with height h has 2 h + 1 - 1 nodes. A full binary tree of height h is a strictly binary tree all of whose leaves are at level h. For example, a full binary tree of height 3 contains 2 3+1 – 1 = 15 nodes.

21. Complete Binary Tree A binary tree with n nodes is said to be complete if it contains all the first n nodes of the above numbering scheme. A complete binary tree of height h looks like a full binary tree down to level h -1 , and the level h is filled from left to right. Leaf nodes at level n occupy the leftmost positions in the tree

22. Perfect Binary Tree A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level. A Perfect Binary Tree of height h has 2 h – 1 non leaf nodes.

23. Representation of Binary Tree Array Representation In array representation of a binary tree, we use one-dimensional array (1-D Array) to represent a binary tree. This numbering can start from 0 to (n-1) or from 1 to n. Lets derive the positions of nodes and their parent and child nodes in the array. When we use  index based sequencing, Suppose parent node is an index p. Then, the left child node is at index (2*p)+ 1. The right child node is at index (2*p) + 2. Root node is at index 0. left_child is at index 1. Right_child is at index 2.

24. Representation of Binary Tree When we use  1 index based sequencing , Suppose parent node is at  index p, Right node is at  index (2*p). Left node is at  index (2*p)+1 . Root node is at index 1. Left child is at index 2. Right child is at index 3. 0 1 2 3 4 5 6 7 8 9 10 11………………..20

25. Representation of Binary Tree ADVANTAGES Any node can be accesses from any other node by calculating the index. Here, data are stored without any pointers to their successor or ancestor. DISADVANTAGES Other than full binary trees, majority of the array entries may be empty A new node to it or deleting a node from it are inefficient with this representation

26. Representation of Binary Tree Linked List Representation Binary trees can be represented by links where each node contains the address of the left child and the right child. If any node has its left or right child empty then it will have in its respective link field, a null value. A leaf node has null value in both of its links. Node Structure in Binary Tree

27. Representation of Binary Tree

28. Representation of Binary Tree ADVANTAGES The drawback of sequential representation are overcome in this representation . We may or may not know the tree depth in advance. Also for unbalanced tree, memory is not wasted. Insertion and deletion operations are more efficient in this representation.

29. Representation of Binary Tree DISADVANTAGES In this representation, there is no direct access to any node . It has to be traversed from root to reach to a particular node As compared to sequential representation memory needed per node is more. This is due to two link fields (left child and right child for binary trees) in node

30. Operations of Binary Tree Creation : Creating an empty binary tree to which ‘root‘ points . Traversal : To Visiting all the nodes in a binary tree Deletion : To Deleting a node from a non-empty binary tree Insertion : To Inserting a node into an existing/empty binary tree. Merge : To Merging two binary trees Copy : Copying a binary tree . Compare : Comparing two binary trees. Find replica or mirror

31. Tree Traversals A binary tree is defined recursively: it consists of a root, a left sub tree, and a right sub tree. To traverse (or walk) the binary tree is to visit each node in the binary tree exactly once. Tree traversals are naturally recursive. Standard traversal orderings: • preorder • inorder • postorder

32. Preorder , Inorder , Postorder In Preorder, the root is visited before (pre) the subtrees traversals. In Inorder , the root is visited in-between left and right subtree traversal. In Postorder , the root is visited after (post) the subtrees traversals

33. Traversal Example Assume: visiting a node is printing its data • Preorder: 15 8 2 6 3 7 11 10 12 14 20 27 22 30 • Inorder : 2 3 6 7 8 10 11 12 14 15 20 22 27 30 • Postorder : 3 7 6 2 10 14 12 11 8 22 30 27 20 15

34. Binary Search Tree Stores keys in the nodes in a way so that searching, insertion and deletion can be done efficiently. Binary Search Tree Property For every node X, all the keys in its left subtree are smaller than the key value in X, and all the keys in its right subtree are larger than the key value in X

35. Binary Search Tree Binary Tree Non Binary Tree

36. Binary Search Tree

37. Searching Binary Search Tree If we are searching for 15, then we are done. If we are searching for a key < 15, then we should search in the left subtree . If we are searching for a key > 15, then we should search in the right subtree .

38. Searching Binary Search Tree

39. Binary Search Tree FindMinimum : Start at the root and go left as long as there is a left child. The stopping point is the smallest element FindMaxmum : Start at the root and go right as long as there is a right child. The stopping point is the largest element Ascending order: Inorder traversal of a binary search tree gives prints elements in sorted order.

40. Applications of Trees Storing naturally hierarchical data File System Organizational Structure of an institution Class inheritance tree Organize data for quick search, insertion, deletion- Binary Search Tree. Dictionary Networking Routing Algorithm. Problem representation Expression trees Decision tree.

41. Questions 1. Construct the tree from the following preorder and inorder travels: Preorder : a,b,c,d,e,g,h,j,f . Inorder : c,d,b,a,h,g,j,e,f .

42. Construct a binary search tree with the below information. The preorder traversal of a binary search tree 10, 4, 3, 5, 11, 12. Preorder Traversal is 10, 4, 3, 5, 11, 12. Inorder Traversal of Binary search tree is equal to ascending order of the nodes of the Tree. Inorder Traversal is 3, 4, 5, 10, 11, 12. The tree constructed using Preorder and Inorder traversal is

43. THANK YOU