Data Structures CSCI 3230
Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 27 page Class Notes was uploaded by Marcel Botsford Sr. on Monday October 12, 2015. The Class Notes belongs to CSCI 3230 at Georgia Southern University taught by Debopam Acharya in Fall. Since its upload, it has received 65 views. For similar materials see /class/221982/csci-3230-georgia-southern-university in ComputerScienence at Georgia Southern University.
Reviews for Data Structures
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/12/15
Trees Basic Concepts Terminology Definition of a general tree A general tree T is a set of one or more nodes such that T is partitioned into disjoint subsets A single node r the root Sets that are general trees called subtrees of r Definition of a binary tree A binary tree is a set T of nodes such that either T is empty or o T is partitioned into three disjoint subsets A single node r the root Two possibly empty sets that are binary trees called left and right subtrees of r Terminology a b a bc a b 900 O b C Binary trees that represent algebraic expressions Terminology The height of trees Height of a tree T defined in terms of the levels of its nodes If T is empty its height is O lfT is not empty its height is equal to the maximum level of its nodes Terminology a b Binary trees with the same nodes but different heights Terminology Balanced binary trees A binary tree is balanced if the height of any node s right subtree differs from the height of the node s left subtree by no more than 1 Terminology Summary of tree terminology General tree A set of one or more nodes partitioned into a root node and subsets that are general subtrees of the root Parent of node n o The node directly above node n in the tree Child of node n o A node directly below node n in the tree Root The only node in the tree with no parent Terminology Summary of tree terminology Continued Leaf A node with no children Siblings Nodes with a common parent Ancestor of node n o A node on the path from the root to n Descendant of node n o A node on a path from n to a leaf Subtree of node n o A tree that consists of a child if any of n and the child s descendants Terminology Summary of tree terminology Continued Height The number of nodes on the longest path from the root to a leaf Binary tree A set of nodes that is either empty or partitioned into a root node and one or two subsets that are binary subtrees of the root Each node has at most two children the left child and the right child Left right child of node n o A node directly below and to the left right of node n in a binary tree Terminology Summary of tree terminology Continued Left right subtree of node n o In a binary tree the left right child if any of node n plus its descendants Binary search tree A binary tree where the value in any node n is greater than the value in every node in n s left subtree but less than the value of every node in n s right subtree Empty binary tree A binary tree with no nodes Terminology Summary of tree terminology Continued Balanced binary tree A binary tree in which the left and right subtrees of any node have heights that differ by at most 1 Basic Operations of the ADT Binary Tree The operations available for a particular binary tree depend on the type of binary tree being implemented Basic operations of the binary tree createBinaryTree createBinaryTreerootItem makeEmpty isEmpty getRootItem throws TreeException General Operations of the Binary Tree General operations of the binary tree createBiharyTree rootItem leftTree rightTree setRootItemhewItem attachLefthewItem throws TreeException attachRighthewItem throws TreeException attachLeftSubtreeleftTree throws TreeException attachRightSubtreerightTree throws TreeException detachLeftSubtree throws TreeException detachRightSubtree throws TreeException Traversals of a Binary Tree A traversal algorithm for a binary tree visits each node in the tree Recursive traversal algorithms Preorder traversal Visit in the order 9 Root Left Child Right Child lnorder traversal Visit in the order 9 Left Child Root Right Child Postorder traversal Visit in the order 9 Left Child Right Child Root Traversal is On Traversal of a Binary Tree a Preorder 60 20 1040 30 50 70 b Inorder 10 20 30 40 50 60 70 c Postorder 10 30 5040 20 70 60 Numbers beside nodes indicate traversal order Traversals of a binary tree a preorder b inorder C postorder Traversal of a Binary Tree Algarithm Prenrderrim Input is the rent of a subtree 1 if 1 g NULL 2 then output keyim 3 Preorderl left 4 Preordermght nn Algorithm Pestorderrfm Mg rimm INUFdEFfCI Input is the rent of a subtree In ut 3 i5 the mat Of a SuthEEh l ifmrquot NULL 1 if 33 NULL 2 then Postarder ef mn 2 then Inorderlleft 3 Postorderrrightm 3 nutnut keytim 4 output Remit 4 INDrdEFKFi htiiD Theorems The maximum number of nodes on level i of a binary tree is 2i Assuming root at level 0 o The maximum number of nodes in a binary tree of height k is 2k11 kgt0 Assuming root at level 0 o If a complete binary tree with n nodes is represented sequentially then for any node with index i 1lt iltn we have parenti is at i2 when i1 i is the root and has no parent lchildi is at 2i if 2iltn If 2igtn i has no left child rchildi is at 2i 1 if 2i1 ltn If 2i1gtn i has no left child Possible Representations of a Binary Tree An arraybased representation is good for complete binary trees It is wasteful for other ones Insertion or deletion of nodes requires the movement of potentially many nodes These problems can be easily overcome through the use of a linked representation Possible Representations of a Binary Tree In linked representation each node has 3 elds lchild data rchild Binary search tree and operations A binary tree that has the following properties for each node n n s value is greater than all values in its left subtree TL n s value is less than all values in its right subtree TR Both TL and TR are binary search trees A binary search tree of names Binary search tree and operations Not a binary search tree A binary search tree Binary search tree and operations The same set of keys may have different BSTs f x I l 5 I a a x w v I I i I 39 quot if x quot I 54143 Iquotni E39squot 39239 quotaquot rquot quot39quot x I Q x 5 If 1 VFW rvf 3quot quotwk v I u 3 I an x r I 5 I If E 391 EPA1 NI J r 5 8 quotquot Ifquot N I 4 ll k 39 Average depth of a node is Oog N Maximum depth of a node is ON Binary search tree and operations Inorder traversal of BST prints out all the keys in sorted order m j x a H r L 9 I x Inorder 2 3 4 6 7 9 131517 1820 Binary search tree and operations Search Insertion Deletion Binary search tree and operations Search Recursive Algorithm Searchl i 1 if D then return 1 else if I gt duh then return i else if I c 4 dam then return Search EarthNd 13 else return SearchU F f i f i 37 Binary search tree and operations Search Iterative Algorithm Searchr39 found falSB t t39rrjr g while it 0 and not found do if 11 z t data i the11 found 2 true else if 1 lt If data then it t v richit d else i 1 it r chiiri if not femur then return 0 else return if Binary search tree and operations Algorithm lnsertr o Insert at into the binary search tree f otrxmi false tree Search for r q is the parent of 1 while 1 U and not found do 2 p Save p if 7 p duu39l then found true else if 139 lt p damn then 1 2 p A rlrihl else 1 p gt vrzhild Perform insertion f not funmi then mquot we p 2 new T N39ENOJC p r lchsrflii 0 p a rchild 0 p 39 data if tree 0 then 1 if 1 lt q damn then 1 1012x114 1 else q whild 1 else Irer p
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'