Master of Information Technology @ The University of Melbourne

0%

Algorithm Analysis - Data Structure

Posted on Edited on In ,
Symbols count in article: 2.4k Reading time ≈ 2 mins.

Data Structure Overview

  • Array
  • Linked List
  • Stack
  • Queue
  • Priority Queue
  • Binary Tree
  • Hashing

Array

  • Search Pseudocode (Recursive)

    “””
    function find(A,x,lo,hi) lo->0 hi->n-1

    if lo > hi
    return -1
else if lo = A[lo]
    return lo
else
    return find(A,x,lo+1,hi)

    “””

  • Node and Pointer(The pointer in last node is null)
  • Function
    • Value - ListName.val
    • Next Value - ListName.next
  • Search Pseudocode (Recursive)
    “”“
    function find(p,x) p->head
    if p = null then
    return p
else if p.val = x
    return p
else
    return find(p.next,x)
    ”“”

Stack

  • Property： Last In First Out
  • Function：
    • Initial - initilise st as an empty stack
    • Add - st.push(element)
    • Out - st.pop()
    • Null judgement - if st is empty

Queue

  • Property： First In First Out
  • Function：
    • Initial - init(queue)
    • Add - inject(queue,element)
    • Out - eject(queue)
    • Null judgement - if queue is empty
    • Head - queue.head()

Binary Tree

  • Property：
    • Empty Tree Height = -1
  • Traveral：
    • Pre-order
    • In-order
    • Post-order
  • Binary Search Tree [Based on Binary Tree]
    [Property]
    Left Child is LESS THAN Parents;
Right Child is LARGER (OR EQUAL) TO Parents;
    [Count Quantity of Diff elements]
    B(n+1) = B(n) * B(0) + B(n-1) * (1) ... + B(0) * B(n)
  • (AVL)Balanced Binary Search Tree [Based on Binary Search Tree]
    [Property]
    Left Child is LESS THAN Parents;
Right Child is LARGER (OR EQUAL) TO Parents;
[!]The |difference between two children| must be <= 1
    [Balanced Rule]
    L-Rotation
R-Rotation
LR-Rotation
RL-Rotation
  • (2-3Tree)Balanced Binary Search Tree [Based on Binary Search Tree]

Priority Queue(max heap & min heap)

  • [Time Complexity]
    Add element - O(logn)
    Delete the heighest priority element - O(logn)
    Add elements to empty heap - O(nlogn)
    Create a complete binary tree first and then construct from bottom up - O(n)

Hashing (Use Space to Reduce Time)

  • [Handle Collision]
    • Separate Chain : Use link list
      Load Factor(alpha) = n/m ; n:the number of items stored, m: the table size
      Number of probes in successful search: (1+alpha)/2
      Number of probes in unsuccessful search: alpha
    • Open-addressing methods
      • Linear probing : Store in the next index
        Number of probes in successful search: 0.5+1/(2(1-alpha))
        Number of probes in unsuccessful search: 0.5+1/(2(1-alpha)^2)
        #PS 在Linear Probe中查找一个已经被移过位置的key是unsuccessful probing
      • Double hashing : Use another hashing function s(k) to add to the original index[h(k)+s(k)]. If collision again, add 2s(k)……

Graphs

  • [Property]
    • Vertex[V], Edges[E], Weight —>>> G<V,E>
    • Edge(u,v) means the edge between node u and node v
    • two nodes is connected, then we call v and u are ADJACENT or NEIGHBOURS
    • Degree : NUMBER of EDGES connected on a node
      • In-degree : NUMBER of EDGES GOING TO v
      • Out-degree : NUMBER of EDGES LEAVING FROM v
  • [Graph Representation]
    • Adjacency Matrix
      • 0 means not connected, 1 means they are connected
      • for undirrected graph, the AM is Symmetric(对称)
    • Adjacency List
      • e.g (a -> b -> c -> d)