Looking for a Tutor Near You?

Post Learning Requirement »
x

Choose Country Code

x

Direction

x

Ask a Question

x

x
x
For better view click here
x
Hire a Tutor
DISCOVER

Data Structures And Algorithms-Part 1

Loading...

Published in: PL/SQL
2,520 Views

Data Structures are the programmatic way of storing data so that data can be used efficiently. Almost every enterprise application uses various types of data structures in one or other way. This tutorial will give you great understanding on Data Structures concepts needed to understand the complexity of enterprise level applications and need of algorithms, data structures.

Prantik S / Kolkata

11 years of teaching experience

Qualification: MCA (Jaipur National University - [JNU], Jaipur - 2017)

Teaches: Basic Computer, Computer for official job, MS Office, School Level Computer, ICT Training, Computer Science, Information Practice, IT & Computer Subjects, BCA Tuition, IT, Computer, C / C++, C# (C Sharp), Java And J2EE, Python Programming, Visual Basic, BCA Subjects, Hardware Training, Networking, Java Script

Contact this Tutor
  1. The Need for Data Structures Data structures organize data more efficient programs. More powerful computers more complex applications. More complex applications demand more calculations. Complex computing tasks are unlike our everyday experience.
  2. Selecting a Data Structure Select a data structure as follows: 2. 3. Analyze the problem to determine the resource constraints a solution must meet. Determine the basic operations that must be supported. Quantify the resource constraints for each operation. Select the data structure that best meets these requirements.
  3. Abstract Data Types Abstract Data Type (ADT): a definition for a data type solely in terms of a set of values and a set of operations on that data type. Each ADT operation is defined by its inputs and outputs. Encapsulation: Hide implementation details.
  4. Data Structure A data structure is the physical implementation of an ADT. Each operation associated with the ADT is implemented by one or more subroutines in the implementation. Data structure usually refers to an organization for data in main memory. File structure is an organization for data on peripheral storage, such as a disk drive.
  5. Metaphors An ADT manages complexity through abstraction: metaphor. Hierarchies of labels Ex: transistors gates CPU. In a program, implement an ADT, then think only about the ADT, not its implementation.
  6. Logical vs. Physical Form Data items have both a logical and a physical form. Logical form: definition of the data item within an ADT. Ex: Integers in mathematical sense: +, Physical form: implementation of the data item within a data structure. Ex: 1 6/32 bit integers, overflow.
  7. Problems Problem: a task to be performed. Best thought of as inputs and matching outputs. Problem definition should include constraints on the resources that may be consumed by any acceptable solution.
  8. Algorithms and Programs Algorithm: a method or a process followed to solve a problem. A recipe. An algorithm takes the input to a problem (function) and transforms it to the output. A mapping of input to output. A problem can have many algorithms.
  9. Algorithm Properties An algorithm possesses the following properties: It must be correct. It must be composed of a series of concrete steps. There can be no ambiguity as to which step will be performed next. It must be composed of a finite number of steps. It must terminate. A computer program is an instance, or concrete representation, for an algorithm in some programming language.
  10. Mathematical Background Set concepts and notation. Recursion Induction Proofs Logarithms Summations Recurrence Relations 10
  11. Estimation Techniques Known as "back of the envelope" or 2. 3. "back of the napkin" calculation Determine the major parameters that effect the problem. Derive an equation that relates the parameters to the problem. Select values for the parameters, and apply the equation to yield and estimated solution.
  12. Estimation Example How many library bookcases does it take to store books totaling one million pages? Estimate: Pages/inch Feet/shelf Shelves/bookcase 12
  13. Algorithm Efficiency There are often many approaches (algorithms) to solve a problem. How do we choose between them? At the heart of computer program design are two (sometimes conflicting) goals. 2. 13 To design an algorithm that is easy to understand, code, debug. To design an algorithm that makes efficient use of the computer's resources.
  14. How to Measure Efficiency? Empirical comparison (run programs) Asymptotic Algorithm Analysis 2. Critical resources: Factors affecting running time: For most algorithms, running time depends on "size" of the input. Running time is expressed as T(n) for some function T on input size n. 14
  15. Examples of Growth Rate Example 1. // Find largest value int largest (int array [l, int n) { // Largest value seen int cur r large O; for (int i = 1; i < n; i++) // For each val if (array [cur r large] < array [i] ) i; cur r large return cur r large, 15 // Remember pos // Return largest
  16. Best, Worst, Average Cases Not all inputs of a given size take the same time to run. Sequential search for K in an array of n integers: Begin at first element in array and look at each element in turn until K is found Best case: Worst case: Average case: 16
  17. Which Analysis to Use? While average time appears to be the fairest measure, it may be diffiuclt to determine. When is the worst case time important? 17
  18. Faster Computer or Algorithm? What happens when we buy a computer 10 times faster? 20n 5n log n 2n2 18 n 1,000 500 250 70 13 n' 10,000 5,000 1 , 842 223 16 Change n' = IOn n' = IOn 410 n < n' < 10n 41 On n' n'/n 10 10 7.37 3.16
  19. Asymptotic Analysis: Big-oh Definition: For T(n) a non-negatively valued function, T(n) is in the set O(f(n)) if there exist two positive constants c and no such that T(n) cf(n) for all n Usage: The algorithm is in O(n2) in [best, average, worst] case. Meaning: For all data sets big enough (i.e., 11>110), the algorithm always executes in less than cf(n) steps in [best, average, worst] case. 19
  20. Big-Oh Examples Example 1 : Finding value X in an array (average cost). T(n) = csn/2. For all values of n > l, csn/2 csn. Therefore, by the definition, T(n) is in O(n) for no = 1 and c = 20
  21. Big-Oh Examples Example 2: T(n) = Cin2 + C2n in average case. C1112 + C2n Cln2 + C2n2 (Cl + C2)n2 for all n > 1. T(n) cn2 forc = Cl + and no = 1. Therefore, T(n) is in O(n2) by the definition. Example 3: T(n) = c. We say this is in 0(1). 21
  22. A Common Misunderstanding "The best case for my algorithm is because that is the fastest." WRONG! Big-oh refers to a growth rate as n grows to T. Best case is defined as which input of size n is cheapest among all inputs of size n. 22
  23. Big-Omega Definition: For T(n) a non-negatively valued function, T(n) is in the set Q(g(n)) if there exist two positive constants c and no such that T(n) cg(n) for all n Meaning: For all data sets big enough (i.e., n > no), the algorithm always executes in more than cg(n) steps. Lower bound. 23
  24. Big-Omega Example T(n) = + C2n. Cln2 + C2n Cln2 for all n > 1. T(n) cn2 forc = Cl and no = 1. Therefore, T(n) is in Q(n2) by the definition. We want the greatest lower bound.
  25. Theta Notation When big-Oh and Q meet, we indicate this by using @ (big-Theta) notation. Definition: An algorithm is said to be @(h(n)) if it is in O(h(n)) and it is in Q(h(n)).
  26. A Common Misunderstanding Confusing worst case with upper bound. Upper bound refers to a growth rate. Worst case refers to the worst input from among the choices for possible inputs of a given size. 26
  27. Simplifying Rules 2. 3. 4. 27 If f(n) is in and g(n) is in then f(n) If f(n) is in O(kg(n)) for any constant k > 0, then f(n) is in O(g(n)). If fl(n) is in and f2(n) is in then (fl + is in g2(n))). If fl(n) is in and f2(n) is in then is in
  28. Running Time Examples (1) Example l: a b; This assignment takes constant time, so it is Example 2: sum = 0; for (1=1; i
  29. Running Time Examples (2) Example 3: sum = 0; for (1=1; i
  30. Binary Search Position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 How many elements are examined in worst case? 30
  31. Binary Search // Return position of element in sorted // array of size n with value K. int binary (int array [l, int n, int K) { int I n; // l, r are beyond array bounds int r while (1+1 ! = r) { // Stop when l, r meet i; int i if (K < if (K if (K > return n; 31 // Check middle array r // Left half array [i]) return i; // Found it // Right half array I i; // Search value not in array
  32. Other Control Statements while loop: Analyze like a for loop. if statement: Take greater complexity of then/else clauses. switch statement: Take complexity of most expensive case. Subroutine call: Complexity of the subroutine. 32
  33. Analyzing Problems Upper bound: Upper bound of best known algorithm. Lower bound: Lower bound for every possible algorithm. 33
  34. Analyzing Problems: Example Common misunderstanding: No distinction between upper/lower bound when you know the exact running time. Example of imperfect knowledge: Sorting I . Cost of I/O: Q(n). 2. Bubble or insertion sort: O(n2). 3. A better sort (Quicksort, Mergesort, Heapsort, etc.): log n). 4. We prove later that sorting is Q(n log n). 34
  35. Multiple Parameters Compute the rank ordering for all C pixel values in a picture of P pixels. for (i =0; i
  36. Space Bounds Space bounds can also be analyzed with asymptotic complexity analysis. Time: Algorithm Space Data Structure 36
  37. Space/ Time Tradeoff Principle One can often reduce time if one is willing to sacrifice space, or vice versa. Encoding or packing information Boolean flags Table lookup Factorials Disk-based Space/Time Tradeoff Principle: The smaller you make the disk storage requirements, the faster your program will run. 37
  38. Lists A list is a finite, ordered sequence of data items. Important concept: List elements have a position. Notation:
  39. List Implementation Concepts Our list implementation will support the concept of a current position. We will do this by defining the list in terms of left and right partitions. Either or both partitions may be empty. Partitions are separated by the fence.
  40. public : virtual virtual virtual virtual virtual virtual virtual virtual 40 List ADT template < class Elem> class List { O; O; void bool bool bool void void void void O; Clear ( ) insert (const Elem&) append (const Elem&) O; remove (Elem& ) O; set Start ( ) O; set End ( ) prev() next ( ) O; O;
  41. List ADT (cont) O; O; virtual virtual virtual virtual virtual 41 int left Length ( ) const O; int right Length ( ) const bool set Pos (int pos) O; bool get Value (Elem&) const void print() const O;
  42. List ADT Examples List: | 32, My List. insert (99) ' Result: | 99, 32, Iterate through the whole list: for (My List. set Start ( ) ; My List. get Value (it) ; My List . next ( ) ) DoSomething (it) ; 42
  43. List Find Function // Return true iff K is in list bool find (List& L, int K) { int it; for (L. set Start ( ) ; L. get Value (it) ; L. next ( ) ) // Found it if (K it) return true; return false; 43 // Not found
  44. Array-Based List Insert Insert 23: 13 12 20 44 (a) 13 12 20 8 (b) 3 (c)
  45. Array-Based List Class (1) template < class Elem> // Array-based list class AList public List { private: int maxSize; int list Size; int fence; // Maximum size of list // Actual elem count // Position of fence El em* list Array; // Array holding list public : AList (int size=DefaultListSize) { maxSize size; list Size O; fence listArray new Elem [max Size] ' 45
  46. Array-Based List Class (2) •List ( ) { delete [l list Array; void clear() delete [l list Array; list Size O; fence list Array new Elem [maxSize] ; void set Start ( ) O; { fence void set End ( ) list Size; } { fence void prev() { if (fence ! 0) fence--; void next ( ) { if (fence
  47. Array-Based List Class (3) bool set Pos (int pos) if ( (pos >= 0) && (pos = 0) && (pos
  48. Insert // Insert at front of right partition template < class Elem> bool AList: : insert (const Elem& item) if (list Size maxSize) return false; for (int i = list Size; i > fence; i -- ) // Shift Elems up to make room list Array [i] list Array [i -1] ; list Array [fence] item; list Size++; // Increment list size return true; 48
  49. Append // Append Elem to end of the list template < class Elem> bool AList: : append (const Elem& item) if (list Size maxSize) return false; list Array [list Size++] item; return true; 49
  50. // Remove and return first Elem in right // partition template < class Elem> bool AList: : remove (Elem& it) { if (right Length ( ) 0) return false; // Copy Elem it list Array [fence] ; for (int i=fence; i < list Size-I; i++) // Shift them down list Array [i] list Array [i +1] ' list Size--; return true; 50 // Decrement size
  51. Link Class Dynamic allocation of new list elements. // Singly-linked list node template < class Elem> class Link { public : Elem element; // Value for this node // Pointer to next node Link *next; Link (const Elem& elemval, Link* next val =NULL) elemval; next Link (Link* next val =NULL) nextval; { next 51 nextval;
  52. Linked List Position (1) head fence head (a) fence tall tall (b) 52
  53. Linked List Position (2) head fence (a) fence tail head tall (b) 53
  54. Linked List Class (1 ) / Linked list implementation template < class Elem> class LList: public List private: Link* head; // Link* tail; // Link* fence; // int leftcnt; int rightcnt; void init ( ) tail fence Point to list header Pointer to last Elem Last element on left Size of left Size of right Intialization routine new Link; head rightcnt O; leftcnt 54
  55. Linked List Class (2) // Return link nodes to void removeall ( ) free store while (head ! = NULL) { fence head; head head->next ; public : LList (int size=DefaultListSize) { init(); LList ( ) { removeall ( ) • void clear() { removeall ( ) 55 // Destructor init();
  56. Linked List Class (3) void set Start ( ) head; rightcnt += leftcnt; fence leftcnt void set End ( ) tail; leftcnt += rightcnt; fence rightcnt void next ( ) // Don't move fence if if (fence ! = tail) fence fence->next ; leftcnt++; } 1 nt left Length ( ) const int right Length ( ) const bool get Value (Elem& it) right empty rightcnt--; return leftcnt; return rightcnt; const { Ö) return false; if (riqhtLength ( ) it fence->next->element; return true; } 56
  57. Insertion fence Insert 10: fence 57
  58. Insert/Append // Insert at front of right partition template < class Elem> bool LList: : insert (const Elem& item) fence->next new Link (item, fence->next) if (tail fence) tail fence->next; rightcnt++; return true; } // Append Elem to end of the list template bool LList: : append (const Elem& tail tail->next new Link (item, NULL) rightcnt++; return true; } 58 item)
  59. Removal fence fence 59
  60. // Remove and return first Elem in right // partition template bool : remove (Elem& it) { if (fence->next NULL) return false; fence—>next->element; // Remember val it // Remember link node Link* I temp fence->next ; Itemp->next; // Remove fence->next I temp) // Reset tail if (tail tail fence; rightcnt--; return true; 60 // Reclaim space
  61. prev // Move fence one step left; // no change if left is empty template void LList: : prev ( ) Link* temp head; if (fence head) return; while (temp->next ! =fence) t emp=t emp->next ; fence t emp ; leftcnt--; rightcnt++; 61 // No prev Elem
  62. Setpos // Set the size of left partition to pos template < class Elem> bool LList: : set Pos (int pos) if ( (pos < 0) I (pos > rightcnt+leftcnt) ) return false; fence head; for (int i =0; i < pos; i++) fence fence->next; return true; 62
  63. Comparison of Implementations Array-Based Lists: Insertion and deletion are Prev and direct access are Array must be allocated in advance. No overhead if all array positions are full. Linked Lists: Insertion and deletion are Prev and direct access are Space grows with number of elements. Every element requires overhead. 63
  64. Space Comparison "Break-even" point: DE = + E); n = DE E: Space for data value. P: Space for pointer. D: Number of elements in array. 64
  65. Freelists System new and delete are slow. // Singly-linked list node with free list template class Link { private: static Link* free list; // Head public : L.ink* next ; // Value for this node // Point to next node Lunk (const Elem& elemval, Link* next val =NULL) elemval; nextval; next Link (Link* next val =NULL) {next=nextval; } // Overload void* operator new (size t) // Overload void operator delete (void* ) 65
  66. Freelists (2) template Link* Link: : free list NULL; // Overload for new template void* Link: : operator new (size t) { if (free list : : new Link; NULL) return free list; // Reuse Link* temp free list freelist->next; // Return the link return temp; // Overload delete template < class Elem> void Link: : operator delete (void* ptr) { ( (Link*) ptr) ->next free list; free list ) ptr; 66
  67. Doubly Linked Lists Simplify insertion and deletion: Add a prev pointer. // Doubly-linked list link node template < class Elem> class Link { public : Link *next; Link *prev; // Value for this node // Pointer to next node // Pointer to previous node Link (const Elem& e, Link* prevp =NULL, Link* next p =NULL) prev=prevp ; Link (Link* prevp =NULL, Link* next p =NULL) { prev next p ; } next prevp ; 67
  68. Doubly Linked Insert fence Insert 10: fence 68
  69. Doubly Linked Insert // Insert at front of right partition template < class Elem> bool LList: : insert (const Elem& item) { fence->next new Link (item, fence, fence->next) fence->next ; if (fence->next->next ! = NULL) fence->next->next->prev // Appending if (tail fence) fence->next; // tail new Elem tail right rightcnt++; return true; 69 // Added to
  70. Doubly Linked Remove fence fence 70
  71. Doubly Linked Remove // Remove, return first Elem in right part template < class Elem> bool LList: : remove (Elem& it) { if (fence->next NULL) return false; it fence—>next->element; Link* I temp fence->next ; if (Itemp->next ! = NULL) Itemp->next->prev fence; fence; // Reset tail fence->next -I e -I t e ITIP ; rightcnt--; return true; 71 Item ->next; // Remove / P Reclaim space // Removed from right
  72. Dictionary Often want to insert records, delete records, search for records. Required concepts: Search key: Describe what we are looking for Key comparison Equality: sequential search Relative order: sorting Record comparison 72
  73. Comparator Class How do we generalize comparison? Use Disastrous Overload Disastrous Define a function with a standard name Implied obligation Breaks down with multiple key fields/indices for same object Pass in a function Explicit obligation Function parameter Template parameter 73
  74. Comparator Example class intintCompare { public : static bool It (int x, { return x < y; } static bool eq(int x, { return x static bool g t (int x, { return x > y; } 74 int Y) int Y) int Y)
  75. Comparator Example (2) class PayRoll { public : int ID; char* name; class IDCompare { public : static bool It (Payroll & x, { return x. ID < y. ID; } class NameCompare { public : static bool It (Payroll & x, Payroll & y) Payroll & y) { return strcmp (x. name, y. name) < 0; 75
  76. Dictionary ADT // The Dictionary abstract class. template < class Key, class El em, class KEComp, class EEComp> class Dictionary { O; public : virtual virtual virtual virtual virtual virtual 76 void clear() O; bool insert (const Elem&) O; bool remove (const Key & , Elem&) O; bool removeAny (Elem&) bool find (const Key & , Elem&) O; const int size() O;
  77. Unsorted List Dictionary template class UALdict public Dictionary { private: AList* list; public : bool remove (const Key & K, Elem& e) { for (list->setStart ( ) ; list->getValue (e) ; list->next ( ) ) if (KEComp: : eq (K, e) ) list->remove (e) ' return true; return false; 77
  78. Stacks LIFO: Last In, First Out. Restricted form of list: Insert and remove only at front of list. Notation : Insert: PUSH Remove: POP The accessible element is called TOP. 78
  79. Stack ADT // Stack abtract class template class Stack public : // Reinitialize the stack virtual void clear ( ) O; // Push an element onto the top virtual bool push (const Elem&) of the stack. O; // Remove the element at the top of the stack. virtual bool pop (Elem&) O; // Get a copy of the top element in the stack virtual bool topValue (Elem&) const O; // Return the number of elements in the stack. virtual int length() const O; 79
  80. Array-Based Stack // Array-based stack implementation private : int size; int top; // Maximum size of stack // Index for top element Elem *list Array; // Array holding elements Issues: Which end is the top? Where does "top" point to? What is the cost of the operations? 80
  81. Linked Stack // Linked stack implementation private : Link* top; // Pointer to first elem // Count number of elems int size; What is the cost of the operations? How do space requirements compare to the array- based stack implementation? 81
  82. Queues FIFO: First in, First Out Restricted form of list: Insert at one end, remove from the other. Notation : Insert: Enqueue Delete: Dequeue First element: Front Last element: Rear 82
  83. Queue Implementation (1 ) front rear front (a) rear (b) 83
  84. Queue Implementation (2) front 20 (a) 84 5 12 rear front 12 3 30 4 rear (b)
  85. Binary Trees A binary tree is made up of a finite set of nodes that is either empty or consists of a node called the root together with two binary trees, called the left and right subtrees, which are disjoint from each other and from the root. 85
  86. Binary Tree Example Notation: Node, children, edge, parent, ancestor, descendant, path, depth, height, level, leaf node, internal node, subtree. 86 D E F G H
  87. Full and Complete Binary Trees Full binary tree: Each node is either a leaf or internal node with exactly two non-empty children. Complete binary tree: If the height of the tree is d, then all leaves except possibly level d are completely full. The bottom level has all nodes to the left side. (a) 87 (b)
  88. Full Binary Tree Theorem (1 ) Theorem: The number of leaves in a non-empty full binary tree is one more than the number of internal nodes. Proof (by Mathematical Induction): Base case: A full binary tree with 1 internal node must have two leaf nodes. Induction Hypothes is : Assume any full binary tree T containing n-l internal nodes has n leaves. 88
  89. Full Binary Tree Theorem (2) Induction Step: Given tree T with n internal nodes, pick internal node I with two leaf children. Remove I's children, call resulting tree T'. By induction hypothesis, T' is a full binary tree with n leaves. Restore I's two children. The number of internal nodes has now gone up by 1 to reach n. The number of leaves has also gone up by 1 . 89
  90. Full Binary Tree Corollary Theorem: The number of null pointers in a non-empty tree is one more than the number of nodes in the tree. Proof: Replace all null pointers with a pointer to an empty leaf node. This is a full binary tree. 90
  91. class BinNodePtr private: Elem it; BinNodePtr* I c; BinNodePtr* rc; public : Binary Tree Node Class (1) // Binary tree node class template < class Elem> l; public BinNode { // // The n Ode s // Pointer to // Pointer to value left child right child BinNodePtr ( ) BinNodePtr (Elem e, { it 91 NULL; rc BinNodePtr* BinNodePtr* rc 1 r =NULL, =NULL)
  92. Binary Tree Node Class (2) { return it; } Elem& val ( ) void set Val (const Elem& e) { it e; inline BinNode* left ( ) const { return I c; } void set Left (BinNode* b) (BinNodePtr*)b; } inline BinNode* right ( ) const { return r c; } void set Right (BinNode* b) (BinNodePtr*)b; } { rc bool is Leaf ( ) { return (lc 92 NULL) (rc NULL) ;
  93. Traversals (1 ) Any process for visiting the nodes in some order is called a traversal. Any traversal that lists every node in the tree exactly once is called an enumeration Of the tree's nodes. 93
  94. Traversals (2) Preorder traversal: Visit each node before visiting its children. Postorder traversal: Visit each node after visiting its children. Inorder traversal: Visit the left subtree, then the node, then the right subtree. 94
  95. Traversals (3) template // Good implementation void preorder (BinNode* subroot) { // Empty if (subroot NULL) return; // Perform some action visit (subroot) preorder (subroot—>left ( ) ) ; preorder (subroot->right ( ) ) ; template < class Elem> // Bad implementation void preorder 2 (BinNode* subroot) { // Perform some action visit (subroot) if (subroot->left ( ) preorder 2 (subroot->left ( ) ) ; if (subroot->right ( ) preorder 2 (subroot->right ( ) ) ; 95
  96. Traversal Example // Return the number of nodes in the tree template < class Elem> int count (BinNode* subroot) { if (subroot NULL) // Nothing to count return 0; return 1 + count (subroot->left ( ) ) + count (subroot->right ( ) ) ; 96
  97. Binary Tree Implementation (1) 97
  98. Binary Tree Implementation (2) 98
  99. Union Implementation (1) enum Nodetype {leaf, internal}; class VarBinNode { // Generic node class public : Nodetype my type; // Store type for node union { // n ternal node struct { // Left child VarBinNode* left; VarBinNode* right; // Right child Operator opx, } int l; Operand var; 99 // / 1.1 e // Leaf: Value only
  100. Union Implementation (2) // Leaf constructor VarBinNode (const Operand& val) leaf; var v al; { mytype // Internal node constructor VarBinNode (const Operator & op, VarBinNode* l, VarBinNode* r) internal; intl. opx mytYPe op; l; intl. right intl. left r; bool is Leaf() { return my type VarBinNode* left child ( ) { return intl. left; } VarBinNode* right child ( ) { return intl. right; } 100 leaf;
  101. Union Implementation (3) // Preorder traversal void traverse (VarBinNode* subroot) if (subroot NULL) return; if (subroot->isLeaf ( ) ) cout
  102. Inheritance (1 ) // Abstract base class class VarBinNode { public : virtual bool is Leaf ( ) O; class Leaf Node private: Operand var; public : public VarBinNode { // Leaf // Operand value Leaf Node (const Operand& val) } // Constructor val; { var bool is Leaf ( ) { return true; } Operand value ( ) { return var; } 102
  103. Inheritance (2) // Internal node public VarBinNode { class Intl Node private: VarBinNode* left; VarBinNode* right; Operator opx, public : // Left child // Right child // Operator value Intl Node (const Operator & op, VarBinNode* l, VarBinNode* r) l; right OP,• left { opx bool is Leaf ( ) { return false; } VarBinNode* left child ( ) { return left; } VarBinNode* right child ( ) { return right; Operator value ( ) { return opx; } 103
  104. Inheritance (3) // Preorder traversal void traverse (VarBinNode *subroot) { NULL) return; // Empty if subroot // Do leaf node if subroot->isLeaf ( ) ) cout value ( ) ( (Intl Node * ) subroot) ) ; traverse ( ( (Intl Node * ) subroot) ) ; 104
  105. Composite (1 ) // Abstract base class class VarBinNode { public : virtual bool is Leaf ( ) O; virtual void trav() O; class Leaf Node private : Operand var; public : public VarBinNode { // Leaf // Operand value Leaf Node (const Operand& val) } // Constructor val; { var bool is Leaf ( ) { return true; } Operand value ( ) { return var; } void trav() { cout
  106. Composite (2) public VarBinNode { class Intl Node private: VarBinNode* Ice VarBinNode* rc; Operator opx, public: // Left child // Right child // Operator value Intl Node (const Operator & op VarBinNode* l, VarÉinNode* r) l; rc { opx r; bool 1 s Leaf ( ) { return false; VarBinNode* left ( ) { return I c; } VarBinNode* right f) { return r c; } return opx; } void trav() cout
  107. Composite (3) // Preorder traversal void traverse (VarBinNode *root) if (root ! = NULL) 107
  108. Space Overhead (1) From the Full Binary Tree Theorem: Half of the pointers are null. If leaves store only data, then overhead depends on whether the tree is full. Ex: All nodes the same, with two pointers to children: Total space required is (2P + d)n Overhead: 2pn If p = d, this means 2p/(2p + d) = 2/3 overhead. 108
  109. Space Overhead (2) Eliminate pointers from the leaf nodes: n/2(2p) This is 1/2 if p = d. 2p/(2p + d) if data only at leaves 2/3 overhead. Note that some method is needed to distinguish leaves from internal nodes. 109
  110. Array Implementation (1 ) Position Parent Left Child Right Child Left Sibling Right Sibling 110 o I 2 1 O 3 4 2 2 o 5 6 1 3 1 7 8 4 4 1 9 10 3 5 2 11 6 6 2 5 7 3 8 8 3 7 9 4 10 10 4 9 11 5
  111. Array Implementation (1 ) Parent (r) = Leftchild(r) = Rightchild(r) = Leftsibling(r) = Rightsibling(r) = > 111
  112. Binary Search Trees BST Property: All elements stored in the left subtree of a node with value K have values < K. All elements stored in the right subtree of a node with value K have values K. 112
  113. BSTADT(I) // BST implementation for the Dictionary ADT template < class Key, class Elem class KEComp class EÉComp> public Diclionary { // Root of the BST // Number of nodes void clear help (BinNode*) insert help (BinNode* const Elem&) ' deletemin (BinNode* BinNode*&) BinNode* removehelp (ÉinNode* const Key & , bool findhelp (BinNode* const Key&, Elem&) const; void print help (BinNode* int) const; 113
  114. BST ADT(2) public : BST() NULL; nodecount { root A-BST() { clearhelp (root) ; void clear() { clear help (root) ; O; nodecount bool insert (const Elem& e) { insert help (root, e) ' root nodecount++; return true; } bool remove (const Key & K, Elem& BinNode* t NULL; removehelp (root, K, t) root if (t NULL) return false; t->val ( ) ; nodecount-- return true; 114 O; root e) NULL;
  115. BST ADT(3) bool removeAny (Elem& e) { // Delete min value if (root NULL) return false; BinNode* t deletemin (root, t) root t->val ( ) ; nodecount--; return true; bool find (const Key & K, Elem& e) { return findhelp (root, K, e) int size() { return nodecount; } void print() const { if (root NULL) cout
  116. BST Search template < class Key, class El em, class KEComp, class EEComp> bool BST: : findhelp (BinNode* subroot, const Key & K, Elem& e) const { if (subroot NULL) return false; else if (KEComp: : It (K, subroot->val ( ) ) ) return findhelp (subroot->left ( ) , K, e) ; else if (KEComp: : g t (K, subroot->val ( ) ) ) return findhelp (subroot->right ( ) , K, e) ; subroot->val ( ) return true; } 116
  117. BST insert (?) 117
  118. BST Insert (2) template < class Key, class El em, class KEComp, class EEComp> BST: : insert help (BinNode* subroot, const Elem& val) NULL) // Empty: create node if (subroot return new BinNodePtr (val, NULL, NULL) if (EEComp: : It (val, subroot->val ( ) ) ) subroot->setLeft (insert help (subroot->left ( ) val)); else subroot->setRight ( insert help (subroot->right ( ) , val) ) ; // Return subtree with node inserted return subroot; 118
  119. Remove Minimum Value subroot template < class Key, class El em, class KEComp, class EEComp> BST: : deletemin (BinNode* subroot, BinNode*& min) { if (subroot->left ( ) NULL) { min subroot ; return subroot->right ( ) else { // Continue left subroot->setLeft ( deletemin (subroot->left ( ) return subroot; 119 10 20 5 9 5 min) ) ;
  120. BST Remove (1) 97/ 40 42 24 42 32 120 120
  121. BST Remove (2) template < class Key, class El em, class KEComp, class EEComp> BST removehelp (BinNode* subroot, const Key & K, BinNode*& t) if (subroot NULL) return NULL; else if (KEComp: : It (K, subroot->val ( ) ) ) subroot->setLeft ( removehelp (subroot->left ( ) , K, t) ) ; else if (KEComp: : g t (K, subroot->val ( ) ) ) subroot->setRight ( removehelp (subroot->right ( ) , K, t) ) ; 121
  122. BST Remove (2) // Found it: BinNode* temp; subroot ; t if (subroot->left ( ) NULL) subroot->right ( ) subroot else if (subroot->right ( ) subroot subroot->left ( ) ; remove it NULL) // Both children are non-empty subroot->setRight ( deletemin (subroot->right ( ) , temp) ) ; Elem te subroot->val ( ) subroot->setVal (temp->val ( ) ) ; temp->setVal (te) ; t t emp ; return subroot; 122
  123. Heaps Heap: Complete binary tree with the heap property: Min-heap: All values less than child values. Max-heap: All values greater than child values. The values are partially ordered. Heap representation: Normally the array-based complete binary tree representation. 123
  124. Heap ADT template class maxheap{ private : int size; int n; // Pointer to the heap array // Maximum size of the heap // Number of elems now in heap // Put element in place void siftdown (int) • public : maxheap (El em* h, int num, int max) • int heapsize() const; bool is Leaf (int os) const; int left child (in? pos) const; int rightchild (int pos) const; int parent (int pos) const; bool insert (const Elem&) ' bool removemax (Elem&) • bool remove (int Elem&) ' void buildHeap (5 ; 124
  125. Building the Heap (a) (4-2) (4-1) (2-1) (5-2) (5-4) (6-3) (6-5) (7-5) (7-6) (b) (5-2), (7-3), (7-1), (6-1) 125
  126. Siftdown (1 ) For fast heap construction: Work from high end of array to low end. Call siftdown for each item. Don't need to call siftdown on leaf nodes. template < class El em, class Comp> void maxheap • : siftdown (int pos) while ( ! is Leaf( os)} leftcRild (pos) ; int j int rc right child( os) ' •Rt (Héap [j] , Heap [rc] ) ) if. ( (rc
  127. Siftdown (2) 127
  128. Buildheap Cost Cost for heap construction: log n (i - 1) n/21 n. 128
  129. Remove Max Value template bool maxheap: : removemax (Elem& it) { 0) return false; // Heap is empty if (n // Swap max with end swap (Heap, 0, - -n) ; if (n ! 0) siftdown (0) ; // Return max value it Heap ; return true; 129
  130. Priority Queues (1) A priority queue stores objects, and on request releases the Object with greatest value. Example: Scheduling jobs in a multi-tasking operating system. The priority of a job may change, requiring some reordering of the jobs. Implementation: Use a heap to store the priority ql-.lelele. 130
  131. Priority Queues (2) To support priority reordering, delete and re-insert. Need to know index for the object in question. template < class El em, class Comp> bool maxheap: : remove (int pos, Elem& it) { if ( (pos < 0) I (pos >= n)) return false; swap (Heap, pos, --n) ; while ( (pos ! 0) && (Comp: : g t (Heap [pos] , Heap [parent (pos) I)) ) swap (Heap, pos, parent (pos) ) ; siftdown (pos) ; it Heap ; return true; 131
  132. Huffman Coding Trees ASCII codes: 8 bits per character. Fixed-length coding. Can take advantage of relative frequency of letters to save space. Variable-length coding ZI
  133. Huffman Tree Construction (1) Step 2: Step 3: 133
  134. Huffman Tree Construction (2) Step 4: step 5: 134
  135. Assigning Codes 306 120 135 Letter Freq Code Bits 186 D E U 32 42 120 24 7 42 37
  136. Coding and Decoding A set of codes is said to meet the prefix property if no code in the set is the prefix of another. Code for DEED: Expected cost per letter: 136
  137. General Trees Root Parent of V p Ancestors of V Siblings of V Subtree rooted at V Cl 137 Children of V
  138. General Tree Node / / General tree n Ode ADT template < class Elem> class GTNode { public : GTNode (const Elem&) ; ÆTNode ( ) ; Elem value ( ) ; bool is Leaf(); GTNode* parent ( ) • // Constructor // Destructor // Return value // TRUE if is a leaf // Return parent // First child GTNode* leftmost child() • // Right sibling GTNode* right sibling ( ) ; // Set value void set ValueTElem&) • void insert first (GTNode* n) void insert—next (GTNode* n) // Remove first child void remove—first ( ) // Remove sibling void remove—next ( ) 138
  139. General Tree Traversal template < class Elem> void GenTree: : print help (GTNode* subroot) { if (subroot->isLeaf ( ) ) cout < < "Leaf: else cout
  140. Parent Pointer Implementation Node Index 1 2 3 4 56 7 8 9 10 140
  141. Equivalence Class Problem The parent pointer representation is good for answering: Are two elements in the same tree? // Return TRUE if nodes in different trees bool Gen tree: : differ (int int rootl FIND ; int root 2 FIND return rootl ! root 2; 141 a, int b) { // Find root for a // Find root for b // Compare roots
  142. Union/Find void Gentree: : UNION (int a, int b) { // Find root for a int rootl FIND ; // Find root for b int root 2 FIND if (rootl ! root 2) array [root 2] root 1; int Gen tree: : FIND (int cur r) const { while (array [cur r] !=ROOT) curr array [cur r] ; // At root return cur r; Want to keep the depth small. Weighted union rule: Join the tree with fewer nodes to the tree with more nodes. 142
  143. Equiv Class Processing (1) 123456,789 123456789 123456789 143 @0000 oe000
  144. Path Compression int Gen tree: : FIND (int curr) const { if (array [cur r] ROOT) return cur r; return array [cur r] 123456789 o O FIND (array [cur r] ) ; A G o D E
  145. Lists of Children Index Val Par 145
  146. Leftmost Child/Right Sibling ? ? ? 146 C D E 0 0
  147. Leftmost Child/Right Sibling ? 2 ? 147 C D E 0 X Tl m O O > g.)
  148. Linked Implementations (1 ) Val Size 148
  149. Linked Implementations (2) 000 149

Need a Tutor or Coaching Class?

Post an enquiry and get instant responses from qualified and experienced tutors.

Post Requirement

Related PPTs

Upload PPTs

If you have your own PowerPoint Presentations which you think can benefit others, please upload on LearnPick. For each approved PPT you will get 100 Credit Points and 100 Activity Score which will increase your profile visibility.

Upload Now
Home > PowerPoint Slides > Data Structures And Algorithms-Part 1