Data Structures Exam 2

Data Structures Exam 2

1. Trees

   • Tree Traversal
     • Preorder
       • root, left child, right child
     • Inorder
       • Left child, Root, Right child
     • Postorder
       • Left child, Right child, Root
   • Types of Trees
     • Binary Trees
       • A binary tree is a tree in which no node can have more than two children. Depth of an average binary tree is sqrt(n)
       • Run Time
         • Search
           • Worst Case: O(n)
           • Average Case: O(log(n))
           • Best Case: O(1)
         • Insert
           • Worst Case: O(n)
           • Average Case: O(log(n))
           • Best Case: O(1)
         • Deletion
           • Worse Case: O(n)
           • Average Case: O(log(n))
           • Best Case: O(1)
     • Search Trees
       • All running times given are for binary search trees. Non binary trees exist but for this course we will be ignoring them.
       • Run Time
         • Search
           • Worst Case: O(n)
           • Average Case: O(log(n))
           • Best Case: O(1)
         • Insert
           • Worst Case: O(n)
           • Average Case: O(log(n))
           • Best Case: O(1)
         • Deletion
           • Worst Case: O(n)
           • Average Case: O(log(n))
           • Best Case: O(1)
     • AVL Tree
       • Run Time
         • Search
           • Worst Case: O(log2(n))
         • Insert
           • Worst Case: O(log2(n))
         • Delete
           • Worst Case: O(log2(n))
       • Conditions
         • Every node in the tree the left and right subtree can differ by at most 1 Therefore minimum num of nodes for heigh h is S(h)=S(h-1)+S(h-2)+1, S(0)=1, S(1)=2
     • Splay Trees
       • Run Time
         • Insert
           • Worst Case: Amoritzed O(log (n))
             •  Generally, when a sequence of M operations has total worst-case running time of O(Mf(N)), we say that the amortized running time is O(f(N)). Thus, a splay tree has an O(logN) amortized cost per operation
           • Average Case: O(log n)
         • Search
           • Average Case: O(log n)
           • Worst Case: Amoritzed O(log (n))
             •  Generally, when a sequence of M operations has total worst-case running time of O(Mf(N)), we say that the amortized running time is O(f(N)). Thus, a splay tree has an O(logN) amortized cost per operation
         • Deletion
           • Average Case: O(log n)
           • Worst Case: Amoritzed O(log (n))
             •  Generally, when a sequence of M operations has total worst-case running time of O(Mf(N)), we say that the amortized running time is O(f(N)). Thus, a splay tree has an O(logN) amortized cost per operation
       • Conditions
         • Each time you search for a node, or delete a node you splay it to the top using AVL rotations. For insertion you go down the tree as in bst, however after inserting you splay to the top
     • B-Trees
       • Run Time
         • B trees minimize disk access
         • Search
           • Average Case: O(log(n))
             • Has to complete linear search once it finds the right key so the total time complexity is more like O(t log(n) )
           • Worst Case: O(log(n))
         • Inset
           • Average Case: O(log(n))
           • Worst Case: O(log(n))
         • Deletion
           • Average Case: O(log(n))
           • Worst Case: O(log(n))
       • Conditions
         • Every path from the root node to a leaf node has an equal length Every node except the root is at least half-filled
       • M-ary Tree
         • Is a B-Tree with order M
         • Conditions
           • 1. The data items are stored at leaves. 2. The nonleaf nodes store up to M − 1 keys to guide the searching; key i represents the smallest key in subtree i+1 3. The root is either a leaf or has between two and M children. 4. All nonleaf nodes (except the root) have between [M/2] and M children. 5. All leaves are at the same depth and have between [L/2] and L data items, for some L (the determination of L is described shortly).
     • 2, 4 Trees
       • Conditions
       • Run Time
     • Red Black Trees
       • Conditions
       • Run Time
         • Search
         • Insert
         • Deletion

2. Heaps (Priority Queue)

   • Binomial Heap
     • Properties
       • Collection of heap ordered trees, known as a forest. Each heap ordered tree is a constrained form known as a binomial tree There is at most one binomial tree of every height
     • Time complexity
       • Get min/max (root): O(1) Delete min/max (root): O(log n) Insert Worst case: O(Log n) Merge: O(Log n) Insert average: O(1)
       • Merge,Insert,DeleteMin,Insertion: O(logN)
       • Insertion average: O(1)
   • Leftest Heap
     • Properties
     • Time complexity
       • Get min/max (root): O(1) Delete min/max (root): O(log n) Insert: O(Log n) Merge: O(Log n)
   • Binary Heap
     • Properties
       • Its root is either greater than or equal to all its children or less than or equal to its children.
     • Time complexity
       • O(log n)
     • Min heap/Max heap
       • A sort of heap that only keeps track of the smallest/largest element and keeps it at the root and has no information on the other
   • General Properties
     • Structure Property -Must be complete binary tree -Height is always O(log N) -Can be represented in an arrayHeap Order Property -Smallest element should be at the root and nodes should be smaller than all of its descendants.
   • Applications
     • Used in operating system design and graph algorithms. Also used in the selection problem and event simulation.
   • Skew Heap
     • Properties
       • Always swap in a skew heap, except the largest of all nodes does not have its children swapped
     • Time complexity
       • Worst Case O(N) Amortized O(MlogN) for M consecutive operations
   • Build Heap
     • Time complexity of build heap is O(n)

3. Hash Functions

   • Separate Chaining
     • Make sure to bring the most recent one to the front. Load factor can rise above 1 without hurting performance very much
   • Linear Probing
     • λ<=.5 Expected number of probes:   1/(1-λ)
   • Quadratic Probing
     • λ<.5
   • Secondary Hash Function
     • You add the secondary hash value to the original output of the hash function. Table size should be prime and λ<=.5 Eliminates primary clustering
   • Load Factor (λ)