Data Structures Final

Merge Sort O?

All: O(nlogn)

Bubble Sort O?

B: O(n) W: O(n²) A: O(n²)

Selection Sort

All: O(n²)

Insertion Sort

Best: O(n) Worst: O(n²) Av: O(n²)

Quick Sort

Best: O(nlogn) Worst: O(n²) Av: O(nlogn)

Tree

Acyclic, connected, n-1 edges, n=nodes/vertices

BST & AVL Linked&ArrayList O?

Searching, Insertion, and Deletion: O(logn). BST Worst A(n).

Linked&Array: at least one of methods will be O(n).

Full, Complete, and Regular Binary Tree

Binary tree

– A tree where every node has at most two child nodes

Full binary tree

– A binary tree that has exactly two child nodes and is fully occupied

Complete binary tree

– When a binary tree is not fully occupied, a complete binary tree is the closest approximation to a full binary tree

BST Case 3 Delete

Smallest element in right tree of deleted node takes the place of the deleted node (move right, then try/spam left, if not right then again, until null).

Balance Factor

+-1, 0, right-left

Breadth First Search

O(|V| + |E|), Prioritizes visiting nodes closer in distance to the starting node

Depth First Search

O(|V| + |E|), visits connected nodes based on the node currently being explored

Prim

For finding MST, Min Spanning Tree, O(|E| log| V|). From all claimed nodes,chooses the next cheapest edge. Only claims a node once.

Dijkstras

for finding shortest path; no negative weights; O(|E| log| V|). Chooses the next cheapest path from r to reach an adjacent node from the claimed nodes.

Chaining P/C

• Better with High Load Factors

  • (can be used when (n #keys/m total slots ) > 1)

• Increased look up time for key due to LinkedList

• Requires more memory

Mult Hash P/C

Multiply input value by A, then by table length (m)

• Distributes hash values evenly

• Often O(1) FAST

• Not flexible to changing hash table size, or data distributions

• If A isnt irrational its mid

Division Hash P/C

input % m

• Simple and fast computations

• Excess space typically, so memory inefficient

Open Addressing P/C

Linear/Quadratic Probing/ Double Hashing

• Very memory efficient

• Clustering

• Deletion complexity (need to mark deleted)

• If run out of space and Hash table must double, all saved keys should be relocated

Complete and Simple Graph

C: Max # edges for vertices(n) = n(n-1)/2

S: no self loops or duplicate edges

Adjacency Matrix P/C

two vertices (i, j) stored as 1 or weight # in matrix

if directional, first vertex # goes to second #

• Easy to understand and confirm edges

• Best for high edge density

• Space inefficient

• Lots of time to fill matrix, n²

Adjacency List

Edges that dont exist arent in list at all.

Slot # is Vertex, then following link #s are the edges to the vertex # that exist from such orginal slot # vertex

• Best for sparse graphs

• Memory Efficient

• Checking if edge exists means traversing Linked List, time consuming