UIUC CS225 Data Structures Final Flashcards

What is the time complexity of inserting an element at the front of an unsorted array?

What is the time complexity of removing an element from the front of an unsorted array?

What is the time complexity of pushing an element onto a stack?

What is the time complexity of popping an element from a stack?

What is the time complexity of enqueueing an element into a queue?

What is the time complexity of dequeueing an element from a queue?

What is the time complexity of inserting an element into a binary tree (general)?

What is the time complexity of removing an element from a binary tree (general)?

What is the average case time complexity of inserting an element into a binary search tree?

What is the time complexity of finding an element in a binary search tree?

What is the time complexity of inserting an element into an AVL tree?

What is the time complexity of finding an element in a hash table (with SUHA)?

What is the time complexity of removing an element from a dictionary?

What is the time complexity of inserting an element into a priority queue?

Runtime Complexity for Data Structures

Unsorted Array Operations
- Insert at Front: O(1)
- Insert: O(n)
- Remove at Front: O(1)
Stack Operations
- Push: O(1)
- Pop: O(1)
Queue Operations
- Enqueue: O(1)
- Dequeue: O(1)

Binary Tree and Variants

Binary Tree (General)
- Insert: O(1)
- Remove: O(n)
- Find: O(n)
- Traverse: O(n)
Binary Search Tree (BST)
- Insert: O(n), average case is O(log n)
- Remove: O(n)
- Find: O(n)
- Traverse: O(n)
AVL Tree (Balanced BST)
- Insert: O(log n)
- Remove: O(log n)
- Find: O(log n)
- Traverse: O(n)
BTree
- Insert: O(log n)
- Remove: O(log n)
- Find: O(log n)
- Traverse: O(n)
- Order m characteristics: max children = m, keys per node between m/2 - 1 and m - 1 (except root)

BTree Properties

Search Complexity: O(m) per node, O(log_m n)
Maximum nodes: ((m^{(h + 1)} - 1) / (m - 1))
Maximum keys: (m^{(h + 1)} - 1)
Minimum nodes: (1 + 2 \cdot \left(\frac{t^h - 1}{t - 1}\right))
Minimum keys: (n \geq 2 \cdot t^h - 1)
Height: (h = O(log n))

Hash Table Operations

SUHA (Straight-Up Hash Array)
- Insert: O(1)
- Remove: O(1)
- Find: O(1)
- Assumes deterministic function and even distribution of keys.
- Resizing occurs when load factor (n/N) exceeds ~2/3, resizing to next prime greater than (2 * current size).
Separate Chaining
- Insert: O(1)
- Remove/Find (without SUHA): O(n)
- Remove/Find (with SUHA): O(load factor)

Dictionary Operations

Insert: O(1)
Remove: O(1)
Find: O(1)

Priority Queue and Heap

Priority Queue
- Insert: O(log n)
- Remove: O(log n)
Heap Operations
- Insert: O(log n)
- Remove Min: O(log n)
- Heapify Up: O(log n)
- Heapify Down: O(log n)
- Build Heap: O(n) through Heapdown; O(n log n) through Heapify Up
- Height: log(n) for n nodes
Heap Array Relations
- Root index: i = 1
- Left Child: i = 2i
- Right Child: i = 2i + 1
- Parent: floor(i/2)

Disjoint Sets

Without Path Compression and Smart Union
- Find: O(n)
- Union: O(1)
With Smart Union
- Find: O(log n)
- Union: O(1)
With Path Compression and Smart Union
- Find: O(1) (worst case O(mlog n))
- Union: O(1)

Test your knowledge of data structures with these flashcards for the UIUC CS225 final. This set covers various operations and their time complexities, focusing on arrays, stacks, and queues. Perfect for quick review and memorization before the exam.