logging in or signing up computer notes - Data Structures - 11 ecomputernotes Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 20 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: December 28, 2011 This Presentation is Public Favorites: 0 Presentation Description Computer Notes on all computer subject that's related to all university and all college.it help you prepare better for the school and college exams ecomputernotes present to you the revision notes on Computer subjects. Comments Posting comment... Premium member Presentation Transcript PowerPoint Presentation: Class No.11 Data Structures http://ecomputernotes.comCode for Simulation: Code for Simulation // print the final avaerage wait time. double avgWait = (totalTime*1.0)/count; cout << "Total time: " << totalTime << endl; cout << “Customer: " << count << endl; cout << "Average wait: " << avgWait << endl; http://ecomputernotes.comPriority Queue: Priority Queue #include "Event.cpp" #define PQMAX 30 class PriorityQueue { public: PriorityQueue() { size = 0; rear = -1; }; ~PriorityQueue() {}; int full(void) { return ( size == PQMAX ) ? 1 : 0; }; http://ecomputernotes.comPriority Queue: Priority Queue Event* remove() { if( size > 0 ) { Event* e = nodes[0]; for(int j=0; j < size-2; j++ ) nodes[j] = nodes[j+1]; size = size-1; rear=rear-1; if( size == 0 ) rear = -1; return e; } return (Event*)NULL; cout << "remove - queue is empty." << endl; }; http://ecomputernotes.comPriority Queue: Priority Queue int insert(Event* e) { if( !full() ) { rear = rear+1; nodes[rear] = e; size = size + 1; sortElements(); // in ascending order return 1; } cout << "insert queue is full." << endl; return 0; }; int length() { return size; }; }; http://ecomputernotes.comTree Data Structures: Tree Data Structures There are a number of applications where linear data structures are not appropriate. Consider a genealogy tree of a family. Mohammad Aslam Khan Sohail Aslam Javed Aslam Yasmeen Aslam Saad Haaris Qasim Asim Fahd Ahmad Sara Omer http://ecomputernotes.comTree Data Structure: Tree Data Structure A linear linked list will not be able to capture the tree-like relationship with ease. Shortly, we will see that for applications that require searching, linear data structures are not suitable. We will focus our attention on binary trees . http://ecomputernotes.comBinary Tree: Binary Tree A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the root of the tree. The other two subsets are themselves binary trees called the left and right subtrees . Each element of a binary tree is called a node of the tree. http://ecomputernotes.comBinary Tree: Binary Tree Binary tree with 9 nodes. A B D H C E F G I http://ecomputernotes.comBinary Tree: Binary Tree A B D H C E F G I Left subtree root Right subtree http://ecomputernotes.comBinary Tree: Binary Tree Recursive definition A B D H C E F G I Left subtree root Right subtree http://ecomputernotes.comBinary Tree: Binary Tree Recursive definition A B D H C E F G I Left subtree root http://ecomputernotes.comBinary Tree: Binary Tree Recursive definition A B D H C E F G I root http://ecomputernotes.comBinary Tree: Binary Tree Recursive definition A B D H C E F G I root Right subtree http://ecomputernotes.comBinary Tree: Binary Tree Recursive definition A B D H C E F G I root Right subtree Left subtree http://ecomputernotes.comNot a Tree: Not a Tree Structures that are not trees. A B D H C E F G I http://ecomputernotes.comNot a Tree: Not a Tree Structures that are not trees. A B D H C E F G I http://ecomputernotes.comNot a Tree: Not a Tree Structures that are not trees. A B D H C E F G I http://ecomputernotes.comBinary Tree: Terminology: Binary Tree: Terminology A B D H C E F G I parent Left descendant Right descendant Leaf nodes Leaf nodes http://ecomputernotes.comBinary Tree: Binary Tree If every non-leaf node in a binary tree has non-empty left and right subtrees, the tree is termed a strictly binary tree . A B D H C E F G I J K http://ecomputernotes.comLevel of a Binary Tree Node: Level of a Binary Tree Node The level of a node in a binary tree is defined as follows: Root has level 0, Level of any other node is one more than the level its parent (father). The depth of a binary tree is the maximum level of any leaf in the tree. http://ecomputernotes.comLevel of a Binary Tree Node: Level of a Binary Tree Node A B D H C E F G I 1 0 1 2 2 2 3 3 3 Level 0 Level 1 Level 2 Level 3 http://ecomputernotes.comComplete Binary Tree: Complete Binary Tree A complete binary tree of depth d is the strictly binary all of whose leaves are at level d . A B N C G O 1 0 1 2 3 3 L F M 2 3 3 H D I 2 3 J E K 2 3 http://ecomputernotes.comComplete Binary Tree: Complete Binary Tree A B Level 0: 2 0 nodes H D I E J K C L F M G N O Level 1: 2 1 nodes Level 2: 2 2 nodes Level 3: 2 3 nodes http://ecomputernotes.comComplete Binary Tree: Complete Binary Tree At level k , there are 2 k nodes. Total number of nodes in the tree of depth d : 2 0 + 2 1 + 2 2 + ………. + 2 d = 2 j = 2 d+1 – 1 In a complete binary tree, there are 2 d leaf nodes and (2 d - 1) non-leaf (inner) nodes. j=0 d http://ecomputernotes.comComplete Binary Tree: Complete Binary Tree If the tree is built out of ‘n’ nodes then n = 2 d+1 – 1 or log 2 (n+1) = d+1 or d = log 2 (n+1) – 1 I.e., the depth of the complete binary tree built using ‘n’ nodes will be log 2 (n+1) – 1. For example, for n=100,000, log 2 (100001) is less than 20; the tree would be 20 levels deep. The significance of this shallowness will become evident later. http://ecomputernotes.comOperations on Binary Tree: Operations on Binary Tree There are a number of operations that can be defined for a binary tree. If p is pointing to a node in an existing tree then left( p ) returns pointer to the left subtree right( p ) returns pointer to right subtree parent( p ) returns the father of p brother( p ) returns brother of p . info(p) returns content of the node. http://ecomputernotes.com You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
computer notes - Data Structures - 11 ecomputernotes Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 20 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: December 28, 2011 This Presentation is Public Favorites: 0 Presentation Description Computer Notes on all computer subject that's related to all university and all college.it help you prepare better for the school and college exams ecomputernotes present to you the revision notes on Computer subjects. Comments Posting comment... Premium member Presentation Transcript PowerPoint Presentation: Class No.11 Data Structures http://ecomputernotes.comCode for Simulation: Code for Simulation // print the final avaerage wait time. double avgWait = (totalTime*1.0)/count; cout << "Total time: " << totalTime << endl; cout << “Customer: " << count << endl; cout << "Average wait: " << avgWait << endl; http://ecomputernotes.comPriority Queue: Priority Queue #include "Event.cpp" #define PQMAX 30 class PriorityQueue { public: PriorityQueue() { size = 0; rear = -1; }; ~PriorityQueue() {}; int full(void) { return ( size == PQMAX ) ? 1 : 0; }; http://ecomputernotes.comPriority Queue: Priority Queue Event* remove() { if( size > 0 ) { Event* e = nodes[0]; for(int j=0; j < size-2; j++ ) nodes[j] = nodes[j+1]; size = size-1; rear=rear-1; if( size == 0 ) rear = -1; return e; } return (Event*)NULL; cout << "remove - queue is empty." << endl; }; http://ecomputernotes.comPriority Queue: Priority Queue int insert(Event* e) { if( !full() ) { rear = rear+1; nodes[rear] = e; size = size + 1; sortElements(); // in ascending order return 1; } cout << "insert queue is full." << endl; return 0; }; int length() { return size; }; }; http://ecomputernotes.comTree Data Structures: Tree Data Structures There are a number of applications where linear data structures are not appropriate. Consider a genealogy tree of a family. Mohammad Aslam Khan Sohail Aslam Javed Aslam Yasmeen Aslam Saad Haaris Qasim Asim Fahd Ahmad Sara Omer http://ecomputernotes.comTree Data Structure: Tree Data Structure A linear linked list will not be able to capture the tree-like relationship with ease. Shortly, we will see that for applications that require searching, linear data structures are not suitable. We will focus our attention on binary trees . http://ecomputernotes.comBinary Tree: Binary Tree A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the root of the tree. The other two subsets are themselves binary trees called the left and right subtrees . Each element of a binary tree is called a node of the tree. http://ecomputernotes.comBinary Tree: Binary Tree Binary tree with 9 nodes. A B D H C E F G I http://ecomputernotes.comBinary Tree: Binary Tree A B D H C E F G I Left subtree root Right subtree http://ecomputernotes.comBinary Tree: Binary Tree Recursive definition A B D H C E F G I Left subtree root Right subtree http://ecomputernotes.comBinary Tree: Binary Tree Recursive definition A B D H C E F G I Left subtree root http://ecomputernotes.comBinary Tree: Binary Tree Recursive definition A B D H C E F G I root http://ecomputernotes.comBinary Tree: Binary Tree Recursive definition A B D H C E F G I root Right subtree http://ecomputernotes.comBinary Tree: Binary Tree Recursive definition A B D H C E F G I root Right subtree Left subtree http://ecomputernotes.comNot a Tree: Not a Tree Structures that are not trees. A B D H C E F G I http://ecomputernotes.comNot a Tree: Not a Tree Structures that are not trees. A B D H C E F G I http://ecomputernotes.comNot a Tree: Not a Tree Structures that are not trees. A B D H C E F G I http://ecomputernotes.comBinary Tree: Terminology: Binary Tree: Terminology A B D H C E F G I parent Left descendant Right descendant Leaf nodes Leaf nodes http://ecomputernotes.comBinary Tree: Binary Tree If every non-leaf node in a binary tree has non-empty left and right subtrees, the tree is termed a strictly binary tree . A B D H C E F G I J K http://ecomputernotes.comLevel of a Binary Tree Node: Level of a Binary Tree Node The level of a node in a binary tree is defined as follows: Root has level 0, Level of any other node is one more than the level its parent (father). The depth of a binary tree is the maximum level of any leaf in the tree. http://ecomputernotes.comLevel of a Binary Tree Node: Level of a Binary Tree Node A B D H C E F G I 1 0 1 2 2 2 3 3 3 Level 0 Level 1 Level 2 Level 3 http://ecomputernotes.comComplete Binary Tree: Complete Binary Tree A complete binary tree of depth d is the strictly binary all of whose leaves are at level d . A B N C G O 1 0 1 2 3 3 L F M 2 3 3 H D I 2 3 J E K 2 3 http://ecomputernotes.comComplete Binary Tree: Complete Binary Tree A B Level 0: 2 0 nodes H D I E J K C L F M G N O Level 1: 2 1 nodes Level 2: 2 2 nodes Level 3: 2 3 nodes http://ecomputernotes.comComplete Binary Tree: Complete Binary Tree At level k , there are 2 k nodes. Total number of nodes in the tree of depth d : 2 0 + 2 1 + 2 2 + ………. + 2 d = 2 j = 2 d+1 – 1 In a complete binary tree, there are 2 d leaf nodes and (2 d - 1) non-leaf (inner) nodes. j=0 d http://ecomputernotes.comComplete Binary Tree: Complete Binary Tree If the tree is built out of ‘n’ nodes then n = 2 d+1 – 1 or log 2 (n+1) = d+1 or d = log 2 (n+1) – 1 I.e., the depth of the complete binary tree built using ‘n’ nodes will be log 2 (n+1) – 1. For example, for n=100,000, log 2 (100001) is less than 20; the tree would be 20 levels deep. The significance of this shallowness will become evident later. http://ecomputernotes.comOperations on Binary Tree: Operations on Binary Tree There are a number of operations that can be defined for a binary tree. If p is pointing to a node in an existing tree then left( p ) returns pointer to the left subtree right( p ) returns pointer to right subtree parent( p ) returns the father of p brother( p ) returns brother of p . info(p) returns content of the node. http://ecomputernotes.com