Topics covered on Second Midterm

Basic Tree Terminology

n-ary tree: a tree where every node has at most n children

arity: the number of children present on the node with the most children 

binary tree: special form of n-ary tree where every node has at most 2 children (0, 1, or 2 
   children); alternately, a tree of arity 2

complete binary tree: A binary tree in which every level, except possibly the last, is completely 
   filled, and all nodes (all leaves) are as far left as possible; a binary heap structure is a 
   complete binary tree

full binary tree: (sometimes called a proper binary tree) A tree in which every node other than 
   the leaves has exactly two children

perfect binary tree: A binary tree in which every internal node has exactly two children, 
   and all the leaf nodes are at the same (deepest) level. A perfect binary tree with height h has 
   the maximum number of nodes that can be in a binary tree of height h.


perfect binary tree:      A
                       /     \
                      /       \     (no room for more nodes without increasing height of tree)
                     /         \
                    /           \   
                  B               C
                /   \            /  \
               /     \          /    \
              /       \        /      \
             D         E      F        G
            / \       / \    / \      / \
           H   I     J   K  L   M    N   O


complete binary tree:     A
                       /     \
                      /       \        (every level but last is filled (perfect), and
                     /         \        last level is left-packed)
                    /           \   
                  B               C
                /   \            /  \
               /     \          /    \
              /       \        /      \
             D         E      F        G
            / \       / \    / 
           H   I     J   K  L 


full binary tree:         A
                       /     \    (every node not a leaf has 2 children)
                      /       \   (every node has 0 children, or 2 children)
                     /         \
                    /           \   
                  B               C
                /   \                
               /     \                
              /       \                
             D         E                
                      / \                
                     J   K                

//===========================================================================

Sets and Maps
ADT ops, behavior, and ways to implement them (lists, trees, hashing, etc.)

//===========================================================================

Hashing, Hash Tables, Hash Maps
  Pigeon hole principle (chicken hole principle)
  Hash Table, hash function
    how to pick table size
    how to make an effective hash function
    what to do about collisions
      hash into linked lists (or other collection data structures)
        table size should be prime, and same the size as # elements expected
      probing to find an open cell in the table
        linear probing function
        quadratic probing function
        "expo" probing function
      table size should be prime, and twice the # elements expected
    Rehasing to extend the table size

  Hash Maps... storing associated information/object along with a hashed key

//===========================================================================

Blockchain
  SHA-256 Cryptographic hash function
  basic block chain construction and operation
  nonce
  "mining" what it is, how it's done
  complexity of the hashing used in mining blocks (for Bitcoin application)

//===========================================================================

binary heap 
  a binary heap is a completely different thing from the runtime heap... 
    runtime heap is not heap-structured, not related at all
    just unfortunate and maybe a bit confusing to share the name "heap"

  binary tree with two properties:
    heap order property
    structure property 
      always a complete binary tree, with 
          last level being filled from L to R but perhaps not full
  representation of binary heap as array
  heaps can be Min or Max

  operations:
    getMin (Max) 
      O(1) worst, avg since it is at the root of the heap tree
    removeMin (Max) 
      O(log N) worst case
      O(log N) average case
    add 
      O(log N) worst case
      O(1) average case (75% of the heap elements in last 2 tree levels)
    incElt, decElt
      cost of searching for the Elt, then plus cost of rearranging the heap array when
                                     the priority is incremented or decremented
      searching the array linearly is O(N)
      using a HashMap (like Assn 4) is O(1)
      cost of rearranging the heap array in O(log N)
    build 
      simple way is O(N log N) by doing N adds
      cleaver way is O(N) if you have all the elements on hand, use special "build"

//===========================================================================

priority queue
  limplementing priority queue with list, BST
  implement priority queue using binary heap
  elements stored have value and priority
    priority is used to put elements into binary heap 
  operations:
    enq: add item to PrQUE
    deq: take item out of the PrQUE, and that item is "highest" (or lowest) priority
    front: produce element from queue that has "highest" (or lowest) priority
    size, empty, etc...

//===========================================================================

Sorting
  we have discussed and analyzed these sorting methods:
    -- Bubble Sort: rearranging the items in an array/list to put them in order
                    "gold standard of badness" since it's O(N^2) worst case as well as avg case
    -- keeping a basic List sorted (using inSort operation)
    -- BST sort: build a binary search tree and do in-order traversal
                 (worst case analysis, and average case analysis)
    -- AVL sort: BST with balancing... avg and worst cases for sorting N elements
    -- sorting using hashing (bucket sort)
    -- Sorting with a binary heap

heap sort 
  special "build" a binary heap
  do repeated getMin(),delMin() to create the ordered sequence
  worst case time complexity if we do repeated insert to construct heap
  worst case time complexity if we do special magic build to construct heap

//===========================================================================

Tree representations (linked cells, implicit as array)
  We have represented a tree (binary tree) as
    -- linked cells (basic unbalanced BST, also used for balanced methods like AVL, Splay)
    -- array (binary heap)
         in array representation, the links are implicit
         and are obtained via array subscript arithmetic
    -- know why implicit, array representation works ok for binary heap, not for general case of binary tree

//===========================================================================

Balanced BST
Tree balancing:
  AVL: imbalance condition, rotations to re-balance
       rotations alter tree structure but maintain the order property
       worst case time complexity for insert, remove, contains
       show how AVL tree is altered by insert, remove

  Splay: another approach to balancing
         splaying done any time a node is accessed
         splaying is applying preserving rotations until accesses node
           is moved to the root
         amortized worst case time complexity
         show how splaying works in a tree for insert, remove, find, etc.