data structure module fourth module linked list

ppt

1. Module 4
Presented by
BhavanaG
Assistant Professor
Dept. of Computer Science(MCA)
Centerfor post Graduate studies, VTU
Muddenahalli.
1
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

2. 2
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli
Introduction of Trees in Data
Structure
Course Code: OBCA201

3. Course outcomes
•CO1:Identifydifferenttypesofdatastructures,operationsandalgorithms.
•CO2:Illustratesearchingandsortingoperationsonfiles.
•CO3:Demonstratetheworkingofstack,Queue,Lists,TreesandGraphsin
problemsolving&implementalldatastructuresinahigh-levellanguagefor
problemsolving.
3
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

4. Textbooks & Reference Books
1.AdamDrozdek,“DataStructuresandAlgorithmsinC++”,2013,FourthEdition,
CengageLearning.
2.BhushanTrivedi,“ProgrammingwithANSIC++”,OxfordPress,SecondEdition,2012.
3.BalagurusamyE,ObjectOrientedProgrammingwithC++,TataMcGrawHill
EducationPvt.Ltd,FourthEdition2010.
4.R.S.Salaria,“DataStructures&Algorithms”,KhannaBookPublishingCo.
(P)Ltd..,2002
4
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

5. AGENDA:
•What is Tree Data Structure?
•Why Tree Data Structure?
•Tree Terminologies.
•Tree Node.
•Types of Trees.
•Tree Traversal
•Application of Trees(BST)
5
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

6. WHAT IS TREE DATA STRUCTURE?
•A Tree is a Non-Linear data Structure that consists of
nodes and is connected by edges.
6
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

7. WHY TREE DATA STRUCTURE?
7
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

8. •AlinearDatastructurethatstoresdataelementsinsequentialform.
•Inoperationperformedinlineardatastructure,thetimecomplexity
increaseswithincreaseddatasize.
8
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli
10 20 30 40 50 60 70

9. 9
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli
10
20 30
40 50 60 70
TheTreeDatastructureisnon-linearandallowseasierand
quickeraccesstothedataelements.

10. The Tree data structure can be useful in many
cases:
•Hierarchical Data: File systems, organizational models, etc.
•Databases: Used for quick data retrieval.
•Routing Tables: Used for routing data in network algorithms.
•Sorting/Searching: Used for sorting data and searching for data.
•Priority Queues: Priority queue data structures are commonly implemented using
trees, such as binary heaps.
10
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

11. Tree Terminologies
•Tree Node :A node is a structure or an entity that contains a key or
value and pointers to its child node.
•
•
11
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

12. Tree Terminologies
•Root:In a tree data structure, the root is the first node of
the tree. The root node is the initial node of the tree in data
structures.
•In the tree data structure, there must be only one root node.
•
12
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

13. 13
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli
•Edge:In a tree in data structures, the connecting link of any
two nodes is called the edge of the tree data structure.
•In the tree data structure, N number of nodes connecting
with N -1 number of edges.
Tree Terminologies

14. •Parent:In the tree in data structures, the node that is the
predecessor of any node is known as a parent node, or a node
with a branch from itself to any other successive node is called
the parent node.
14
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli
Tree Terminologies

15. Tree Terminologies
Child:
•The node, a descendant of any node, is
known as child nodes in data structures.
•In a tree, any number of parent nodes can
have any number of child nodes.
•In a tree, every node except the root node
is a child node.
15
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

16. Tree Terminologies
Siblings:
•Intreesinthedatastructure,nodes
thatbelongtothesameparentare
calledsiblings.
16
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

17. Tree Terminologies
Leaf:
•Trees in the data structure, the
node with no child, is known as a
leaf node.
•In trees, leaf nodes are also called
external nodes or terminal nodes.
17
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

18. Tree Terminologies
Internalnodes
•Treesinthedatastructurehaveatleastonechild
nodeknownasinternalnodes.
•Intrees,nodesotherthanleafnodesareinternal
nodes.
•Sometimesrootnodesarealsocalledinternalnodes
ifthetreehasmorethanonenode.
18
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

19. Tree Terminologies
19
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli
Degree:
•Inthetreedatastructure,thetotalnumberof
childrenofanodeiscalledthedegreeofthe
node.
•Thehighestdegreeofthenodeamongallthe
nodesinatreeiscalledtheDegreeofTree.

20. Tree Terminologies
Level:
•Intreedatastructures,therootnode
issaidtobeatlevel0,andtheroot
node'schildrenareatlevel1,andthe
childrenofthatnodeatlevel1willbe
level2,andsoon.
20
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

