Master of Information Technology @ The University of Melbourne

0%

## Data Structure Overview

• Array
• 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)
“”“
``````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
• Out - st.pop()
• Null judgement - if st is empty

## Queue

• Property： First In First Out
• Function：
• Initial - init(queue)
• Out - eject(queue)
• Null judgement - if queue is empty

## 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]
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``
• 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]