21. Tree Terminologies
•Height:
•Inatreedatastructure,thenumberof
edgesfromtheleafnodetotheparticular
nodeinthelongestpathisknownasthe
heightofthatnode.
•Inthetree,theheightoftherootnodeis
called"HeightofTree".
•Thetreeheightofallleafnodesis0.
21
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

22. Depth:
•Inatree,manyedgesfromtheroot
nodetotheparticularnodearecalled
thedepthofthetree.
•Inthetree,thetotalnumberofedges
fromtherootnodetotheleafnodein
thelongestpathisknownas"Depthof
Tree".
•Inthetreedatastructures,thedepthof
therootnodeis0.
22
Tree Terminologies
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

23. Path:
•Inthetreeindatastructures,the
sequenceofnodesandedgesfromone
nodetoanothernodeiscalledthepath
betweenthosetwonodes.
•Thelengthofapathisthetotalnumber
ofnodesinapath.zx
23
Tree Terminologies
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

24. Subtree
•Inthetreeindatastructures,each
childfromanodeshapesasub-tree
recursivelyandeverychildinthetree
willformasub-treeonitsparent
node.
24
Tree Terminologies
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

25. Here are the different kinds of tree in data structures:
General Tree:
•The general tree is the type of tree where there are no
constraints on the hierarchical structure.
Properties
•The general tree follows all properties of the tree data
structure.
•A node can have any number of nodes.
25
Types of Tree in Data Structures
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

26. Types of Tree in Data Structures
BinaryTree
•Abinarytreehasthefollowingproperties:
Properties
•Followsallpropertiesofthetreedatastructure.
•Binarytreescanhaveatmosttwochildnodes.
•Thesetwochildrenarecalledtheleftchildandthe
rightchild.
26
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

27. BinarySearchTree
•Abinarysearchtreeisatypeoftreethatisa
moreconstrictedextensionofabinarytreedata
structure.
Properties
•Followsallpropertiesofthetreedatastructure.
•Thebinarysearchtreehasauniqueproperty
knownasthebinarysearchproperty.Thisstates
thatthevalueofaleftchildnodeofthetree
shouldbelessthanorequaltotheparentnode
valueofthetree.Andthevalueoftherightchild
nodeshouldbegreaterthanorequaltothe
parentvalue.
27
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

28. AVL Tree
•An AVL tree is a type of tree that is a self-balancing
binary search tree.
Properties
•Follows all properties of the tree data structure.
•Self-balancing.
•Each node stores a value called a balanced factor, which
is the difference in the height of the left sub-tree and
right sub-tree.
•All the nodes in the AVL tree must have a balance factor
of -1, 0, and1.
28
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

29. Tree Traversal
29
Traversal of the tree in data structures is a process of visiting
each node and prints their value. There are three ways to
traverse tree data structure.
Pre-order Traversal
In-Order Traversal
Post-order Traversal
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

30. Inthein-ordertraversal,theleftsubtreeisvisitedfirst,then
theroot,andlatertherightsubtree.
Algorithm:
Inorder(tree)
•Traverse the left subtree, i.e., call Inorder(left->subtree)
•Visit the root.
•Traverse the right subtree, i.e., call Inorder(right-
>subtree)
30
In-Order Traversal
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

31. Inpre-ordertraversal,itvisitstherootnode
first,thentheleftsubtree,andlastlyright
subtree.
Algorithm:
Preorder(tree)
•Visit the root.
•Traverse the left subtree, i.e., call Preorder(left->subtree)
•Traverse the right subtree, i.e., call Preorder(right-
>subtree)
31
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli
Pre-Order Traversal

32. Post-Order Traversal
It visits the left subtree first in post-order traversal, then the
right subtree, and finally the root node.
Algorithm:
Postorder(tree)
•Traverse the left subtree, i.e., call Postorder(left->subtree)
•Traverse the right subtree, i.e., call Postorder(right->subtree)
•Visit the root.
32
Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli

33. Bhavana G, Assistant Professor, Dept. of CS(MCA), CPGSB,VTU, Muddenahalli
33
•Binary Search Tree (BST) is used to check whether elements
present or not.
•Heap is a type of tree that is used to heap sort.
•Tries are the modified version of the tree used in modem routing to
information of the router.
•The widespread database uses B-tree.
•Compilers use syntax trees to check every syntax of a program.
•With this, you’ve come to the end of this tutorial about the tree in
data structures.
Application of Tree in Data Structures

34. Latharani T R, Assistant Professor, Dept. of CS&E, JIT, Davangere 34